Basically we are looking for setting up a capability to undertake phonetic name search operations. The most popular and old algorithm used for phonetic search is soundex. The Soundex algorithm essentially encodes an input character string into a four digit alphanumeric representation. The first digit is a alphabet and the rest are numerals. The alphabet of the soundex code is the first alphabet of the input word. This is a key limitation as we cannot match a character sequence that forms a subset of the complete encoded word. This limitation was overcome by an improved algorithm called Metaphone which was further enhanced by the Double Metaphone algorithm.
The Commons Codec framework provides ready-to-use classes for Soundex, Metaphone and Double Metaphone algorithm. There is also a refined soundex available however this post will restrict itself to discussing only Soundex, Metaphone and Double Metaphone.
public interface Algorithm {
public void processPhrase(String word);
public PhraseMatchResults findMatchingPhrases(String word);
}
Now let’s provide concrete implementations for the three algorithms.
********************************* SoundEx ****************************
class SoundEx implements Algorithm {
public void processPhrase(String word) {
Soundex algo = new Soundex();
String encodedValue = algo.soundex(word);
NameIndexer.addWordIndex(encodedValue, word);
}
public PhraseMatchResults findMatchingPhrases(String word) {
Soundex algo = new Soundex();
String value = algo.soundex(word);
return searchIndexer(word, value);
}
private PhraseMatchResults searchIndexer(String word, String value) {
List<String> partialMatches = NameIndexer.getSoundExCodeMatches(value);
PhraseMatchResults results = new PhraseMatchResults();
results.setAlgoName(PhraseMatchResults.ALGO_SOUNDEX);
results.setKey(word);
if (partialMatches != null) {
//Check if the phrase is present
for (Iterator<String> matchItr = partialMatches.iterator(); matchItr.hasNext();) {
String result = matchItr.next();
if (result.contains(word) || result.startsWith(word)) {
results.addExactMatch(result);
} else {
results.addNearMatch(result);
}
}
}
//Loop thru all valid combinations for e.g. if the encoded value is A123
//Loop thru from A100 to A199.
for(int i=0; i<10; i++) {
StringBuilder soundExString = new StringBuilder();
soundExString.append(getFirstAlphabet(value));
soundExString.append(getFirstDigit(value));
soundExString.append("0");
soundExString.append(i);
String searchValue = soundExString.toString();
if (value != searchValue) {
partialMatches = NameIndexer.getSoundExCodeMatches(searchValue);
//System.out.println("Code: " + searchValue + " " + partialMatches);
if (partialMatches != null) {
//Check if the phrase is present
for (Iterator<String> matchItr = partialMatches.iterator();
matchItr.hasNext();) {
String result = matchItr.next();
if (result.contains(word) || result.startsWith(word)) {
results.addExactMatch(result);
} else {
results.addNearMatch(result);
}
}
}
}
}
for(int i=10; i<100; i++) {
StringBuilder soundExString = new StringBuilder();
soundExString.append(getFirstAlphabet(value));
soundExString.append(getFirstDigit(value));
soundExString.append(i);
String searchValue = soundExString.toString();
if (value != searchValue) {
partialMatches = NameIndexer.getSoundExCodeMatches(searchValue);
//System.out.println("Code: " + searchValue + " " + partialMatches);
if (partialMatches != null) {
//Check if the phrase is present
for (Iterator<String> matchItr = partialMatches.iterator(); matchItr.hasNext();) {
String result = matchItr.next();
if (result.contains(word)) {
results.addExactMatch(result);
} else {
results.addNearMatch(result);
}
}
}
}
}
return results;
}
private static String getFirstAlphabet(String word) {
return word.substring(0, 1);
}
private static String getSecondAlphabetFromWord(String word) {
return word.substring(1, 2).toUpperCase();
}
private static String getFirstDigit(String word) {
return word.substring(1, 2);
}
private static String getSecondDigit(String word) {
return word.substring(2, 3);
}
private static String getLastDigit(String word) {
return word.substring(3);
}
}
********************************* End of SoundEx *******************
Now let’s understand what SoundEx class is doing. The processPhrase method’s sole responsibility to convert a word into its Soundex encoded value and store into a lookup map with the encoded value as key. For our tutorial purposes I have a list of around 2500 odd indian names which I am indexing on startup to serve the purpose of lookup data. If I pass a word say “Robert” to the method it would convert the word into its Soundex encoding value “R163”. As discussed earlier the first character of the code is the first alphabetic character of the word, in this case R. If we have a word changed to say “1Robert”, the encoded value returned is 6163 and the value is consistent for any other numeric or special character. This encoding strategy of Soundex acts as a major impediment is phonetic matching. Suppose mistypes LIZABETH instead of ELIZABETH. Soundex would not be able to identify the two as similar or matching phrases.
The second and the larger portion of the code is to match a search phrase to suitable exact or partial matches. This is achieved by the findMatchingPhrases method implementation. The method implementation does the following: converts the search phrase into its soundex encoded value, checks for a encoded value match in the indexer. If there exists a match the records are retrieved, the matching phrases are cross verified with the search phrase to check if the search phrase has a character to character match with the results. If not the results are treated as nearmatches. The additional thing I have done is to get a more substantial data set, I have put in additional logic to retrieve words around the encoded search value. Basically VINAY’s encoded value is V500, I have further enhanced the search by allowing V501 to V599 to be considered in the additional search results. This is purely from a completeness stand point, the result set data can be near match or completely off.
For ready understanding please find below the PhraseMatchResults and relevant code snippets of NameIndexer class.
******************** PhraseMatchResults ************************************
public class PhraseMatchResults {
public static final String ALGO_SOUNDEX = "SOUNDEX";
public static final String ALGO_METAPHONE = "METAPHONE";
public static final String ALGO_DOUBLEMETAPHONE = "DOUBLEMETAPHONE";
public class PhraseMatchResults {
public static final String ALGO_SOUNDEX = "SOUNDEX";
public static final String ALGO_METAPHONE = "METAPHONE";
public static final String ALGO_DOUBLEMETAPHONE = "DOUBLEMETAPHONE";
private static final int LEVENSHTEIN_DIST = 5;
private static final float SIMILARITY_DIST = .6f;
private Set<String> exactMatches = new HashSet<String>();
private Set<String> nearMatches = new HashSet<String>();
private String key = null;
private String algoName = null;
public String getAlgoName() {
return algoName;
}
public void setAlgoName(String algoName) {
this.algoName = algoName;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public void addExactMatch(String word) {
this.exactMatches.add(word);
}
public void addNearMatch(String word) {
if (withinJWRange(word)) {
this.nearMatches.add(word);
}
}
private boolean withinLDRange(String word) {
int dist = StringUtils.getLevenshteinDistance(word, this.key);
if (dist > LEVENSHTEIN_DIST) {
return Boolean.FALSE;
}
return Boolean.TRUE;
}
private boolean withinJWRange(String word) {
float dist = new JaroWinkler().getSimilarity(word, this.key);
//System.out.println("Word: " + word + " Dist: " + dist);
if (dist > SIMILARITY_DIST) {
return Boolean.TRUE;
}
return Boolean.FALSE;
}
public void addNearMatch(List<String> words) {
this.nearMatches.addAll(words);
}
public void addExactMatch(List<String> words) {
this.exactMatches.addAll(words);
}
public List<String> getExactMatches() {
return sortExactSet();
}
public List<String> getNearMatches() {
return sortNearSet();
}
private List<String> sortExactSet() {
List<String> exactMatchList = new ArrayList<String>();
exactMatchList.addAll(exactMatches);
SortComparator comp = new SortComparator();
comp.setKey(this.key);
Collections.sort(exactMatchList, comp);
return exactMatchList;
}
private List<String> sortNearSet() {
List<String> nearMatchList = new ArrayList<String>();
nearMatchList.addAll(nearMatches);
JaroWinklerDistanceComparator comp = new JaroWinklerDistanceComparator();
comp.setKey(this.key);
Collections.sort(nearMatchList, comp);
return nearMatchList;
}
class SortComparator implements Comparator<String> {
private String key = null;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public int compare(String o1, String o2) {
int index1 = o1.indexOf(key);
int index2 = o2.indexOf(key);
if(index1 >=0 && index2 >=0) {
if (index1 == index2) {
return 0;
}
if (index1 > index2) {
return 1;
}
if (index1 < index2) {
return -1;
}
}
if (index1 >=0 && index2 < 0) {
return -1;
}
if (index1 <0 && index2 >= 0) {
return 1;
}
return -1;
}
}
class LevensteinDistanceComparator implements Comparator<String> {
private String key = null;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public int compare(String o1, String o2) {
int dist1 = StringUtils.getLevenshteinDistance(key, o1);
int dist2 = StringUtils.getLevenshteinDistance(key, o2);
if(dist1 >=0 && dist2 >=0) {
if (dist1 == dist2) {
return 0;
}
if (dist1 > dist2) {
return 1;
}
if (dist1 < dist2) {
return -1;
}
}
return 1;
}
}
class JaroWinklerDistanceComparator implements Comparator<String> {
private String key = null;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public int compare(String o1, String o2) {
JaroWinkler algo = new JaroWinkler();
float fdist1 = algo.getSimilarity(key, o1);
float fdist2 = algo.getSimilarity(key, o2);
int dist1 = (int)fdist1;
int dist2 = (int)fdist2;
if(dist1 >=0 && dist2 >=0) {
if (dist1 == dist2) {
return 0;
}
if (dist1 > dist2) {
return 1;
}
if (dist1 < dist2) {
return -1;
}
}
return 1;
}
}
}
********************************** End of PhraseMatchResults ***************
************************ Start of NameIndexer ******************************
public class NameIndexer {
private static Map<String, ArrayList>String>> wordIndex = new HashMap<String, ArrayList<String>>();
private static Algorithm[] algo = { new SoundEx(), new MetaPhone(), new DoubleMetaPhone()};
private NameIndexer() {
}
static void indexName(String name) {
if (name == null) {
return;
}
name = name.toUpperCase();
for (int i = 0; i <; algo.length; i++) {
Algorithm algorithm = algo[i];
algorithm.processPhrase(name);
}
}
static void printIndex() {
System.out.println(wordIndex);
}
static void addWordIndex(String index, String word) {
ArrayList<String> words = wordIndex.get(index);
if (words != null) {
words.add(word);
} else {
ArrayList<String> wordList = new ArrayList<String>();
wordList.add(word);
wordIndex.put(index, wordList);
}
}
static List<String> getSoundExCodeMatches(String soundExCode) {
return wordIndex.get(soundExCode);
}
public static List<PhraseMatchResults> findMatchingPhrases(String word) {
if (word == null) {
return new ArrayList<PhraseMatchResults>();
}
word = word.toUpperCase();
List<PhraseMatchResults> results = new ArrayList<PhraseMatchResults>();
for (int i = 0; i < algo.length; i++) {
Algorithm algorithm = algo[i];
results.add(algorithm.findMatchingPhrases(word));
}
return results;
}
}
************ End of NameIndexer*******************************************************
Now let’s take the soundex algorithm for a test drive. I key in phrase “VINAY” and get a response back specifying VINAY and VINAYAK as the exact matches. I am not too concerned about the near matches at the moment. The exact match response is in line with my expectations. Now let’s test the boundary conditions. I put in the search phrase as “LIZ”. Here I expect a match to be found for LIZ and ELIZABETH, but the response only provides LIZ. Soundex cannot determine that ELIZABETH also fits the search profile.
One other thing, to limit the probable near match results, I have applied tried out two algorithms one is the Levenstein Distance and the Jaro Winkler Distance. These algorithms provide two different mathematical approaches for identifying similarities between two strings. I used the Jaro Winkler algorithm to check for string similarity between the near match results and the search phrase. For Levenstein, I set the acceptable limit as 5 and for Jaro Winkler .6f. I implemented two custom Comparators to sort the nearMatch results on the basis of these two algorithms so that the results would appear appropriately to the end user. Ready to use Levenshtein distance implementation is available in the Commons lang project and Jaro Winker is available at URL. The best algorithm for string similiarity matching as per the authors of the Simmetrics project is TF-IDF, unfortunately I could not get a handle on any open source implementation for this algorithm, therefore used Jaro-Winkler. Inspite of all the efforts, I have to say the near match results are not satisfactory.
Moving on, once it was obvious that soundex was inadequate to cover my requirements, I tried out the Metaphone and DoubleMetaphone algorithms. Below are the class implementations and code snippets of NameIndexer relevant to the two algorithms.
*********************** Start MetaPhone ************************
public class MetaPhone implements Algorithm {
public void processPhrase(String word) {
String metaPhoneValue = new Metaphone().metaphone(word);
NameIndexer.addMetaIndex(metaPhoneValue, word);
}
public PhraseMatchResults findMatchingPhrases(String word) {
String metaPhoneValue = new Metaphone().metaphone(word);
PhraseMatchResults results = new PhraseMatchResults();
results.setAlgoName(PhraseMatchResults.ALGO_METAPHONE);
results.setKey(word);
Set<String> indexes = NameIndexer.getMetaIndices();
for (Iterator<String> values = indexes.iterator(); values.hasNext();) {
String code = values.next();
if (code.contains(metaPhoneValue) ||
code.startsWith(metaPhoneValue)) {
List<String> words = NameIndexer.getMetaPhoneMatches(code);
for (Iterator<String> wrds = words.iterator(); wrds.hasNext();) {
String phrase = wrds.next();
if ( phrase.startsWith(word) ||
phrase.contains(word)) {
results.addExactMatch(phrase);
continue;
} else {
results.addNearMatch(phrase);
}
}
//results.addExactMatch(words);
}
}
return results;
}
}
************************ End MetaPhone***************************************************
************************ Start DoubleMetaPhone *****************************************
public class DoubleMetaPhone implements Algorithm {
public void processPhrase(String word) {
DoubleMetaphone dMetaPhone = new DoubleMetaphone();
String encodedValue = dMetaPhone.doubleMetaphone(word);
NameIndexer.addDMetaIndex(encodedValue, word);
}
public PhraseMatchResults findMatchingPhrases(String word) {
String metaPhoneValue = new DoubleMetaphone().doubleMetaphone(word);
PhraseMatchResults results = new PhraseMatchResults();
results.setAlgoName(PhraseMatchResults.ALGO_DOUBLEMETAPHONE);
results.setKey(word);
Set<String> indexes = NameIndexer.getDMetaIndices();
for (Iterator<String> values = indexes.iterator(); values.hasNext();) {
String code = values.next();
if (code.contains(metaPhoneValue) ||
code.startsWith(metaPhoneValue)) {
List<String> words = NameIndexer.getDoubleMetaPhoneMatches(code);
for (Iterator<String> wrds = words.iterator(); wrds.hasNext();) {
String phrase = wrds.next();
if ( phrase.startsWith(word) ||
phrase.contains(word)) {
results.addExactMatch(phrase);
continue;
} else {
results.addNearMatch(phrase);
}
}
//results.addExactMatch(words);
}
}
return results;
}
}
****************************** Start NameIndexer *************************************************
public class NameIndexer {
private static Map<String, ArrayList>String>> metaIndex = new HashMap<String, ArrayList<String>>
private static Map<String, ArrayList<String>> doubleMetaIndex = new HashMap<String, ArrayList<String>>();
static void addDMetaIndex(String index, String word) {
ArrayList<String> words = doubleMetaIndex.get(index);
if (words != null) {
words.add(word);
} else {
ArrayList<String> wordList = new ArrayList<String>();
wordList.add(word);
doubleMetaIndex.put(index, wordList);
}
}
static void addMetaIndex(String index, String word) {
ArrayList<String> words = metaIndex.get(index);
if (words != null) {
words.add(word);
} else {
ArrayList<String> wordList = new ArrayList<String>();
wordList.add(word);
metaIndex.put(index, wordList);
}
}
static Set<String> getMetaIndices() {
return metaIndex.keySet();
}
static Set<String> getDMetaIndices() {
return doubleMetaIndex.keySet();
}
static List<String> getMetaPhoneMatches(String metaPhoneCode) {
return metaIndex.get(metaPhoneCode);
}
static List<String> getDoubleMetaPhoneMatches(String metaPhoneCode) {
return doubleMetaIndex.get(metaPhoneCode);
}
}
****************************** End NameIndexer ****************************************
OK, now let’s see how these two perform against the same test case. Input VINAY generates VINAY and VINAYAK in all the three algorithms. For the second test case, I input LIZ and get LIZ back in soundex but the metaphone and double metaphone returns back LIZ and ELIZABETH. I key in poor and get back POORNA and POORNACHANDRA in soundex, the metaphones additional provide APOORVA. Note the near match results also throws APURVA for the metaphones.
***************************** Start NameFileReader *******************************
public class NameFileReader {
public NameFileReader() {
}
public void loadNames() {
InputStream ipStream = NameFileReader.class.getResourceAsStream("Names.xls");
try {
HSSFWorkbook workBook = new HSSFWorkbook(ipStream);
HSSFSheet workSheet = workBook.getSheet("Boys");
if (workSheet != null) {
for(short i=2; i<2503; i++) {
HSSFRow row = workSheet.getRow(i);
//System.out.println("Row:" + i);
HSSFCell cell = row.getCell((short)1);
String name = cell.getStringCellValue();
NameIndexer.indexName(name);
}
System.out.println("Processing names xls complete.");
//NameIndexer.printIndex();
promptUser();
} else {
throw new NullPointerException("WorkSheet not Found!");
}
} catch (IOException e) {
e.printStackTrace();
}
}
public void promptUser() {
Scanner scanner = new Scanner(System.in);
System.out.print("Please input your phrase: ");
String phrase = scanner.nextLine();
List<PhraseMatchResults> topResults = NameIndexer.findMatchingPhrases(phrase);
for (Iterator<PhraseMatchResults> iterator = topResults.iterator(); iterator.hasNext();) {
PhraseMatchResults results = iterator.next();
System.out.println("*********** ALGORITHM: " + results.getAlgoName());
System.out.println("Exact match words are: ");
for (Iterator<String> phrases = results.getExactMatches().iterator(); phrases.hasNext();) {
String word = phrases.next();
System.out.println(word);
}
System.out.println("Near match words are: ");
for (Iterator<String> phrases = results.getNearMatches().iterator(); phrases.hasNext();) {
String word = phrases.next();
System.out.println(word);
}
System.out.println("*********** END ALGORITHM *****************");
}
PhraseMatchResults soundExResults = topResults.get(0);
PhraseMatchResults metaPhoneResults = topResults.get(1);
PhraseMatchResults dMetaPhoneResults = topResults.get(2);
//Comparison
System.out.println("&&&&&&&&&&& EXACT ANALYSIS &&&&&&&&&&&&");
Collection unionCol = CollectionUtils.union(soundExResults.getExactMatches(), metaPhoneResults.getExactMatches());
System.out.println(unionCol);
Collection interCol = CollectionUtils.intersection(soundExResults.getExactMatches(), metaPhoneResults.getExactMatches());
System.out.println(interCol);
System.out.println("&&&&&&&&&&& NEAR ANALYSIS &&&&&&&&&&&");
Collection unionColn = CollectionUtils.union(soundExResults.getNearMatches(), metaPhoneResults.getNearMatches());
//System.out.println(unionColn);
Collection interColn = CollectionUtils.intersection(soundExResults.getNearMatches(), metaPhoneResults.getNearMatches());
//System.out.println(interColn);
System.out.println("#######METAPHONE BETTER THAN SOUNDEX???#######");
System.out.println("MetaPhone result set has all: " + metaPhoneResults.getExactMatches().containsAll(soundExResults.getExactMatches()));
System.out.println("MetaPhone Near result set has all: " + metaPhoneResults.getNearMatches().containsAll(soundExResults.getNearMatches()));
System.out.println("Whats missing in SOUNDEX near matches?");
System.out.println(CollectionUtils.subtract(unionColn, soundExResults.getNearMatches()));
System.out.println("Whats missing in METAPHONE near matches?");
System.out.println(CollectionUtils.subtract(unionColn, metaPhoneResults.getNearMatches()));
System.out.println("####### DOUBLEMETAPHONE BETTER THAN METAPHONE???#######");
System.out.println("DMetaPhone result set has all: " + dMetaPhoneResults.getExactMatches().containsAll(metaPhoneResults.getExactMatches()));
System.out.println("DMetaPhone Near result set has all: " + dMetaPhoneResults.getNearMatches().containsAll(metaPhoneResults.getNearMatches()));
Collection unionDColn = CollectionUtils.union(dMetaPhoneResults.getNearMatches(), metaPhoneResults.getNearMatches());
//System.out.println(unionColn);
Collection interDColn = CollectionUtils.intersection(dMetaPhoneResults.getNearMatches(), metaPhoneResults.getNearMatches());
//System.out.println(interColn);
System.out.println("Whats missing in METAPHONE near matches?");
System.out.println(CollectionUtils.subtract(unionDColn, metaPhoneResults.getNearMatches()));
System.out.println("Whats missing in DOUBLEMETAPHONE near matches?");
System.out.println(CollectionUtils.subtract(unionDColn, dMetaPhoneResults.getNearMatches()));
}
public static void main(String args[]) {
NameFileReader reader = new NameFileReader();
reader.loadNames();
}
}
******************************* End NameFileReader *****************
The class above merely reads a excel having around 2500 names, indexes them for each of the algorithms and allows user to supply a search phrase to query for a match. Additionally I have done some comparisons around the result sets generated by the individual algorithm.
Here’s a summary of the various projects I used for testing:
Commons Codec – 1.4
Commons Collection – 2.1
Commons Lang – 1.0.1
POI – 3.0
Simmetrics – 1.6.2
So do I have any recommendations? I would definitely go to Metaphone or DoubleMetaphone for phonetic search requirements. I am not concerned around the exact matches, however there is still considerable work required in the near match areas to achieve a better and closer result set. Probably would need the assistance of a mathematician to figure that out.
My Experiments with Technology 
Thanks, good work….
Hi Thanks for the very very useful info. Can you please share the code with the test data by that we can also play around. thanks
Can you please share the code with real time data so that we can evaluate it’s working.
Great stuff, thanks for Sharing.
Thanks!
I am working on data matching algorithms for seeding the UID nos. in various databases. Your algorithms should be very useful. Could you share the code? The names are in Hindi.
I am working on data migration Project in various databases. Your algorithms should be very useful for my project. Could you share the code?
Sorry, Suresh I do not have the source code any more. The inline source code in the blog post is the only reference available.
Your algorithms should be very useful for my project. Could you share names are in english
Your algorithms should be very useful for my project. Could you share names are in english