Implement Phonetic ("Sounds-like") Name Searches with Double Metaphone Part I: Introduction & C++ Implementation

// WordLookupSample.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "..\MetaphoneLib\DoubleMetaphone.h"

#include <fstream>
#include <iostream>

#include <map> 
#include <set>
#include <string>

#define METAPHONE_KEY_LENGTH 	4

using namespace std;

typedef std::multimap<string, string> WordMapType;
typedef std::set<string> WordListType;

void phoneticMatch(WordMapType& words, const string& searchWord, WordListType& matchingWord);
int computeMatchLevel(const string& searchWord, const string& candidateWord);

int _tmain(int argc, _TCHAR* argv[])
{
	//Attempt to open the list of names
	ifstream file;
	
	file.open("..\\namelist.txt");
	if (file.fail()) {
		cout << "Unable to open ..\\namelist.txt" << endl;
		return -1;
	}
	
	//Read the contents of the file
	//Each line is a word
	WordMapType wordMap;
	DoubleMetaphone<METAPHONE_KEY_LENGTH> mphone;
	char line[100];
	while (!file.eof()) {
		//Read a word from the file
		file.getline(line, 100);
		
		//Compute the metaphone keys for the word
		mphone.computeKeys(line);
		
		//Add a string object containing the word to the map,
		//with the primary and alternate metaphone keys as map keys
		string word = line;
		wordMap.insert(WordMapType::value_type(string(mphone.getPrimaryKey()), 
											   word));
		if (mphone.getAlternateKey() != NULL) {
			wordMap.insert(WordMapType::value_type(string(mphone.getAlternateKey()), 
												   word));
		}
	}
	file.close();
	
	//wordMap is populated.  Enter the loop that performs searches
	string searchWord;
	
	while (1) {
		cout << "Enter word to search (q to quit): ";
		cin >> searchWord;
		
		if (searchWord.compare("q") == 0) {
			break;
		}
		
		//Declare a set to contain the matches
		WordListType matchingWords;
		
		//Perform the search
		phoneticMatch(wordMap, searchWord, matchingWords);
		
		//Display the results
		for (WordListType::iterator iter = matchingWords.begin();
			  iter != matchingWords.end();
			  iter++) {
			cout << "\tFound: " << (*iter).c_str();
			
			//Display and compute the match level
			cout << " (Match level: " << computeMatchLevel(searchWord, (*iter)) << ")" << endl;
		}
		matchingWords.clear();
	}
}

void phoneticMatch(WordMapType& words, const string& searchWord, WordListType& matchingWords) {
	DoubleMetaphone<METAPHONE_KEY_LENGTH> searchKey(searchWord.c_str());
	string search1 = searchKey.getPrimaryKey();
	cout << "Searching for [" << searchWord.c_str() << "]" << endl;
	
	for (WordMapType::iterator iter = words.lower_bound(search1);
		  iter != words.upper_bound(search1);
		  iter++) {
		matchingWords.insert((*iter).second);
	}
	if (searchKey.getAlternateKey() != NULL) {
		string search2 = searchKey.getAlternateKey();
		for (WordMapType::iterator iter = words.lower_bound(search2);
			  iter != words.upper_bound(search2);
			  iter++) {
			matchingWords.insert((*iter).second);
		}
	}
}

int computeMatchLevel(const string& searchWord, const string& candidateWord) {
	DoubleMetaphone<METAPHONE_KEY_LENGTH> searchWordMphone(searchWord.c_str());
	DoubleMetaphone<METAPHONE_KEY_LENGTH> candidateWordMphone(candidateWord.c_str());
	
	if (strcmp(searchWordMphone.getPrimaryKey(), 
			   candidateWordMphone.getPrimaryKey()) == 0) {
		//Primary-Primary match, that's level 1 (strongest)
		return 1;
	}
	
	if (searchWordMphone.getAlternateKey() != NULL) {
		if (strcmp(searchWordMphone.getAlternateKey(), 
				   candidateWordMphone.getPrimaryKey()) == 0) {
			//Alternate-Primary match, that's level 2 (normal)
			return 2;
		} 
	}
	
	if (candidateWordMphone.getAlternateKey() != NULL) {
		if (strcmp(searchWordMphone.getPrimaryKey(), 
				   candidateWordMphone.getAlternateKey()) == 0) {
			//Primary-Alternate match, that's level 2 (normal)
			return 2;
		} 
	}
	
	if (searchWordMphone.getAlternateKey() != NULL &&
		candidateWordMphone.getAlternateKey() != NULL) {
		if (strcmp(searchWordMphone.getAlternateKey(), 
				   candidateWordMphone.getAlternateKey()) == 0) {
			//Alternate-Alternate match, that's level 3 (minimal)
			return 3;
		} 
	}

	return 0;
}