home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_09_05 / 9n05130a < prev    next >
Text File  |  1991-03-19  |  4KB  |  125 lines
  1. /*
  2. is_alike()     Determins whether two character strings are
  3.                sufficiently 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. See l_distance.c()
  9.                listing.
  10.                '#define COMP_LEN' may be changed to decrease or
  11.                increase the number of characters compared.
  12.  
  13. Returns:       The constant ACCEPTED or REJECTED.
  14.  
  15.                De-commenting the following '#define DEBUG' will
  16.                create a stand-alone program, which enables you
  17.                to experiment with different values for the 
  18.                constants 'addition', 'change' and 'deletion'.
  19. */
  20.  
  21. /* #define DEBUG */
  22.  
  23. #include <stdlib.h>
  24. #include <string.h>
  25. #include <math.h>
  26. #include <ctype.h>
  27.  
  28. #ifdef DEBUG
  29. #include <stdio.h>
  30. #endif
  31.  
  32. int     addition = 1;    /* change constants in this block */
  33. int     change   = 2;    /* of four lines if needed.       */
  34. int     deletion = 3;
  35.  
  36. #define COMP_LEN         20
  37. #define TU(x)            toupper(x)
  38. #define ARR_SIZE         COMP_LEN + 1
  39. #define SMALLEST_OF(x,y,z)  ( (x<y) ? min(x,z) : min(y,z) )
  40. #define ZERO_IF_EQUAL(x,y)  (TU(requested[x-1])==TU(found[y-1]) ? 0 : change)
  41. #define ACCEPTED         1
  42. #define REJECTED         0
  43.  
  44. int     distance[ARR_SIZE][ARR_SIZE];
  45.  
  46. int is_alike(char *requested, char *found)
  47. {
  48.    register int i,j;
  49.    int r_len, f_len, threshold;
  50.  
  51.    /* first test: compare first character of both strings */
  52.    if (toupper(*requested) != toupper(*found))   {
  53.       #ifdef DEBUG
  54.          printf("\nRejected due to difference in first letters\n");
  55.       #endif
  56.       return(REJECTED);            /* different first characters */
  57.    }
  58.  
  59.    r_len = (strlen(requested)>COMP_LEN ? COMP_LEN : strlen(requested));
  60.    f_len = (strlen(found)>COMP_LEN ? COMP_LEN : strlen(found));
  61.  
  62.    /* second test: comparing string length */
  63.    threshold = (int)  floor( (double) 1 + ((r_len + 2) / 4));
  64.    if ( abs(r_len - f_len) > threshold) {
  65.       #ifdef DEBUG
  66.          printf("\nRejected due to large length difference\n");
  67.       #endif
  68.       return(REJECTED);         /* length difference too big */
  69.    }
  70.  
  71.    distance[0][0] = 0;
  72.    for (j = 1; j <= ARR_SIZE ; j++)
  73.       distance[0][j] = distance[0][j-1] + addition;
  74.    for (j = 1; j <= ARR_SIZE ; j++)
  75.       distance[j][0] = distance[j-1][0] + deletion;
  76.  
  77.    for (i = 1; i <= r_len; i++)
  78.       for (j = 1; j <= f_len; j++)
  79.          distance[i][j] = SMALLEST_OF(
  80.                           (distance[i-1][j-1] + ZERO_IF_EQUAL(i,j)),
  81.                           (distance[i][j-1]   + addition),
  82.                           (distance[i-1][j]   + deletion)  );
  83. #ifdef DEBUG
  84.    printf("\nis_alike(): threshold %d\n\n",threshold);
  85.    for (i=1; i <= r_len; i++) {
  86.       for (j=1; j <= f_len; j++)
  87.          printf("  %3d",distance[i][j]);
  88.       printf("\n");
  89.    }
  90.    printf("\nis_alike(): l_distance is %d\n",distance[r_len][f_len]);
  91. #endif
  92.  
  93.    /* third test: Levenstein distance within threshold limit ? */
  94.  
  95.    if ( distance[r_len][f_len] <= threshold )
  96.       return(ACCEPTED);                /* distance within limits */
  97.    else
  98.       return(REJECTED);                /* distance too big */
  99. }
  100.  
  101. #ifdef DEBUG
  102. void usage()
  103. {
  104.    printf("\nUsage:  IA requested found\n");
  105.    printf("\n        requested & found are the two strings to");
  106.    printf("\n        be compared with the is_alike() function");
  107.    printf("\n        containing the Levenstein distance algorithm.\n\n");
  108. }
  109.  
  110. int main(int argc, char *argv[])
  111. {
  112.    if (argc != 3) {
  113.       usage();
  114.       exit(1);
  115.    } else {
  116.       printf("\nMain(): Comparing '%s' and '%s':\n", argv[1], argv[2]);
  117.       if (is_alike(argv[1], argv[2]))
  118.          printf("\nMain(): Strings sufficiently alike...\n\n");
  119.       else
  120.          printf("\nMain(): Strings differing too much...\n\n");
  121.    }
  122.    return(0);
  123. }
  124. #endif
  125.