"""scenario: online word processorUsual causes of typing error are an inability to spell, or a tendency tomake typing mistakes. In the first case, the user is likely to try tosound things out, and write the word like it sounds. For instance, hemight spell "vehicle" as "wheeckle". Here, it would be useful to have anidea of how similar words sound phonetically. Conveniently, there aremany phonetic algorithms like Soundex or Metaphone that map words intophonetic classes.In the second case, the user's mechanical error is the source of theproblem. Here, it is likely that the user will miss a key, or hit thewrong key on the keyboard, or hit two keys at once. In this situation,it is useful to use the notion of edit distance to compare how close inspelling two words are. The standard measure of Levenshtein distanceonly includes insertions, deletions and replacements to a string. To improve hit results, it may be useful to know how often words areused. To suggest one word among many that are of equal phonetic andwritten distance to the query, we choose the most common one.Since this is an online word processor, we can use the fact that manyhits are being made to the engine and cache queries, so that repeatedqueries don't need to be recomputed.TODO: 1. Add a fourth operation, swap, so that ed('teh', 'the') = 1 """MAX_WORD_ED = 5MAX_SOUND_ED = 2class SpellChecker: def __init__(self, vocab_file_name): # the vocabulary of the spell checker self.vocab = {} # cache every query made, and store the best match self.queries = {} self._parse_vocab(vocab_file_name) def _parse_vocab(self, file_name): """ Reads in word list and word frequency from a file and also maps each word to a phonetic class """ vocab_file = file(file_name, 'r') line = vocab_file.readline() while line: tokens = line.split() # expecting a specific frequency list format if len(tokens) != 4: continue word = tokens[1].lower() self.vocab[word] = { 'sound': phonetic(word), 'count': tokens[0]} line = vocab_file.readline() def closest_word(self, query): """ Determine the best word match for a given query """ query = query.lower() # normalize query # is this query a real word? if query in self.vocab: return query # has this word been queried before? if query in self.queries: return self.queries[query] # first find all words that sound alike soundalike = [word for word in self.vocab if edit_distance_decision(phonetic(query), self.vocab[word]['sound'], MAX_SOUND_ED)] # then find which of these are spelled similarly for ed in range(2,MAX_WORD_ED): spellalike = [word for word in soundalike if edit_distance_decision(query, word, ed)] if spellalike: break if spellalike: spellalike.sort(self.freq_sorter) best_match = spellalike[0] # hash the query so that repeat queries can be immediately answered self.queries[query] = best_match return best_match # otherwise, we found nothing return None def freq_sorter(self, s,t): """ Sort the results by most popular word """ if self.vocab[s]['count'] == self.vocab[t]['count']: return 0 elif self.vocab[s]['count'] < self.vocab[t]['count']: return -1 return 1def edit_distance_decision(s, t, threshold): """ Decision problem can be simplified dramatically, since we only care about the banded matrix with band width equal to threshold. Returns true if edit_distance(str1, str2) < threshold """ m = len(s) n = len(t) # since |m - n| >= ed(s,t), we can eliminate a lot of possibilities if abs(m - n) >= threshold: return False size = min(m,n) # create a banded matrix with bandwidth = threshold + 1, since we want # to also include large values on the outermost diagonals band = [[0] * (size+1) for d in range((threshold+1)*2 + 1)] # have the threshold + 1 bands must be set to the threshold band[-threshold - 1] = [threshold for e in range(size+1)] band[ threshold + 1] = [threshold for e in range(size+1)] # populate the band matrix with initial data for i in range(-threshold, threshold + 1): band[i][0] = abs(i) # iterate through the elements for e in range(size): emin = threshold # then iterate through the diagonals, starting with main diagonal # and expanding outwards for d in (range(threshold+1) + range(-1,-threshold-1,-1)): (i,j) = table_coords(d,e) if i >= m or j >= n: continue if s[i] == t[j]: cost = 0 else: cost = 1 # doing table lookups in a banded matrix is tricky. top = band[d+1][(e+1, e)[d >= 0]] left = band[d-1][(e+1, e)[d <= 0]] corner = band[d][e] value = min(left + 1, top + 1, corner + cost) band[d][e+1] = value # keep track of the minimal entry for each e emin = min(emin,value) # if this minimal value is above the threshold, then the end # result must be as well if emin >= threshold: return False return Truedef table_coords(d, e): """ Convert from band matrix representation into a regular table """ if d == 0: i = e; j = e elif d > 0: i = e + d; j = e else: i = e; j = e - d return (i,j)def phonetic(s): """ A mapping of words into phonetic representation. simplified Soundex using the following rules: 'aeiouyhw' -> 0, 'bfpv' -> 1, 'cgjkqsxz' -> 2, 'dt' -> 3, 'l' -> 4, 'mn' -> 5, 'r' -> 6 """ from string import maketrans import re # apply a translation table that maps each letter into a phonetic # equivalence class p = s[0] + s[1:].lower().translate(maketrans( 'abcdefghijklmnopqrstuvwxyz', '01230120022455012623010202') ) p = re.sub(r'(.)\1+', r'\1', p, re.DOTALL) # remove the vowels and soundless consonants p = p.replace('0', '') # pad with enough zeroes p = p + '0' * 3 # we only care about the first four digits return p[:4]