Abstract
Simple information searches--name lookups, word searches, etc--are often implemented in terms of an exact match criterion. However, given both the diversity of homophonic (pronounced the same) words and names, as well as the propensity for humans to misspell surnames, this simplistic criterion often yields less than desirable results, in the form of reduced result sets, missing records that differ by a misplaced letter or different national spelling.
This article series discusses Lawrence Phillips' Double Metaphone phonetic matching algorithm, and provides several useful implementations which can be employed in a variety of solutions, to create more useful, effective searches of proper names in databases and other collections.
Introduction
This article series discusses the practical use of the Double Metaphone algorithm to phonetically search name data, using the author's implementations written for C++, COM (Visual Basic, etc.), scripting clients (VBScript, JScript, ASP), SQL, and .NET (C#, VB.NET, and any other .NET language). For a discussion of the Double Metaphone algorithm itself, and Phillips' original code, see Phillips' article in the June 2000 CUJ, available here.
Part I introduces Double Metaphone and describes the author's C++ implementation and its use. Part II discusses the use of the author's COM implementation from within Visual Basic. Part III demonstrates use of the COM implementation from ASP and with VBScript. Part IV shows how to perform phonetic matching within SQL Server using the author's extended stored procedure. Part V demonstrates the author's .NET implementation. Finally, Part VI closes with a survey of phonetic matching alternatives, and pointers to other resources.
Background
Part I of this article series discussed the Double Metaphone algorithm, its origin and use, and the author's C++ implementation. While this section summarizes the key information from that article, readers are encouraged to review the entire article, even if the reader has no C++ experience.
The Double Metaphone algorithm, developed by Lawrence Phillips and published in the June 2000 issue of C/C++ Users Journal, is part of a class of algorithms known as "phonetic matching" or "phonetic encoding" algorithms. These algorithms attempt to detect phonetic ("sounds-like") relationships between words. For example, a phonetic matching algorithm should detect a strong phonetic relationship between "Nelson" and "Nilsen", and no phonetic relationship between "Adam" and "Nelson."
Double Metaphone works by producing one or possibly two phonetic keys given a word. These keys represent the "sound" of the word. A typical Double Metaphone key is four characters long, as this tends to produce the ideal balance between specificity and generality of results.
The first, or primary, Double Metaphone key represents the American pronunciation of the source word. All words have a primary Double Metaphone key.
The second, or alternate, Double Metaphone key represents an alternate, national pronunciation. For example, many Polish surnames are "Americanized", yielding two possible pronunciations, the original Polish, and the American. For this reason, Double Metaphone computes alternate keys for some words. Note that the vast majority (very roughly, 90%) of words will not yield an alternate key, but when an alternate is computed, it can be pivotal in matching the word.
To compare two words for phonetic similarity, one computes their respective Double Metaphone keys, and then compares each combination:
- Word 1 Primary - Word 2 Primary
- Word 1 Primary - Word 2 Alternate
- Word 1 Alternate - Word 2 Primary
- Word 1 Alternate - Word 2 Alternate
Obviously if the keys in any of these comparisons are not produced for the given words, the comparisons involving those keys are not performed.
Depending upon which of the above comparisons match, a match strength is computed. If the first comparison matches, the two words have a strong phonetic similarity. If the second or third comparison matches, the two words have a medium phonetic similarity. If the fourth comparison matches, the two words have a minimal phonetic similarity. Depending upon the particular application requirements, one or more match levels may be excluded from match results.
Scripting client implementation
In Part II of this series, a COM implementation of Double Metaphone was discussed, in the context of using the component from within Visual Basic. With slight modifications, the same implementation can be used from VBScript, JScript, or any other scripting language, including VBScript within Active Server Pages (ASP).
Two COM components are provided with the COM implementation of Double Metaphone: MetaphoneCOM.DoubleMetaphoneString, and MetaphoneCOM.DoubleMetaphoneShort. The former produces four-character Metaphone keys in the form of strings, while the latter produces those same keys, represented as integers for efficiency. In cases where performance matters, the integer version is preferable.
Each component exposes a method, ComputeMetaphoneKeys, which takes as parameters the word to compute, and two variables which will receive the keys. For the string version, these two variables are of type String, while the integer version takes the two key variables of type Integer.
The primary difference between Visual Basic and the scripting languages for the purposes of the COM Double Metaphone implementation, is that Visual Basic supports typed variables (String, Integer, Boolean, etc), while the scripting languages are type-less. Therefore, when building the COM implementation of Double Metaphone, two versions of the ComputeMetaphoneKeys method were created: one for COM clients like VB, and another for dispatch clients like VBScript. The version for VB and other compiled clients is ComputeMetaphoneKeys, while the scripting version is ComputeMetaphoneKeysScr. If a scripting language attempts to call ComputeMetaphoneKeys, a Type Mismatch error is raised.
To compute the string Double Metaphone keys for a word in VBScript, code like this would be used:
Dim mphoneString
Dim primaryKey, alternateKey
Dim word
word = "nelson"
Set mphoneString =
CreateObject("MetaphoneCOM.DoubleMetaphoneString")
mphoneString.ComputeMetaphoneKeysScr word, primaryKey,
alternateKey
WScript.Echo "Keys: " & primaryKey & "
" & alternateKey
When placed into a VBS file and executed, the above code produces the following message:
From this is it clear that the word "Nelson" produces a primary Metaphone key of "NLSN", and does not produce an alternate key.
Modifying the above code to use the integer version instead:
Dim mphoneShort
Dim primaryKey, alternateKey
Dim word
word = "nelson"
Set mphoneShort =
CreateObject("MetaphoneCOM.DoubleMetaphoneShort")
mphoneShort.ComputeMetaphoneKeysScr
word, primaryKey, alternateKey
WScript.Echo "Keys: " &
primaryKey & " " & alternateKey
This version yields the following output:
Here, one can see that the integer version of the Metaphone key "NLSN" produced by the previous script is -31064, while the -1 value for the alternate key indicates that, like the previous script, no alternate key was produced for the word "Nelson".
A sample application, VBScript Word Lookup, is included in the source archive associated with this article. This application loads a list of 21,000 names from a text file, computes the Double Metaphone keys for each name, and then fills a Dictionary object mapping phonetic keys with arrays of words. The script then prompts for a name to search, and lists all phonetic matches for that name. Most of the source code deals not with Double Metaphone, but with maintaining this Dictionary of names; however, the script does clearly demonstrate the use of the Double Metaphone components within VBScript.
Active Server Pages & databases
While it may be interesting to build applications like VBScript Word Lookup, they are hardly compelling. This section discusses a very simple Active Server Pages application, which presents a browser-based form prompting for a search term. Once the user submits the request, a list of names from the Access database of 21,000 test names, which phonetically match the search term is displayed to the user. The code is very similar to the VB Word DB Lookup sample from Part II, modified for VBScript and to use the ASP intrinsic objects. Nonetheless, a web-based phonetic search application which matches against a relational database of data, is somewhat less contrived than a script which reads a list of names and interacts via message boxes.
To run this sample, a few installation steps are necessary:
First, create a new virtual directory in IIS on your local machine. Call this virtual directory ASPWordDBLookup (that is not optional; the script assumes it is in that virtual directory), and map this virtual directory to the directory created by the source archive called ASPWordDBLookup.
Second, ensure that the user account IUSR_machine (where machine is the name of the host machine) has Full Control rights on the folder containing namelist.mdb and the ASPWordDBLookup folder.
Finally, navigate to http://localhost/aspworddblookup/search.htm
Enter a name to search, and press "Search":
Since the code for this sample is based largely on the VB Word DB Lookup sample from Part II, see that article for a more detailed discussion of its operation, and the use of Double Metaphone with a relational database such as the one in this sample.
Conclusion
In this article, the use of the Double Metaphone COM implementation from VBScript and ASP has been explored. The relational database searching technique developed in Part II was used with ASP to build a web-based phonetic matching sample application.
If the reader is interested in a further discussion of use of relational databases with Double Metaphone, in particular a more realistic discussion of issues pertaining to real-world applications, move on to Part IV, which introduces the SQL Server extended stored procedure implementation of Double Metaphone. Part V will present the .NET implementation of Double Metaphone, which should also be of interest to ASP.NET programmers, somewhat dissatisfied with this sample. Part VI will conclude with a review of other phonetic matching techniques and links to other resources, and therefore should be read by anyone interested in adding phonetic matching to their applications.
History
- 7-22-03 Initial publication
- 7-31-03 Added hyperlinks between articles in the series
Article Series
