home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource4 / 248_01 / matches.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-08-18  |  12.1 KB  |  487 lines
  1. /*
  2. **    name:        matches.c
  3. **    purpose:    Words that almost match pattern searching
  4. **    source:        Computer Language - November 1986
  5. **            by Dave Taylor
  6. **    coded:        1988.11.07 - Roberto Artigas Jr
  7. **    NOTES:        This set of routines comes from a number of
  8. **            sources, all I did is integrate them into a
  9. **            subroutine that uses all the methods for
  10. **            text matches.
  11. */
  12. #define    DEBUG    0    /* 0 = NO debug, 1 = YES debug */
  13. #define    TEST    0    /* 0 = library, 1 = mainline test */
  14.  
  15. #include    <stdio.h>
  16. #include    <stdlib.h>
  17. #include    <ctype.h>
  18. #include    <string.h>
  19.  
  20. #ifdef    tolower
  21. #undef    tolower
  22. #endif
  23. #define    tolower(c)    (isupper(c) ? c - 'A' + 'a' : c)
  24. #ifdef    min
  25. #undef    min
  26. #endif
  27. #define    min(a,b)    ((a) < (b) ? (a) : (b))
  28.  
  29. /*
  30. **    Defined constants
  31. */
  32. #define    WORD_LENGTH    40
  33. #define    THRESHOLD    0.500    /* PF474 */
  34. #define    THRESHOLD2    0.750    /* GESTALT */
  35. #define    SOUNDEX_LENGTH    4    /* soundex */
  36. #ifndef    TRUE
  37. #define    TRUE        1
  38. #define    FALSE        0
  39. #endif
  40. /*
  41. **    For the soundex algorithm: 'x' means 'delete this letter'
  42. */
  43. #define    index_of(ch)    (ch - 'A')
  44. #define    IGNORE        'x'
  45. static    char soundex_mappings[] = { "x123x12xx22455x12623x1x2x2" };
  46. /*
  47. **    Routine prototypes
  48. */
  49. char    *remove_duplicate_letters();
  50. char    *translate_case();
  51. char    *soundex_translation_of();
  52. char    *reverse();
  53. double    pf474_algorithm();
  54.  
  55.  
  56. /*
  57. **    name:        reverse
  58. **    purpose:    Reverse the word and return it
  59. */
  60. char    *reverse(word)
  61. char    *word;
  62. {
  63.     static char    buffer[WORD_LENGTH];
  64.     register int    i, j = 0;
  65.     for (i=strlen(word)-1; i > -1; i--)
  66.         buffer[j++] = word[i];
  67.     buffer[j] = '\0';
  68.     return((char *)buffer);
  69. }
  70.  
  71.  
  72. /*
  73. **    name:        translate_case
  74. **    purpose:    Destructively translate the word to all lowercase
  75. **            returning both the altered word and a pointer to
  76. **            the altered word
  77. */
  78. char    *translate_case(word)
  79. char    *word;
  80. {
  81.     register int    index;
  82.     for (index = 0; index < strlen(word); index++)
  83.         word[index] = tolower(word[index]);
  84.     return((char *)word);
  85. }
  86.  
  87. /*
  88. **    name:        remove_duplicate_letters
  89. **    purpose:    This routine removes all multiply occurring
  90. **            letters in the given word and returns a
  91. **            'sanitized' version of the word. For example,
  92. **            given 'missionary' it returns 'misionary'.
  93. */
  94. char    *remove_duplicate_letters(word)
  95. char    *word;
  96. {
  97.     register int    index, bindex = 0;
  98.     static char    buffer[WORD_LENGTH] = { "" };
  99.     buffer[bindex++] = word[0];
  100.     for (index = 1; index < strlen(word); index++)
  101.         if (word[index-1] != word[index])
  102.             buffer[bindex++] = word[index];
  103.     buffer[bindex] = 0;
  104.     return((char *)buffer);
  105. }
  106.  
  107.  
  108. /*
  109. **    name:        check_transpositions
  110. **    purpose:    Transposes character pairs in word to see if
  111. **            any match the given patter. Returns TRUE if
  112. **            so, FALSE if not
  113. */
  114. int    check_transpositions(word,pattern)
  115. char    *word;
  116. char    *pattern;
  117. {
  118.     register int    index;
  119.     char        spare_character;
  120.     for (index=1; index < strlen(word); index++) {
  121.         spare_character = word[index];
  122.         word[index] = word[index-1];
  123.         word[index-1] = spare_character;
  124.         if (strcmp(word,pattern) == 0)
  125.             return(TRUE);
  126.         word[index-1] = word[index];
  127.         word[index] = spare_character;
  128.     }
  129.     return(FALSE);
  130. }
  131.  
  132. /*
  133. **    name:        allow_a_missing_character
  134. **    purpose:    This routine returns TRUE if word is the
  135. **            same as pattern, just missing a single letter.
  136. **    1988.10.07    Roberto Artigas Jr - If word and pattern
  137. **            is a length of one and not an exact match exit
  138. **            saying that it is false
  139. */
  140. int    allow_a_missing_character(word, pattern)
  141. char    *word;
  142. char    *pattern;
  143. {
  144.     register int    index, windex = 0;
  145.     if ((strlen(word)==1) && (strlen(pattern)==1) && (*word != *pattern))
  146.         return(FALSE);
  147.     if (strlen(word) + 1 != strlen(pattern))
  148.         return(FALSE);
  149.     for (index=0, windex=0; index < strlen(pattern); index++)
  150.         if (word[windex] == pattern[index])
  151.             windex++;
  152.         else if (windex < index)
  153.             return(FALSE);
  154.     if (word[windex] == pattern[index])
  155.          return(TRUE);
  156.     else
  157.         return(FALSE);
  158. }
  159.  
  160. /*
  161. **    name:        allow_an_incorrect_character
  162. **    purpose:    This routine returns TRUE if word is the same
  163. **            as pattern, just with a single incorrect letter.
  164. **    1988.10.07    Roberto Artigas Jr - If word and pattern
  165. **            is a length of one and not an exact match exit
  166. **            saying that it is false
  167. */
  168. int    allow_an_incorrect_character(word,pattern)
  169. char    *word;
  170. char    *pattern;
  171. {
  172.     register int    index, windex;
  173.     register int    already_seen_bad_letter = FALSE;
  174.     if (strlen(word) != strlen(pattern))
  175.         return(FALSE);
  176.     if ((strlen(word)==1) && (strlen(pattern)==1) && (*word != *pattern))
  177.         return(FALSE);
  178.     for (index=0, windex=0; index < strlen(pattern); index++) {
  179.         if (word[windex] == pattern[index])
  180.             windex++;
  181.         else if (already_seen_bad_letter)
  182.             return(FALSE);
  183.         else {
  184.             already_seen_bad_letter++;
  185.             windex++;
  186.         }
  187.     }
  188.     return(TRUE);
  189. }
  190.  
  191. /*
  192. **    name:        soundex_translation_of
  193. **    purpose:    Implement soundex algorithm tranlation
  194. */
  195. char    *soundex_translation_of(buffer)
  196. char    *buffer;
  197. {
  198.     static char    result[WORD_LENGTH];
  199.     register int    i, j, ch, newch;
  200.     result[0] = toupper(buffer[0]);
  201.     result[1] = result[2] = result[3] = '0';
  202.     result[4] = '\0';
  203.     for (i=1, j=1; i < strlen(buffer) && j < SOUNDEX_LENGTH; i++) {
  204.         ch = toupper(buffer[i]);
  205.         if ((newch = soundex_mappings[index_of(ch)]) != IGNORE)
  206.             if (result[j-1] != (char)newch)
  207.                 if (!(j == 1 && ch == result[0]))
  208.                     result[j++] = (char)newch;
  209.     }
  210.     return((char *)result);
  211. }
  212.  
  213. /*
  214. **    name:        soundex
  215. **    puspose:    Implements matching based on the soundex
  216. **            algorithm - this simple part gets the two
  217. **            words 'Soundex'ized then returns a nonzero
  218. **            if the two match on this technique.
  219. */
  220. int    soundex(word,pattern)
  221. char    *word;
  222. char    *pattern;
  223. {
  224.     char        word2[WORD_LENGTH];
  225.     char        pattern2[WORD_LENGTH];
  226.     strcpy(word2,soundex_translation_of(word));
  227.     strcpy(pattern2,soundex_translation_of(pattern2));
  228.     return((strcmp(word2,pattern2)==0));
  229. }
  230.  
  231. /*
  232. **    name:        proximity_value
  233. **    purpose:    This actually implements the algorithm used
  234. **            in the PF474 pattern matching chip from
  235. **            Proximity technologies, returning the number
  236. **            of matches encountered.
  237. */
  238. int    proximity_value(word,pattern)
  239. char    *word;
  240. char    *pattern;
  241. {
  242.     int    matches = 0, count = 1;
  243.     int    iteration, index, len;
  244.     if (strcmp(word,pattern) == 0) {
  245.         for (count=0; count <= strlen(word); count++)
  246.             matches += (2*count);
  247.         return(matches);
  248.     }
  249.      len = min(strlen(word),strlen(pattern)) + 1;
  250.     count =1;
  251.     do {
  252.     for (iteration=1; iteration<len; iteration++)
  253.         for (index=0; index<iteration; index++)
  254.             if (tolower(word[index]) == tolower(pattern[index]))
  255.                 matches++;
  256.         strcpy(word,reverse(word));
  257.         strcpy(pattern,reverse(pattern));
  258.     } while (count++ < 2);
  259.     return(matches);
  260. }
  261.  
  262. /*
  263. **    name:        pf474_algorithm
  264. **    purpose:    This is the top-level PF474 pattern matching
  265. **            routines. It implements the equation we are
  266. **            using
  267. */
  268. double    pf474_algorithm(word,pattern)
  269. char    *word;
  270. char    *pattern;
  271. {
  272.     if (strlen(word) == 0 && strlen(pattern) == 0)
  273.         return((double)1.0);
  274.     return((double) (proximity_value(word,pattern) /
  275.         (proximity_value(word,word)+proximity_value(pattern,pattern))));
  276. }
  277.  
  278. /*
  279. **    name:        GCsubstr
  280. **    purpose:    Recursive greatest common sub-string
  281. */
  282. int    GCsubstr(st1, end1, st2, end2)
  283. char    *st1;
  284. char    *end1;
  285. char    *st2;
  286. char    *end2;
  287. {
  288.     register char    *a1, *b1, *s1, *a2, *b2, *s2;
  289.     short        max, i;
  290.  
  291.     if (end1 <= st1)        /* s1 empty */
  292.       return (0);
  293.     if (end2 <= st2)        /* s2 empty */
  294.       return (0);
  295.     if (end1 == st1 + 1)        /* s1 has one char */
  296.       if (end2 == st2 + 1)        /* and s2 has one char */
  297.         return (0);            /* They cannot be equal */
  298.  
  299.     max = 0;
  300.     b1 = end1; b2 = end2;
  301.  
  302.     for (a1 = st1; a1 < b1; a1++)
  303.        for (a2 = st2; a2 < b2; a2++)
  304.           if (*a1 == *a2)
  305.             {            /* How long common sub-string? */
  306.         for (i = 1; a1[i] && (a1[i] == a2[i]); i++)
  307.            ;
  308.         if (i > max)
  309.           {
  310.           max = i; s1 = a1; s2 = a2;
  311.           b1 = end1 - max; b2 = end2 - max;
  312.           }
  313.         }
  314.     if (! max)
  315.       return (0);
  316.  
  317.     max += GCsubstr(s1 + max, end1, s2 + max, end2);    /* RHS */
  318.     max += GCsubstr(st1, s1, st2, s2);            /* LHS */
  319.  
  320.     return(max);
  321. }
  322.  
  323. /*
  324. **    name:        simil
  325. **    purpose:    Best guess matches
  326. **    author:        Ratcliff/Obershelp pattern matching
  327. **    source:        Pattern matching by Gestalt
  328. **            by John W. Ratcliff
  329. **            Dr. Dobb's Journal #141 - July 1988
  330. */
  331. double    simil(s1,s2)
  332. char    *s1;
  333. char    *s2;
  334. {
  335.     short    l1;
  336.     short    l2;
  337.  
  338.     l1 = strlen(s1);
  339.     l2 = strlen(s2);
  340.  
  341.     if ( l1 == 1)            /* Check for easiest case */
  342.       if (l2 == 1)
  343.         if (*s1 == *s2)
  344.            return(100.0);
  345.  
  346.     return(2.0 * GCsubstr(s1, s1 + l1, s2, s2 + l2) / (l1 + l2));
  347. }
  348.  
  349. /*
  350. **    name:        matches
  351. **    purpose:    Apply all pattern matching techniques to get
  352. **            a list of possible words to substitute
  353. */
  354. int    matches(word,pattern)
  355. char    *word;
  356. char    *pattern;
  357. {
  358.     static    double    pf474_value;
  359.     static    double    percnt;
  360.     static    int    pword;        /* Difference after drop duplicates */
  361.     static    int    ppatt;        /* Difference after drop duplicates */
  362.     static    int    i;        /* For loops */
  363.  
  364.     if (strcmp(word,pattern) == 0) {
  365. #if    TEST 
  366.         printf("MATCHED by comparison (EXACT)\n");
  367. #endif
  368.         return(1);
  369.     }
  370.     translate_case(word);
  371.     translate_case(pattern);
  372.     if (strcmp(word,pattern) == 0) {
  373. #if    TEST 
  374.         printf("MATCHED by translation of case\n");
  375. #endif
  376.         return(2);
  377.     }
  378. /*
  379. **    We remove all duplicate characters and count how many we have
  380. **    removed.  This will allow some measure of control with eccessive
  381. **    matches
  382. */
  383.     pword = strlen(word);
  384.     ppatt = strlen(pattern);
  385.     strcpy(word,remove_duplicate_letters(word));
  386.     strcpy(pattern,remove_duplicate_letters(pattern));
  387.     pword -=strlen(word);
  388.     ppatt -=strlen(pattern);
  389.     if (strcmp(word,pattern)==0) {
  390. #if    TEST 
  391.         printf("MATCHED by removal of duplicate letters\n");
  392. #endif
  393.         return(3);
  394.     }
  395.     if (check_transpositions(word,pattern)) {
  396. #if    TEST 
  397.         printf("MATCHED by transposition of letters\n");
  398. #endif
  399.         return(4);
  400.     }
  401.     if (allow_a_missing_character(word,pattern)) {
  402.         if (!(abs((pword-ppatt)+(strlen(word)-strlen(pattern)))>1)) {
  403. #if    TEST 
  404.             printf("MATCHED by allowance of a missing character\n");
  405. #endif
  406.             return(5);
  407.         }
  408.     }
  409.     if (allow_an_incorrect_character(word,pattern)) {
  410. #if    TEST 
  411.         printf("MATCHED by allowing an incorrect character\n");
  412. #endif
  413.         return(6);
  414.     }
  415.     if (soundex(word,pattern)) {
  416. #if    TEST 
  417.         printf("MATCHED by using the Soundex algorithm\n");
  418. #endif
  419.         return(7);
  420.     }
  421.     if ((pf474_value = pf474_algorithm(word,pattern)) > THRESHOLD) {
  422. #if    TEST 
  423.         printf("MATCHED (%g) by using PF474 algorithm\n",
  424.             pf474_value);
  425. #endif
  426.         return(8);
  427.     }
  428. /*
  429. **    Matching by gestalt does not seem to be a good way to match in
  430. **    a spell checker type of application. All sort of weird things
  431. **    match that have no relation to the word we are trying to spell
  432. **    However - this seems to be a good method for badly misspelled
  433. **    words. Perhaps a matching by GESTALT with some sort of inteligent
  434. **    weeding out would be a good solution. Also it might be possible
  435. **    that for a minimum length with a high enough percentage threshhold
  436. **    might work for the longer words, BUT what about the shorter ones.
  437. */
  438.     if ((percnt = simil(word,pattern)) > THRESHOLD2) {
  439. #if    TEST
  440.         printf("MATCHED (%g) by using GESTALT algorithm\n",
  441.             percnt);
  442. #endif
  443.         return(9);
  444.     }
  445.     return(0);    /* No MATCH found */
  446. }
  447.  
  448.  
  449. #if    TEST
  450. /*
  451. **    name:        main
  452. **    purpose:    Test algorithms that match
  453. */
  454. int    main(argc,argv)
  455. int    argc;
  456. char    *argv[];
  457. {
  458.     char    save_word[WORD_LENGTH];
  459.     char    save_pattern[WORD_LENGTH];
  460.     char    word[WORD_LENGTH];
  461.     char    pattern[WORD_LENGTH];
  462.     int    result;
  463.  
  464.     printf("Enter the pattern to match against: ");
  465.     fgets(save_pattern,WORD_LENGTH,stdin);
  466.     while (1) {
  467.         printf("\n\nPattern is : %s",save_pattern,pattern);
  468.         printf("Enter word or \"quit\" to quit : ");
  469.         fgets(save_word,WORD_LENGTH,stdin);
  470.         if (strcmp(save_word,"quit\n")==0) break;
  471.         if (strcmp(save_word,"QUIT\n")==0) break;
  472.         strcpy(word,save_word);
  473.         strcpy(pattern,save_pattern);
  474.         result = matches(word,pattern);
  475.         if (result) {
  476.             printf("Matched by algorithm %d\n",result);
  477.             printf("Original pattern : %s",save_pattern);
  478.             printf("Original word    : %s",save_word);
  479.             printf("   Final pattern : %s",pattern);
  480.             printf("   Final word    : %s",word);
  481.         }
  482.         else printf("Couln't match word to pattern\n");
  483.     }
  484.     return(0);
  485. }
  486. #endif
  487.