home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_09_05 / 9n05128a < prev    next >
Text File  |  1991-03-19  |  3KB  |  97 lines
  1. /*
  2. l_distance()   Determins to what extent two character strings
  3.                are (un)equal using the 'Levenstein distance'
  4.                algorithm.
  5.  
  6. Limitation:    For memory space conservation and execution speed
  7.                this implementation compares the first 20 
  8.                characters of both string only if longer strings
  9.                are supplied to l_distance().
  10.                '#define COMP_LEN' may be changed to decrease or
  11.                increase the number of characters compared.
  12.  
  13.                De-commenting the following '#define DEBUG' will
  14.                create a stand-alone program, which enables you
  15.                to experiment with different values for the 
  16.                constants 'addition', 'change' and 'deletion'.
  17. */
  18.  
  19. /* #define DEBUG */
  20.  
  21. #include <stdlib.h>
  22. #include <string.h>
  23.  
  24. #ifdef DEBUG
  25. #include <stdio.h>
  26. #endif
  27.  
  28. int     addition = 1;           /* change constants in this block */
  29. int     change   = 3;           /* of four lines if needed.       */
  30. int     deletion = 5;
  31. #define COMP_LEN                20
  32.  
  33. #define ARR_SIZE                COMP_LEN + 1
  34. #define SMALLEST_OF(x,y,z)      ( (x<y) ? min(x,z) : min(y,z) )
  35. #define ZERO_IF_EQUAL(x,y)      (requested[x-1] == found[y-1] ? 0 : change)
  36.  
  37. int     distance[ARR_SIZE][ARR_SIZE];
  38.  
  39.  
  40. int l_distance(char *requested, char *found)
  41. {
  42.    register int i,j;
  43.    int r_len, f_len;
  44.  
  45.    r_len = (strlen(requested)>COMP_LEN ? COMP_LEN : strlen(requested));
  46.    f_len = (strlen(found)>COMP_LEN ? COMP_LEN : strlen(found));
  47.  
  48.    distance[0][0] = 0;
  49.    for (j = 1; j <= ARR_SIZE ; j++)
  50.       distance[0][j] = distance[0][j-1] + addition;
  51.    for (j = 1; j <= ARR_SIZE ; j++)
  52.       distance[j][0] = distance[j-1][0] + deletion;
  53.  
  54.    for (i = 1; i <= r_len; i++)
  55.       for (j = 1; j <= f_len; j++)
  56.          distance[i][j] = SMALLEST_OF(
  57.                             (distance[i-1][j-1] + ZERO_IF_EQUAL(i,j)),
  58.                             (distance[i][j-1]   + addition),    
  59.                             (distance[i-1][j]   + deletion)  );
  60.  
  61. #ifdef DEBUG
  62.    printf("\n");
  63.    for (i = 1; i <= r_len; i++) {
  64.       for (j = 1; j <= f_len; j++)
  65.          printf("  %3d",distance[i][j]);
  66.       printf("\n");
  67.    }
  68. #endif
  69.  
  70.    return( distance [r_len] [f_len] );
  71. }
  72.  
  73. #ifdef DEBUG
  74. void usage()
  75. {
  76.    printf("\nUsage:  LD requested found\n");
  77.    printf("\n        requested & found are the two strings");
  78.    printf("\n        to be compared with the Levenstein distance");
  79.    printf("\n        algorithm.\n\n");
  80. }
  81.  
  82. int main(int argc, char *argv[])
  83. {
  84.    int result;
  85.  
  86.    if (argc != 3) {
  87.       usage();
  88.       exit(1);
  89.    } else {
  90.       printf("\nComparing '%s' and '%s':\n", argv[1], argv[2]);
  91.       result = l_distance(argv[1], argv[2]);
  92.       printf("\nResult = %d\n", result);
  93.    }
  94.    return(0);
  95. }
  96. #endif
  97.