Correct the spelling of a sentence with a dictionary of word frequencies.
What to build
A program that replaces unknown words with the closest, most frequent dictionary word.
Requirements
- Distance is edit distance with insertions, deletions, substitutions and swaps of two neighbouring characters, each costing 1 (the lesson's
distancewith swaps). - Lowercase the sentence. A dictionary word is kept. For any other word, choose the dictionary word with the smallest distance, then the highest count, then alphabetically first; if that distance is at most 2 use it, otherwise keep the word and add
?to it. - Print the corrected sentence. Then, in order, print
word -> correction (d)for each corrected word andword: no suggestionfor each word left with?.
Input
Line 1: n. Then n lines word count. Last line: the sentence.
Output
The sentence, then one line per unknown word.
Constraints
n ≤ 500; the sentence has at most 50 words of at most 20 letters.
Example
Input:
5
the 500
ten 40
tea 30
cat 20
sat 25
Teh cat sta
Output:
the cat sat
teh -> the (1)
sta -> sat (1)
Why it works
Small edit distances cover most typos, and among equally close candidates the more common word is more likely to be the one intended, which is the noisy channel idea with a frequency prior.
Examples
5 the 500 ten 40 tea 30 cat 20 sat 25 Teh cat sta
the cat sat teh -> the (1) sta -> sat (1)
3 apple 10 apply 10 ample 3 appel xyzzy apple
apple xyzzy? apple appel -> apple (1) xyzzy: no suggestion
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Use the edit distance with adjacent swaps from the lesson's example (it keeps the row two steps back).
Hint 2
`min(counts, key=lambda w: (distance(word, w), -counts[w], w))` picks the closest word, then the most frequent, then the alphabetically first.
Solution
Show one correct solution (try it yourself first)
def distance(a, b):
older, prev = None, list(range(len(b) + 1))
for i in range(1, len(a) + 1):
cur = [i]
for j in range(1, len(b) + 1):
cost = 0 if a[i - 1] == b[j - 1] else 1
d = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost)
if i > 1 and j > 1 and a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]:
d = min(d, older[j - 2] + 1)
cur.append(d)
older, prev = prev, cur
return prev[-1]
counts = {}
for _ in range(int(input())):
word, c = input().split()
counts[word] = int(c)
out, notes = [], []
for word in input().lower().split():
if word in counts:
out.append(word)
continue
best = min(counts, key=lambda w: (distance(word, w), -counts[w], w))
d = distance(word, best)
if d <= 2:
out.append(best)
notes.append(f"{word} -> {best} ({d})")
else:
out.append(word + "?")
notes.append(f"{word}: no suggestion")
print(" ".join(out))
for note in notes:
print(note)