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

• US 20050257147A1
• Filed: 07/15/2005
• Published: 11/17/2005
• Est. Priority Date: 03/31/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brill, Eric D., Moore, Robert C.
• Granted Patent: US 7,366,983 B2
• Time in Patent Office: Days
• 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. A method comprising:

receiving an entered string; and

determining how likely a word was to have been entered as the string based on partitioning the word w and the string s and computing probabilities for various partitionings to determine a highest likelihood of at least one edit operation that converts a first character sequence of arbitrary length in the word to a second character sequence of arbitrary length in the string.

2. The method as recited in claim 1, further comprising determining how likely the word is to have been generated.

3. The method as recited in claim 1, further comprising conditioning an edit operation that changes the string into the word on at least one of the probabilities.

4. The method as recited in claim 1, further comprising identifying the string as potentially incorrect.

5. The method as recited in claim 1, further comprising correcting the string to the word.

6. A computer readable medium having computer-executable instructions that, when executed on a processor, perform the method as recited in claim 1.

7. A program embodied on a computer readable medium, which when executed, directs a computer to perform spell checking, including:

a source model component of the program to determine how likely a word w in a dictionary is to have been generated; and

an error model component of the program to determine how likely the word w was to have been incorrectly entered as the string s based on arbitrary length string-to-string transformations, wherein the error model partitions the word w and the string s and computes probabilities for various partitionings.

8. A program embodied on a computer readable medium as recited in claim 7, wherein the string-to-string transformations involve converting a first character sequence of a first length into a second character sequence of a second length that is different than the first length.

9. A program embodied on a computer readable medium as recited in claim 7, wherein the string-to-string transformations involve converting a first character sequence with multiple characters into a second character sequence with multiple characters.

10. A program embodied on a computer readable medium as recited in claim 7, wherein the string-to-string transformations involve converting a first character sequence having a first number of multiple characters into a second character sequence having a second number of multiple characters that is different from the first number of multiple characters.