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