Natural Language Corpus Data - Peter Norvig

57 downloads 203 Views 682KB Size Report
sage with a substitution cipher key (the Python library functions maketrans and ... is replaced by “b” and “b” i
,ch14.14922 Page 219 Thursday, June 25, 2009 2:34 PM

Chapter 14

CHAPTER FOURTEEN

Natural Language Corpus Spell-correct all words in text." return re.sub('[a-zA-Z]+', lambda m: correct(m.group(0)), text) def correct(w): "Return the word that is the most likely spell correction of w." candidates = edits(w).items( ) c, edit = max(candidates, key=lambda (c,e): Pedit(e) * Pw(c)) return c

P(w | c) is computed by Pedit: def Pedit(edit): "The probability of an edit; can be '' or 'a|b' or 'a|b+c|d'." if edit == '': return (1. - p_spell_error) return p_spell_error*product(P1edit(e) for e in edit.split('+')) p_spell_error = 1./20. P1edit = Pdist(datafile('count1edit')) ## Probabilities of single edits

The candidates are generated by edits, which is passed a word, and returns a dict of {word: edit} pairs indicating the possible corrections. In general there will be several edits that arrive at a correction. (For example, we can get from “tel” to “tell” by inserting an “l” after the “e” or after the “l”.) We choose the edit with the highest probability. edits is the most complex function we’ve seen so far. In part this is inherent; it is complicated to generate four kinds of edits. But in part it is because we took some efforts to make edits efficient. (A slower but easier-to-read version is at http://norvig.com/spell-correct.html.) If we considered all edits, a word like “acommodations” would yield 233,166 candidates. But only 11 of these are in the vocabulary. So edits works by precomputing the set of all prefixes of all the words in the vocabulary. It then calls editsR recursively, splitting the word into a head and a tail (hd and tl in the code) and assuring that the head is always in the list of prefixes. The results are collected by adding to the dict results: def edits(word, d=2): "Return a dict of {correct: edit} pairs within d edits of word." results = {} def editsR(hd, tl, d, edits): def ed(L,R): return edits+[R+'|'+L] C = hd+tl if C in Pw: e = '+'.join(edits) if C not in results: results[C] = e else: results[C] = max(results[C], e, key=Pedit) if d =2 and tl[0]!=tl[1] and hd+tl[1] in PREFIXES: editsR(hd+tl[1], tl[0]+tl[2:], d-1, ed(tl[1]+tl[0], tl[0:2])) ## Body of edits: editsR('', word, d, []) return results PREFIXES = set(w[:i] for w in Pw for i in range(len(w) + 1))

Here’s an example of edits: >>> edits('adiabatic', 2) {'adiabatic': '', 'diabetic': '