Natural Language Processing · TEE · formulas

Spelling correction and edit distance

Application calculations

Formulas explained through full worked examples

Spelling correction proposes the intended word or sentence when the observed text contains an error. A non-word error produces an invalid vocabulary item (“recieve”); a real-word error produces an existing word in the wrong context (“I will meat you”). Dictionary lookup can detect many non-words but cannot reliably detect real-word errors.

Detect suspicious text

Generate candidates

Score edit + context fit

Choose correction

Minimum edit distance

Levenshtein distance is the minimum total cost of insertions, deletions and substitutions needed to transform one string into another. In the examples below, each edit costs 1; matching characters cost 0. Transposition is not a single Levenshtein operation. State different costs explicitly if the question gives them.

D(i,j)=\min\begin{cases}D(i-1,j)+1\\D(i,j-1)+1\\D(i-1,j-1)+[a_i\ne b_j]\end{cases}

Rows represent prefixes of the source; columns represent prefixes of the target. D(i,j) is the best cost for transforming the first i source characters to the first j target characters. Initialise D(i,0)=i and D(0,j)=j. The three choices are deletion, insertion and diagonal match/substitution.

Example 1 · cat → cut

Calculate the unit-cost Levenshtein distance from “cat” to “cut”. Show the dynamic-programming table.

Given

Source=cat; target=cut; insertion=deletion=substitution=1; match=0.

To find

Minimum edit cost.

Formula and why it applies

D(i,j)=\min(D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+c)

c = 0 for matching characters, 1 otherwise. Compare all three possible ways to reach each cell.

Solution

Step 1. Initialise empty prefixes

First row counts insertions; first column counts deletions.

Step 2. Fill row 1: source character “c”

D(1,1)=\min(1+1,\ 1+1,\ 0+0)=0

D(1,2)=\min(2+1,\ 0+1,\ 1+1)=1

D(1,3)=\min(3+1,\ 1+1,\ 2+1)=2

Step 3. Fill row 2: source character “a”

D(2,1)=\min(0+1,\ 2+1,\ 1+1)=1

D(2,2)=\min(1+1,\ 1+1,\ 0+1)=1

D(2,3)=\min(2+1,\ 1+1,\ 1+1)=2

Step 4. Fill row 3: source character “t”

D(3,1)=\min(1+1,\ 3+1,\ 2+1)=2

D(3,2)=\min(1+1,\ 2+1,\ 1+1)=2

D(3,3)=\min(2+1,\ 2+1,\ 1+0)=1

Step 5. Read the completed matrix

Source / target	∅	c	u	t
∅	0	1	2	3
c	1	0	1	2
a	2	1	1	2
t	3	2	2	1

Minimum edit distance = 1.

Example 2 · at → cat

Calculate the unit-cost Levenshtein distance from “at” to “cat”. Show the dynamic-programming table.

Given

Source=at; target=cat; insertion=deletion=substitution=1; match=0.

To find

Minimum edit cost.

Formula and why it applies

D(i,j)=\min(D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+c)

c = 0 for matching characters, 1 otherwise. Compare all three possible ways to reach each cell.

Solution

Step 1. Initialise empty prefixes

First row counts insertions; first column counts deletions.

Step 2. Fill row 1: source character “a”

D(1,1)=\min(1+1,\ 1+1,\ 0+1)=1

D(1,2)=\min(2+1,\ 1+1,\ 1+0)=1

D(1,3)=\min(3+1,\ 1+1,\ 2+1)=2

Step 3. Fill row 2: source character “t”

D(2,1)=\min(1+1,\ 2+1,\ 1+1)=2

D(2,2)=\min(1+1,\ 2+1,\ 1+1)=2

D(2,3)=\min(2+1,\ 2+1,\ 1+0)=1

Step 4. Read the completed matrix

Source / target	∅	c	a	t
∅	0	1	2	3
a	1	1	1	2
t	2	2	2	1

Minimum edit distance = 1.

Example 3 · cats → cat

Calculate the unit-cost Levenshtein distance from “cats” to “cat”. Show the dynamic-programming table.

Given

Source=cats; target=cat; insertion=deletion=substitution=1; match=0.

To find

Minimum edit cost.

Formula and why it applies

D(i,j)=\min(D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+c)

c = 0 for matching characters, 1 otherwise. Compare all three possible ways to reach each cell.

Solution

Step 1. Initialise empty prefixes

First row counts insertions; first column counts deletions.

Step 2. Fill row 1: source character “c”

D(1,1)=\min(1+1,\ 1+1,\ 0+0)=0

D(1,2)=\min(2+1,\ 0+1,\ 1+1)=1

D(1,3)=\min(3+1,\ 1+1,\ 2+1)=2

Step 3. Fill row 2: source character “a”

D(2,1)=\min(0+1,\ 2+1,\ 1+1)=1

D(2,2)=\min(1+1,\ 1+1,\ 0+0)=0

D(2,3)=\min(2+1,\ 0+1,\ 1+1)=1

Step 4. Fill row 3: source character “t”

D(3,1)=\min(1+1,\ 3+1,\ 2+1)=2

D(3,2)=\min(0+1,\ 2+1,\ 1+1)=1

D(3,3)=\min(1+1,\ 1+1,\ 0+0)=0

Step 5. Fill row 4: source character “s”

D(4,1)=\min(2+1,\ 4+1,\ 3+1)=3

D(4,2)=\min(1+1,\ 3+1,\ 2+1)=2

D(4,3)=\min(0+1,\ 2+1,\ 1+1)=1

Step 6. Read the completed matrix

Source / target	∅	c	a	t
∅	0	1	2	3
c	1	0	1	2
a	2	1	0	1
t	3	2	1	0
s	4	3	2	1

Minimum edit distance = 1.

Noisy-channel correction

\hat w=\arg\max_w P(x\mid w)P(w)

x is the observed misspelling and w a candidate intended word. P(x | w) is the error-model likelihood; P(w) is the language-model prior. In context, replace the isolated-word prior with an appropriate contextual probability. A frequent word with a plausible typo may beat a rarer candidate, but context can reverse the ranking.

Candidate ranking

For observed “teh”, candidate “the” has prior 0.05 and error likelihood 0.02. Candidate “ten” has prior 0.01 and likelihood 0.01. Select the intended word.

Given

Two candidates and their prior/error-model likelihoods are supplied.

To find

Largest noisy-channel score.

Formula and why it applies

s(w)=P(x\mid w)P(w)

Multiply likelihood by prior; the same evidence normaliser is irrelevant to ranking.

Solution

Step 1. Score the

s(\text{the})=0.02\times0.05=0.001

Step 2. Score ten

s(\text{ten})=0.01\times0.01=0.0001

Step 3. Compare

0.001 is ten times 0.0001.

Choose “the”.