Soundex matching

Various forms of matching are used in various contexts in computer systems when searching for information. One particularly specialised kind of matching is soundex matching which attempts to match two names on the basis of their phonetic quality. The names might have quite different spellings and yet sound similar when spoken.

The soundex matching algorithm was invented by Donald Knuth although the soundex method itself was originally developed by Margaret K. Odell and Robert C. Russell who hold U.S. patents on the method from 1918 and 1922. This algorithm is useful to help telephone operators search for the name of a person in a directory even if they or the caller cannot spell the name of the person exactly. Similarly, automated directory systems such as the Edinburgh University Email Directory use soundex matching. The soundex algorithm proceeds by ignoring vowels and compressing double letters so that `ll' becomes `l' and `rr' becomes `r' and so forth. The first letter remaining is then chosen to begin the soundex code for the name and three digits are computed from the rest of the name using a table which assigns the same numeric value to similar-sounding letters.

Thus the soundex algorithm will match `Gilmore', `Gillmore' and `Gilmour' but it sometimes fails to match names which should be matched, for example `Rogers' and `Rodgers' and `Tchebysheff' and `Chebyshev' remain unmatched one with the other. Against this some significant differences can be recognised: the names `Dijkstra' and `Daxter' have the same soundex code. At present Soundex is one of the most widely used computer-based methods to address the problem of matching names phonetically; another method is Metaphone.

In Volume 3 of `The Art of Computer Programming', Donald Knuth describes his algorithm for the method in this way:

1. Retain the first letter of the name, and drop all occurrences of a, e, h, i, o, u, w, y in other positions.
2. Assign the following numbers to the remaining letters after the first:
   1. b, f, p, v;
   2. c, g, j, k, q, s, x, z;
   3. d, t;
   4. l;
   5. m, n;
   6. r.
3. If two or more letters with the same code were adjacent in the original name (before step 1), omit all but the first.
4. Convert to the form ``letter, digit, digit, digit'' by adding trailing zeros (if there are less than three digits), or by dropping rightmost digits (if there are more than three).