home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / snippet.exe / APPROX.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-01-02  |  5.0 KB  |  169 lines
  1. /***************************************************************
  2.  *
  3.  * Fuzzy string searching subroutines
  4.  *
  5.  * Author:    John Rex
  6.  * Date:      August, 1988
  7.  * References: (1) Computer Algorithms, by Sara Baase
  8.  *                 Addison-Wesley, 1988, pp 242-4.
  9.  *             (2) Hall PAV, Dowling GR: "Approximate string matching",
  10.  *                 ACM Computing Surveys, 12:381-402, 1980.
  11.  *
  12.  * Verified on:
  13.  *    Datalite, DeSmet, Ecosoft, Lattice, MetaWare, MSC, Turbo, Watcom
  14.  *
  15.  * Compile time preprocessor switches:
  16.  *    DEBUG - if defined, include test driver
  17.  *
  18.  * Usage:
  19.  *
  20.  *    char *pattern, *text;  - search for pattern in text
  21.  *    int degree;      - degree of allowed mismatch
  22.  *    char *start, *end;
  23.  *    int howclose;
  24.  *
  25.  *    void App_init(pattern, text, degree);   - setup routine
  26.  *    void App_next(&start, &end, &howclose); - find next match
  27.  *
  28.  *    - searching is done when App_next() returns start==NULL
  29.  *
  30.  **************************************************************/
  31.  
  32. #define DEBUG 1
  33.  
  34. #include <stdio.h>
  35. #include <stdlib.h>
  36. #include <string.h>
  37.  
  38. /* local, static data */
  39.  
  40. static char *Text, *Pattern; /* pointers to search strings       */
  41. static int Textloc;          /* current search position in Text  */
  42. static int Plen;             /* length of Pattern                */
  43. static int Degree;           /* max degree of allowed mismatch   */
  44. static int *Ldiff, *Rdiff;   /* dynamic difference arrays        */
  45. static int *Loff,  *Roff;    /* used to calculate start of match */
  46.  
  47. void App_init(char *pattern, char *text, int degree)
  48. {
  49.       int i;
  50.  
  51.       /* save parameters */
  52.  
  53.       Text = text;
  54.       Pattern = pattern;
  55.       Degree = degree;
  56.  
  57.       /* initialize */
  58.  
  59.       Plen = strlen(pattern);
  60.       Ldiff  = (int *) malloc(sizeof(int) * (Plen + 1) * 4);
  61.       Rdiff  = Ldiff + Plen + 1;
  62.       Loff   = Rdiff + Plen + 1;
  63.       Roff   = Loff +  Plen + 1;
  64.       for (i = 0; i <= Plen; i++)
  65.       {
  66.             Rdiff[i] = i;   /* initial values for right-hand column */
  67.             Roff[i]  = 1;
  68.       }
  69.  
  70.       Textloc = -1; /* current offset into Text */
  71. }
  72.  
  73. void App_next(char **start, char **end, int *howclose)
  74. {
  75.       int *temp, a, b, c, i;
  76.  
  77.       *start = NULL;
  78.       while (*start == NULL)  /* start computing columns */
  79.       {
  80.             if (Text[++Textloc] == '\0') /* out of text to search! */
  81.                   break;
  82.  
  83.             temp = Rdiff;   /* move right-hand column to left ... */
  84.             Rdiff = Ldiff;  /* ... so that we can compute new ... */
  85.             Ldiff = temp;   /* ... right-hand column */
  86.             Rdiff[0] = 0;   /* top (boundary) row */
  87.  
  88.             temp = Roff;    /* and swap offset arrays, too */
  89.             Roff = Loff;
  90.             Loff = temp;
  91.             Roff[1] = 0;
  92.  
  93.             for (i = 0; i < Plen; i++)    /* run through pattern */
  94.             {
  95.                   /* compute a, b, & c as the three adjacent cells ... */
  96.  
  97.                   if (Pattern[i] == Text[Textloc])
  98.                         a = Ldiff[i];
  99.                   else  a = Ldiff[i] + 1;
  100.                   b = Ldiff[i+1] + 1;
  101.                   c = Rdiff[i] + 1;
  102.  
  103.                   /* ... now pick minimum ... */
  104.  
  105.                   if (b < a)
  106.                         a = b;
  107.                   if (c < a)
  108.                         a = c;
  109.  
  110.                   /* ... and store */
  111.  
  112.                   Rdiff[i+1] = a;
  113.             }
  114.  
  115.             /* now update offset array */
  116.             /* the values in the offset arrays are added to the
  117.                current location to determine the beginning of the
  118.                mismatched substring. (see text for details) */
  119.  
  120.             if (Plen > 1) for (i=2; i<=Plen; i++)
  121.             {
  122.                   if (Ldiff[i-1] < Rdiff[i])
  123.                         Roff[i] = Loff[i-1] - 1;
  124.                   else if (Rdiff[i-1] < Rdiff[i])
  125.                         Roff[i] = Roff[i-1];
  126.                   else if (Ldiff[i] < Rdiff[i])
  127.                         Roff[i] = Loff[i] - 1;
  128.                   else /* Ldiff[i-1] == Rdiff[i] */
  129.                         Roff[i] = Loff[i-1] - 1;
  130.             }
  131.  
  132.             /* now, do we have an approximate match? */
  133.  
  134.             if (Rdiff[Plen] <= Degree)    /* indeed so! */
  135.             {
  136.                   *end = Text + Textloc;
  137.                   *start = *end + Roff[Plen];
  138.                   *howclose = Rdiff[Plen];
  139.             }
  140.       }
  141.  
  142.       if (start == NULL) /* all done - free dynamic arrays */
  143.             free(Ldiff);
  144. }
  145.  
  146. #ifdef DEBUG
  147.  
  148. void main(int argc, char **argv)
  149. {
  150.       char *begin, *end;
  151.       int howclose;
  152.  
  153.       if (argc != 4)
  154.       {
  155.             puts("Usage is: approx pattern text degree\n");
  156.             exit(0);
  157.       }
  158.  
  159.       App_init(argv[1], argv[2], atoi(argv[3]));
  160.       App_next(&begin, &end, &howclose);
  161.       while (begin != NULL)
  162.       {
  163.             printf("Degree %d: %.*s\n", howclose, end-begin+1, begin);
  164.             App_next(&begin, &end, &howclose);
  165.       }
  166. }
  167.  
  168. #endif
  169.