home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / unix_c / utils / soundex2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-21  |  4.0 KB  |  126 lines
  1. From riacs!eos!agate!violet.berkeley.edu!dean Mon Jan 16 14:11:47 PST 1989
  2.  
  3. Following is an implementation of the Soundex keying routine.  It uses
  4. the first letter and a function of the next few letters of a name to
  5. derive a four-character key.  The algorithm tends to cluster names
  6. which sound similar.  It was originally developed by the Bureau of the
  7. Census to let them find an individual's record even if the name is
  8. slightly misspelled.
  9.  
  10. There was another version on the net, but when I looked at it, the 
  11. implementation seemed excessively arcane.  This routine is reasonably
  12. straightforward, documented, and includes test data for verification.
  13.  
  14. Released to the public domain.  Have fun.
  15.  
  16. -Dean
  17.  
  18. ---- cut (and check for .signature at the end) --- cut --- cut --- cut ---
  19. /* Note: code text edited with a 4-character tab stop.
  20.  *
  21.  * This implementation of the Soundex algorithm is released to the public
  22.  * domain: anyone may use it for any purpose.  See if I care.
  23.  *
  24.  * N. Dean Pentcheff
  25.  * 1/13/89
  26.  * Dept. of Zoology
  27.  * University of California
  28.  * Berkeley, CA  94720
  29.  * dean@violet.berkeley.edu
  30.  *
  31.  * char * soundex( char * )
  32.  *
  33.  * Given as argument: Pointer to a character string.
  34.  * Returns: Pointer to a static string, 4 characters long, plus a terminal
  35.  *    '\0'.  This string is the Soundex key for the argument string.
  36.  * Side effects and limitations:
  37.  *    Does not clobber the string passed in as the argument.
  38.  *    No limit on argument string length.
  39.  *    Assumes a character set with continuously ascending and contiguous
  40.  *       letters within each case and within the digits (e.g. this works for
  41.  *       ASCII and bombs in EBCDIC.  But then, most things do.).
  42.  * Reference: Adapted from Knuth, D.E. (1973) The art of computer programming;
  43.  *    Volume 3: Sorting and searching.  Addison-Wesley Publishing Company:
  44.  *    Reading, Mass. Page 392.
  45.  * Special cases:
  46.  *    Leading or embedded spaces, numerals, or punctuation are squeezed out
  47.  *       before encoding begins.
  48.  *    Null strings or those with no encodable letters return the code 'Z000'.
  49.  * Test data from Knuth (1973):
  50.  *    Euler   Gauss   Hilbert Knuth   Lloyd   Lukasiewicz
  51.  *    E460    G200    H416    K530    L300    L222
  52.  */
  53.  
  54. #include    <string.h>
  55. #include    <ctype.h>
  56.  
  57. char *
  58. soundex(in)
  59.     char    *in;
  60. {
  61.     static    int code[] =
  62.         {  0,1,2,3,0,1,2,0,0,2,2,4,5,5,0,1,2,6,2,3,0,1,0,2,0,2 };
  63.         /* 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 */
  64.     static    char key[5];
  65.     register    char ch;
  66.     register    int last;
  67.     register    int count;
  68.  
  69.     /* Set up default key, complete with trailing '0's */
  70.     key[0] = 'Z';
  71.     key[1] = key[2] = key[3] = '0';
  72.     key[4] = '\0';
  73.  
  74.     /* Advance to the first letter.  If none present, return default key */
  75.     while (*in != '\0'  &&  !isalpha(*in))
  76.         ++in;
  77.     if (*in == '\0')
  78.         return(key);
  79.  
  80.     /* Pull out the first letter, uppercase it, and set up for main loop */
  81.     key[0] = islower(*in) ? toupper(*in) : *in;
  82.     last = code[key[0] - 'A'];
  83.     ++in;
  84.  
  85.     /* Scan rest of string, stop at end of string or when the key is full */
  86.     for (count = 1;  count < 4  &&  *in != '\0';  ++in) {
  87.         /* If non-alpha, ignore the character altogether */
  88.         if (isalpha(*in)) {
  89.             ch = isupper(*in) ? tolower(*in) : *in;
  90.             /* Fold together adjacent letters sharing the same code */
  91.             if (last != code[ch - 'a']) {
  92.                 last = code[ch - 'a'];
  93.                 /* Ignore code==0 letters except as separators */
  94.                 if (last != 0)
  95.                     key[count++] = '0' + last;
  96.             }
  97.         }
  98.     }
  99.  
  100.     return(key);
  101. }
  102.  
  103. #ifdef    TESTPROG
  104. /*
  105.  * If compiled with -DTESTPROG, main() will print back the key for each
  106.  * line from stdin.
  107.  */
  108. #include    <stdio.h>
  109. void
  110. main()
  111. {
  112.     char    instring[80];
  113.  
  114.     while (fgets(instring, 79, stdin) != (char *)NULL)
  115.         printf("%s\n", soundex(instring));
  116. }
  117. #endif    TESTPROG
  118.  
  119. Dean Pentcheff        dean@violet.berkeley.edu
  120. ----------------------------------------------
  121. As an adolescent I aspired to lasting fame, I craved factual certainty, and I
  122. thirsted for a meaningful vision of human life - so I became a scientist.  This
  123. is like becoming an archbishop so you can meet girls.               M. Cartmill
  124.  
  125.  
  126.