• Some Observations:
  • Many applications need to compare pieces of text
  • Users often don't know how things are spelled (e.g., "Bernstein" or "Burnstein?") or how they should be described (e.g., "1 Duke Plaza" or "One Duke Plaza")
• Possible Resolutions:
  • Find things that "sound alike"
  • Handle numbers in many ways
  • Ignore small differences (e.g., transposed letters)
• In Practice:
  • More matches are often better than fewer (especially in a GUI-based application in which users can be offered a choice)

• History:
  • Developed by Odell and Russel (for the U.S. Census Bureau) in the 1870s to search for names
  • Many "versions" exist; we will use the version sanctioned by the National Archives
• Concepts:
  • Ignore (non-initial) vowels
  • Create phonetic groups
  • Eliminate repeating sounds
  • Create a 4-digit code

• Phoentic Groups:
  • A,E,I,O,U,H,W,Y (Removed)
  • B,F,P,V (1)
  • C,G,J,K,Q,S,X,Z (2)
  • D,T (3)
  • L (4)
  • M,N (5)
  • R (6)
• Rules:
  • Always use the first letter
  • Remove duplicate soundex codes
  • If a vowel (A, E, I, O, U) separates two consonants that have the same soundex code, the consonant to the right of the vowel is coded
  • If "H" or "W" separate two consonants that have the same soundex code, the consonant to the right of the vowel is not coded
  • Truncate to four characters (pad with '0' if less than four characters)

A Simple Implementation

javaexamples/strings/Soundex.java

/**
 * A utility class that implements the Soundex algorithm
 * for finding strings that sound the same
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 1.0
 */
public class Soundex
{

    /**
     * Construct a 4-character Soundex code from a String
     *
     * @param s   The String to convert
     * @return    The Soundex code
     */
    public static String toCode(String s)
    {
        char       c;
        char[]     code = {'0','0','0','0'};
        char[]     chars, coded, noDups, noHW, noVowels, source;
        int        i, index, n, start;


        // Create a character array
        chars = s.toUpperCase().toCharArray();


        // Remove non alphabetic characters
        source = new char[chars.length];        
        index = 0;
        for (i=0; i<chars.length; i++)
        {
           if ((chars[i] < 'A') || (chars[i] > 'Z'))
           {
              // Remove
           }
           else
           {
              source[index] = chars[i];
              index++;
           }
        }
        

        // Code the consonants
        coded = new char[index];
        for (i=0; i<coded.length; i++) {

            c = source[i];
            if       ((c=='B') || (c=='P') || (c=='F') || 
                      (c=='V')                            )   coded[i]='1';

            else if  ((c=='C') || (c=='S') || (c=='K') || 
                      (c=='G') || (c=='J') || (c=='Q') || 
                      (c=='X') || (c=='Z')                )   coded[i]='2';

            else if  ((c=='D') || (c=='T') )                  coded[i]='3';

            else if  ((c=='L'))                               coded[i]='4';

            else if  ((c=='M') || (c=='N') )                  coded[i]='5';

            else if  ((c=='R'))                               coded[i]='6';
            else                                              coded[i]=c;
            
        }


        // Remove H and W  (except if the first letter)
        noHW    = new char[coded.length];
        noHW[0] = coded[0];
        index   = 1;
        for (i=1; i<coded.length; i++)
        {
            if ((coded[i] == 'H') || (coded[i] == 'W'))
            {
               // Remove
            }
            else
            {
                noHW[index] = coded[i];
                index++;
            }
        }
        

        // Remove duplicates
        noDups    = new char[index];
        noDups[0] = noHW[0];
        index     = 1;        
        for (i=1; i<noDups.length; i++)
        {
            if (noHW[i] == noDups[index-1])
            {
                // Duplicate
            }
            else
            {
                noDups[index] = noHW[i];
                index++;
            }
        }


        // Remove the vowels (except if the first letter) and non-alphabetic
        noVowels    = new char[index];
        noVowels[0] = noDups[0];
        index       = 1;
        for (i=1; i<noVowels.length; i++) {

           if ((noDups[i]=='A') || (noDups[i]=='E') || (noDups[i]=='I') ||
               (noDups[i]=='O') || (noDups[i]=='U') || (noDups[i]=='Y')      )
            {
               // Remove
            }
            else
            {
                noVowels[index] = noDups[i];
                index++;
            }
        }


        // Construct the final code
        code[0] = source[0];
        n = code.length;
        if (index < n) n = index;
        for (i=1; i<n; i++) code[i] = noVowels[i];




        return new String(code);
    }







}
        

• Observations:
  • Soundex was developed when computing power was very limited
  • It is possible to use more (language-specific, dialect-specific) phonetic knowledge
• Some Existing Algorithms:
  • Metaphone
  • Double Metaphone

• Getting Started:
  • Convert to upper case
• Some Phonetic Rules (In Order):
  • ght becomes t
  • gh and ph become f
  • gn becomes n
  • ch and sh becomes x
  • ci, ce, cy become s
  • z becomes s
  • c becomes k
  • q becomes k
  • dg becomes j
  • g becomes j
  • wr becomes r
• Finishing:
  • Remove vowels
  • Remove repeated consonants

• Jaro Measure:
  • Part of UNIMATCH record linkage system for the U.S. Census (1976)
  • The weighted sum of percentage of matched characters from each string (including transposed characters)
• Ratcliff-Obershelp Measure:
  • Part of a pattern matching algorithm (1988)
  • The number of matching characters divided by the total number of characters in the two strings (where the matching characters are those in the longest common subsequence plus the matching characters on either side of the subsequence)
• Levenshtein Distance:
  • The smallest number of insertions, deletions, and substitutions required to change one string into another

• Absolute Numbers:
  • "1" and "one", "2" and "two", etc...
• Relative Numbers:
  • "1st" and "first", "2nd" and "second", "3rd" and "third", "4th" and "fourth", etc...
  • "1st" and "1", etc... (e.g., for streets)

• An Observation:
  • More likely to be a problem for small numbers (e.g., "521" and "five hundred twenty one" are not interchanged often)
• A Simple Algorithm:
  • Use a hash table with multiple keys for the same value (e.g., "1st", "1 st", "1" and "first" are all keys for "1st")

• Transportation Domain:
  • Interchangeability of "Interstate 81", "I81", "Route 81"
• Geographic Domain:
  • Interchangeability of "N" and "North"