Spell checker with arbitrary length string-to-string transformations to improve noisy channel spelling correction

• US 7,290,209 B2
• Filed: 07/15/2005
• Issued: 10/30/2007
• Est. Priority Date: 03/31/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Moore, Robert, Brill, Eric
• Primary Examiner(s): Hong; Stephen
• Assistant Examiner(s): Stork; Kyle R
• Application Number:
  US11/182,388
• Publication Number:
  US 20050251744A1
• Time in Patent Office: 837 Days
• Field of Search: 715/513, 715/517, 715/523, 715/530, 715/533
• US Class Current: 715/257
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G10L 15/183 using context dependencies, e.g. language models

Abstract

A spell checker based on the noisy channel model has a source model and an error model. The source model determines how likely a word w in a dictionary is to have been generated. The error model determines how likely the word w was to have been incorrectly entered as the string s (e.g., mistyped or incorrectly interpreted by a speech recognition system) according to the probabilities of string-to-string edits. The string-to-string edits allow conversion of one arbitrary length character sequence to another arbitrary length character sequence.

Claims

1. An apparatus, comprising:

a computing processor;

an electronic memory coupled with the computing processor;

an input device to receive an entered string s, and

a program in the memory for execution on the computing processor to determine a probability P(s|w) expressing how likely a word w was to have been incorrectly entered as the string s, by partitioning the word w and the string s into different numbers of segments that define varying lengths of character sequences and computing probabilities for various partitionings, as follows;

$P<br><br>\left(s❘<br><br>w\right)=\underset{R\in <br><br>\mathrm{Part}<br><br>\left(w\right)}{\sum <br><br>}<br><br>P<br><br>\left(R❘<br><br>w\right)<br><br>\underset{\underset{<br><br>T<br><br>=<br><br>R<br><br>}{T\in <br><br>\mathrm{Part}<br><br>\left(s\right)}}{\sum <br><br>}<br><br>\underset{i=1}{\overset{<br><br>R<br><br>}{\prod <br><br>}}<br><br>P<br><br>\left(T_i❘<br><br>R_i\right)$

where Part(w) is a set of possible ways of partitioning the word w, Part(s) is a set of possible ways of partitioning the string s, R is a particular partition of the word w, and T is a particular partition of the string s.

2. The apparatus as recited in claim 1, wherein the program determines how likely the word w is to have been generated.

3. The apparatus as recited in claim 1, wherein the program corrects the string s to the word w.

4. The apparatus as recited in claim 1, wherein the program identifies the string s as potentially incorrect.

5. The apparatus as recited in claim 1, further comprising a training program:

to determine, given a <

wrong, right>

training pair and multiple single character edits that convert characters in one of the right or wrong strings to characters in the other of the right or wrong strings at differing costs, an alignment of the wrong string and the right string that results is a least cost to convert the characters,

to collapse contiguous non-match edits into one or more common error regions, each error region containing one or more characters that can be converted to one or more other characters using a substitution edit, and

to compute a probability for each substitution edit.

6. The apparatus as recited in claim 5, wherein the training program assigns a cost of 0 to match edits and a cost of 1 to non-match edits.

7. The apparatus as recited in claim 6, wherein the single character edits comprises insertion, deletion, and substitution.

8. The apparatus as recited in claim 1, wherein the training program collects multiple <

wrong, right >

training pairs from online resources.

9. The apparatus as recited in claim 1, wherein the training program expands each of the error regions to capture at least one character on at least one side of the error region.

10. A system, comprising:

means for receiving an entered string s, and

an input device to receive an entered string s, and

means for determining a probability P(s|w) expressing how likely a word w was to have been incorrectly entered as the string s, by partitioning the word w and the string s into different numbers of segments that define varying lengths of character sequences and computing probabilities for various partitonings, as follows;

$P<br><br>\left(s❘<br><br>w\right)=\underset{R\in <br><br>\mathrm{Part}<br><br>\left(w\right)}{\sum <br><br>}<br><br>P<br><br>\left(R❘<br><br>w\right)<br><br>\underset{\underset{<br><br>T<br><br>=<br><br>R<br><br>}{T\in <br><br>\mathrm{Part}<br><br>\left(s\right)}}{\sum <br><br>}<br><br>\underset{i=1}{\overset{<br><br>R<br><br>}{\prod <br><br>}}<br><br>P<br><br>\left(T_i❘<br><br>R_i\right)$

where Part(w) is a set of possible ways of partitioning the word w, Part(s) is a set of possible ways of partitioning the string s, R is a particular partition of the word w, and T is a particular partition of the string.