Tame the Beast by Matching Similar Strings - The Soundex Algorithm
(Page 4 of 7 )
The Soundex algorithm is an attempt to match strings that sound alike. The idea is that you take the two strings of the comparison, map each of them to a new string that represents their phonetics, and then compare those strings for an exact match. The algorithm is only intended to work with English pronunciation, and there are plenty of counter-examples, even in English, where it doesn’t work. However, it is easy to implement and, even better, is already available as a pre-programmed function in the Oracle Database Management System. There’s also a good chance that you are able to find an implementation in your favorite programming language by a quick web search.
The algorithm works as follows. When mapping the original strings to their phonetic strings, the first letter is always retained, and the rest of the string is processed in a left to right fashion. The subsequent letters of the string are compressed to a three digit code according to the scheme shown in Table 1. Since the first letter is always retained, the algorithm always generates a 4 digit string. The code ‘0’ is used as padding if there are not enough letters in the input string, and any excess letters are disregarded.
| Letter | Phonetic Code |
| B,F,P,V | 1 |
| C,G,J,K,Q,S,X,Z | 2 |
| D,T | 3 |
| L | 4 |
| M,N | 5 |
| R | 6 |
| A,E,I,O,U,Y,H,W | not coded |
Table 1: Phonetic Codes in the Soundex Algorithm
For example, the strings ‘LICENCE’, ‘LICENSE’ and ‘LICENSING’ all map to the same Soundex string, ‘L252’. Additionally,
- adjacent pairs of the same consonant are treated as one
- adjacent consonants from the same code group are treated as one
- a consonant immediately following an initial letter from the same code group is ignored
- consonants from the same code group separated by W or H are treated as one
The Soundex algorithm is interesting because it addresses the pronunciation of words, rather than raw lexical similarity. Its main drawbacks are that it is language dependent, and there are many examples of similar strings that nevertheless produce different Soundex codes. And of course it only provides for comparisons of alphabetic characters - anything outside of the range ‘A’-‘Z’ will simply be ignored.
The Soundex algorithm is also very old (it is documented in Donald Knuth’s “The Art of Computer Programming", from 1973, but attributed to 1918 and 1922 U.S. Patents by Margaret K. Odell and Robert C. Russell). A more recent attempt at the same problem, called MetaPhone, dates from 1990 and allegedly gives better results. There is a description of MetaPhone on the web, and you can also test the algorithm online against databases of names and place names.
Next: Similarity Ranking Methods >>
More Development Cycles Articles
More By Simon White
/ 26 
