NLP: A frequency-based spelling corrector

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 distance with 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 and word: no suggestion for 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

Example 1 · Input
5
the 500
ten 40
tea 30
cat 20
sat 25
Teh cat sta
Expected output
the cat sat
teh -> the (1)
sta -> sat (1)
Example 2 · Input
3
apple 10
apply 10
ample 3
appel xyzzy apple
Expected output
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)

Lesson: Edit distance and spelling correction →