home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / METAPHON.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  13KB  |  411 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /*
  4. **  METAPHON.C - Phonetic string matching
  5. **
  6. **  The Metaphone algorithm was developed by Lawrence Phillips. Like the
  7. **  Soundex algorithm, it compares words that sound alike but are spelled
  8. **  differently. Metaphone was designed to overcome difficulties encountered
  9. **  with Soundex.
  10. **
  11. **  This implementation was written by Gary A. Parker and originally published
  12. **  in the June/July, 1991 (vol. 5 nr. 4) issue of C Gazette. As published,
  13. **  this code was explicitly placed in the public domain by the author.
  14. */
  15.  
  16. #include <ctype.h>
  17. #include "phonetic.h"
  18.  
  19. /*
  20. **  Character coding array
  21. */
  22.  
  23. static char vsvfn[26] = {
  24.       1,16,4,16,9,2,4,16,9,2,0,2,2,2,1,4,0,2,4,4,1,0,0,0,8,0};
  25. /*    A  B C  D E F G  H I J K L M N O P Q R S T U V W X Y Z      */
  26.  
  27. /*
  28. **  Macros to access the character coding array
  29. */
  30.  
  31. #define vowel(x)  (vsvfn[(x) - 'A'] & 1)  /* AEIOU    */
  32. #define same(x)   (vsvfn[(x) - 'A'] & 2)  /* FJLMNR   */
  33. #define varson(x) (vsvfn[(x) - 'A'] & 4)  /* CGPST    */
  34. #define frontv(x) (vsvfn[(x) - 'A'] & 8)  /* EIY      */
  35. #define noghf(x)  (vsvfn[(x) - 'A'] & 16) /* BDH      */
  36.  
  37. /*
  38. **  metaphone()
  39. **
  40. **  Arguments: 1 - The word to be converted to a metaphone code.
  41. **             2 - A MAXMETAPH+1 char field for the result.
  42. **             3 - Function flag:
  43. **                 If 0: Compute the Metaphone code for the first argument,
  44. **                       then compare it to the Metaphone code passed in
  45. **                       the second argument.
  46. **                 If 1: Compute the Metaphone code for the first argument,
  47. **                       then store the result in the area pointed to by the
  48. **                       second argument.
  49. **
  50. **  Returns: If function code is 0, returns Success_ for a match, else Error_.
  51. **           If function code is 1, returns Success_.
  52. */
  53.  
  54. Boolean_T metaphone(const char *Word, char *Metaph, metaphlag Flag)
  55. {
  56.       char *n, *n_start, *n_end;    /* Pointers to string               */
  57.       char *metaph, *metaph_end;    /* Pointers to metaph               */
  58.       char ntrans[512];             /* Word with uppercase letters      */
  59.       char newm[MAXMETAPH + 4];     /* New metaph for comparison        */
  60.       int KSflag;                   /* State flag for X translation     */
  61.  
  62.       /*
  63.       ** Copy word to internal buffer, dropping non-alphabetic characters
  64.       ** and converting to upper case.
  65.       */
  66.  
  67.       for (n = ntrans + 1, n_end = ntrans + sizeof(ntrans) - 2;
  68.             *Word && n < n_end; ++Word)
  69.       {
  70.             if (isalpha(*Word))
  71.                   *n++ = toupper(*Word);
  72.       }
  73.  
  74.       if (n == ntrans + 1)
  75.             return Error_;           /* Return if zero characters        */
  76.       else  n_end = n;              /* Set end of string pointer        */
  77.  
  78.       /*
  79.       ** Pad with NULs, front and rear
  80.       */
  81.  
  82.       *n++ = NUL;
  83.       *n   = NUL;
  84.       n    = ntrans;
  85.       *n++ = NUL;
  86.  
  87.       /*
  88.       ** If doing comparison, redirect pointers
  89.       */
  90.  
  91.       if (COMPARE == Flag)
  92.       {
  93.             metaph = Metaph;
  94.             Metaph = newm;
  95.       }
  96.  
  97.       /*
  98.       ** Check for PN, KN, GN, WR, WH, and X at start
  99.       */
  100.  
  101.       switch (*n)
  102.       {
  103.       case 'P':
  104.       case 'K':
  105.       case 'G':
  106.             if ('N' == *(n + 1))
  107.                   *n++ = NUL;
  108.             break;
  109.  
  110.       case 'A':
  111.             if ('E' == *(n + 1))
  112.                   *n++ = NUL;
  113.             break;
  114.  
  115.       case 'W':
  116.             if ('R' == *(n + 1))
  117.                   *n++ = NUL;
  118.             else if ('H' == *(n + 1))
  119.             {
  120.                   *(n + 1) = *n;
  121.                   *n++ = NUL;
  122.             }
  123.             break;
  124.  
  125.       case 'X':
  126.             *n = 'S';
  127.             break;
  128.       }
  129.  
  130.       /*
  131.       ** Now loop through the string, stopping at the end of the string
  132.       ** or when the computed Metaphone code is MAXMETAPH characters long.
  133.       */
  134.  
  135.       KSflag = False_;              /* State flag for KStranslation     */
  136.       for (metaph_end = Metaph + MAXMETAPH, n_start = n;
  137.             n <= n_end && Metaph < metaph_end; ++n)
  138.       {
  139.             if (KSflag)
  140.             {
  141.                   KSflag = False_;
  142.                   *Metaph++ = *n;
  143.             }
  144.             else
  145.             {
  146.                   /* Drop duplicates except for CC    */
  147.  
  148.                   if (*(n - 1) == *n && *n != 'C')
  149.                         continue;
  150.  
  151.                   /* Check for F J L M N R  or first letter vowel */
  152.  
  153.                   if (same(*n) || (n == n_start && vowel(*n)))
  154.                         *Metaph++ = *n;
  155.                   else switch (*n)
  156.                   {
  157.                   case 'B':
  158.                         if (n < n_end || *(n - 1) != 'M')
  159.                               *Metaph++ = *n;
  160.                         break;
  161.  
  162.                   case 'C':
  163.                         if (*(n - 1) != 'S' || !frontv(*(n + 1)))
  164.                         {
  165.                               if ('I' == *(n + 1) && 'A' == *(n + 2))
  166.                                     *Metaph++ = 'X';
  167.                               else if (frontv(*(n + 1)))
  168.                                     *Metaph++ = 'S';
  169.                               else if ('H' == *(n + 1))
  170.                                     *Metaph++ = ((n == n_start &&
  171.                                           !vowel(*(n + 2))) ||
  172.                                           'S' == *(n - 1)) ? 'K' : 'X';
  173.                               else  *Metaph++ = 'K';
  174.                         }
  175.                         break;
  176.  
  177.                   case 'D':
  178.                         *Metaph++ = ('G' == *(n + 1) && frontv(*(n + 2))) ?
  179.                               'J' : 'T';
  180.                         break;
  181.  
  182.                   case 'G':
  183.                         if ((*(n + 1) != 'H' || vowel(*(n + 2))) &&
  184.                               (*(n + 1) != 'N' || ((n + 1) < n_end &&
  185.                               (*(n + 2) != 'E' || *(n + 3) != 'D'))) &&
  186.                               (*(n - 1) != 'D' || !frontv(*(n + 1))))
  187.                         {
  188.                               *Metaph++ = (frontv(*(n + 1)) &&
  189.                                     *(n + 2) != 'G') ? 'J' : 'K';
  190.                         }
  191.                         else if ('H' == *(n + 1) && !noghf(*(n - 3)) &&
  192.                               *(n - 4) != 'H')
  193.                         {
  194.                               *Metaph++ = 'F';
  195.                         }
  196.                         break;
  197.  
  198.                   case 'H':
  199.                         if (!varson(*(n - 1)) && (!vowel(*(n - 1)) ||
  200.                               vowel(*(n + 1))))
  201.                         {
  202.                               *Metaph++ = 'H';
  203.                         }
  204.                         break;
  205.  
  206.                   case 'K':
  207.                         if (*(n - 1) != 'C')
  208.                               *Metaph++ = 'K';
  209.                         break;
  210.  
  211.                   case 'P':
  212.                         *Metaph++ = ('H' == *(n + 1)) ? 'F' : 'P';
  213.                         break;
  214.  
  215.                   case 'Q':
  216.                         *Metaph++ = 'K';
  217.                         break;
  218.  
  219.                   case 'S':
  220.                         *Metaph++ = ('H' == *(n + 1) || ('I' == *(n + 1) &&
  221.                               ('O' == *(n + 2) || 'A' == *(n + 2)))) ?
  222.                               'X' : 'S';
  223.                         break;
  224.  
  225.                   case 'T':
  226.                         if ('I' == *(n + 1) && ('O' == *(n + 2) ||
  227.                               'A' == *(n + 2)))
  228.                         {
  229.                               *Metaph++ = 'X';
  230.                         }
  231.                         else if ('H' == *(n + 1))
  232.                               *Metaph++ = 'O';
  233.                         else if (*(n + 1) != 'C' || *(n + 2) != 'H')
  234.                               *Metaph++ = 'T';
  235.                         break;
  236.  
  237.                   case 'V':
  238.                         *Metaph++ = 'F';
  239.                         break;
  240.  
  241.                   case 'W':
  242.                   case 'Y':
  243.                         if (vowel(*(n + 1)))
  244.                               *Metaph++ = *n;
  245.                         break;
  246.  
  247.                   case 'X':
  248.                         if (n == n_start)
  249.                               *Metaph++ = 'S';
  250.                         else
  251.                         {
  252.                               *Metaph++ = 'K';
  253.                               KSflag = True_;
  254.                         }
  255.                         break;
  256.  
  257.                   case 'Z':
  258.                         *Metaph++ = 'S';
  259.                         break;
  260.                   }
  261.             }
  262.  
  263.             /*
  264.             ** Compare new Metaphone code with old
  265.             */
  266.  
  267.             if (COMPARE == Flag &&
  268.                   *(Metaph - 1) != metaph[(Metaph - newm) - 1])
  269.             {
  270.                   return Error_;
  271.             }
  272.       }
  273.  
  274.       /*
  275.       ** If comparing, check if Metaphone codes were equal in length
  276.       */
  277.  
  278.       if (COMPARE == Flag && metaph[Metaph - newm])
  279.             return Error_;
  280.  
  281.       *Metaph = NUL;
  282.       return Success_;
  283. }
  284.  
  285. #ifdef TEST
  286.  
  287. /*
  288. **  Test demo to search a drive for a filename which sounds similar to
  289. **  file names passed on the command line
  290. */
  291.  
  292. #include <stdio.h>
  293. #include <stdlib.h>
  294. #include <string.h>
  295. #include "dirent.h"     /* metaphone() is portable so use Posix   */
  296. #include "filnames.h"   /* valid_fname() prototype                */
  297. #include "snip_str.h"   /* strchcat() prototype                   */
  298.  
  299. /*
  300. **  Prototypes
  301. */
  302.  
  303. void print_find_t(char * dir, DOSFileData *find);
  304. void search(char *dir, char *name);
  305.  
  306. Boolean_T found = False_;
  307. char meta[MAXMETAPH + 4];
  308.  
  309. main(int argc, char *argv[])
  310. {
  311.       char *ptr;
  312.  
  313.       if (2 > argc)
  314.       {
  315.             puts("Usage: METAPHON filename [...filename]");
  316.             return EXIT_FAILURE;
  317.       }
  318.       while (--argc)
  319.       {
  320.             char *fname = *++argv;
  321.  
  322.             if (Success_ != valid_fname(fname, -1))
  323.             {
  324.                   printf("\nIllegal filename: %s\n", fname);
  325.                   continue;
  326.             }
  327.             printf("\nSearching for: %s\n", fname);
  328.  
  329.             /* Remove the extension, if any     */
  330.  
  331.             if (NULL != (ptr = strchr(fname, '.')))
  332.                   *ptr = NUL;
  333.  
  334.             /* Store the Metaphone code         */
  335.  
  336.             metaphone(fname, meta, GENERATE);
  337.             printf("Metaphone for %s is %s\n", fname, meta);
  338.  
  339.             /* Search for matches               */
  340.  
  341.             search("", "");
  342.             if (!found)
  343.                   puts("A match was not found");
  344.       }
  345.       return EXIT_SUCCESS;
  346. }
  347.  
  348. void search(char *dir, char *newdir)
  349. {
  350.       char         curdir[FILENAME_MAX];
  351.       DIR         *dirp;
  352.       DOSFileData *dstruct;
  353.       char        *ptr;
  354.       Boolean_T    retval;
  355.  
  356.       while (NULL != (ptr = strchr(dir, '\\')))
  357.             *ptr = '/';
  358.  
  359.       strcpy(curdir, dir);
  360.  
  361.       if ('/' != LAST_CHAR(curdir))
  362.             strchcat(curdir, '/', FILENAME_MAX);
  363.  
  364.       strcat(curdir, newdir);
  365.  
  366.       if (NULL != (dirp = opendir(curdir)))
  367.       {
  368.             while (NULL != (dstruct = readdir(dirp)))
  369.             {
  370.                   if ('.' == *(ff_name(dstruct)))
  371.                         continue;
  372.                   else
  373.                   {
  374.                         /* Don't look at file extension     */
  375.  
  376.                         if (NULL != (ptr = strchr(ff_name(dstruct), '.')))
  377.                               *ptr = NUL;
  378.                         else  ptr  = NULL;
  379.  
  380.                         retval = metaphone(ff_name(dstruct), meta, COMPARE);
  381.  
  382.                         /* Restore extension, if any        */
  383.  
  384.                         if (ptr != NULL)
  385.                               *ptr = '.';
  386.  
  387.                         if (Success_ == retval)
  388.                               print_find_t(curdir, dstruct);
  389.                   }
  390.                   if (ff_attr(dstruct) & _A_SUBDIR)
  391.                         search(curdir, ff_name(dstruct));
  392.             }
  393.             closedir(dirp);
  394.       }
  395. }
  396.  
  397. void print_find_t(char *dir, DOSFileData *find)
  398. {
  399.       printf("%s/%-12s %8ld %2.2d-%02.2d-%02.2d %c%c%c%c%c\n", dir,
  400.             ff_name(find), ff_size(find), ff_mo(find),
  401.             ff_day(find), (ff_yr(find) + 80) % 100,
  402.             (ff_attr(find) & _A_SUBDIR) ? 'D' : '.',
  403.             (ff_attr(find) & _A_RDONLY) ? 'R' : '.',
  404.             (ff_attr(find) & _A_HIDDEN) ? 'H' : '.',
  405.             (ff_attr(find) & _A_SYSTEM) ? 'S' : '.',
  406.             (ff_attr(find) & _A_ARCH)   ? 'A' : '.');
  407.       found = True_;
  408. }
  409.  
  410. #endif /* TEST */
  411.