Methods and systems for large-scale statistical misspelling correction

• US 8,881,005 B2
• Filed: 04/20/2012
• Issued: 11/04/2014
• Est. Priority Date: 04/20/2012
• Status: Active Grant

• Current Assignee: King Abdul AZIZ City For Science and Technology
• Original Assignee: King Abdul AZIZ City For Science and Technology
• Inventors: Al Badrashiny, Mohammed A., Alghamdi, Mansour M., Alkanhal, Mohamed I., Al-Qabbany, Abdulaziz O.
• Primary Examiner(s): HUYNH, CONG LAC T
• Application Number:
  US13/451,763
• Publication Number:
  US 20130283156A1
• Time in Patent Office: 928 Days
• Field of Search: 715/257
• US Class Current: 715/257
• CPC Class Codes: G06F 40/163 Handling of whitespace
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

Methods and systems for large-scale statistical misspelling correction are provided. A method implemented in a computer infrastructure includes reviewing the input text to detect spelling errors in one or more words and calculating a variable cost distance of letters associated with the one or more words. Furthermore, the method can detect space-deletion errors and space-insertion errors. The method further includes determining a best candidate solution for correcting the spelling errors based on the variable cost distance. The method includes correcting the spelling errors using the best candidate solution.

Claims

1. A method implemented in a computer infrastructure, comprising:

reviewing an input text to detect spelling errors in one or more words by detecting space-deletion errors and space-insertion errors;

calculating a variable cost distance of letters associated with the one or more words;

determining a best candidate solution for correcting the spelling errors based on the variable cost distance; and

correcting the spelling errors using the best candidate solution, wherein;

the detecting space-deletion errors comprises choosing a sequence of letters with a maximum marginal probability via an A* lattice search and m-grams probability estimation; and

the detecting space-insertion errors comprises generating all possible combinations between words in an input phrase.

2. The method of claim 1, wherein the spelling errors include one or more insertions, deletions, substitutions, or transpositions.

3. The method of claim 2, wherein the spelling errors further include hidden semantic errors.

4. The method of claim 1, wherein the calculating the variable cost distance comprises utilizing a Damerau-Levenshtein distance to determine a cost of correcting the spelling errors.

5. The method of claim 4, wherein letters having similar shapes, similar pronunciation, or keyboard proximity are given a low variable cost distance.

6. The method of claim 4, wherein the determining the best candidate solution comprises comparing the spelling errors with all words in a dictionary using the variable cost distance and selecting one or more words having a minimum variable cost distance.

7. The method of claim 6, wherein the determining the best candidate solution further comprises choosing a sequence of words with a maximum marginal probability via an A^* lattice search and m-grams probability estimation.

8. The method of claim 7, wherein the A* lattice search follows a best-first path strategy to select a path through a best candidate trellis, wherein the best-first path strategy is a statistical score of a path until its terminal expansion node.

9. The method of claim 8, wherein the determining the best candidate solution further comprises disambiguating the selected one or more words having a minimum variable cost distance.

10. The method of claim 9, further comprising adding a heuristic score function to the best-first path strategy to expand during the A* lattice search, wherein the heuristic score function stays above a minimum upper bound of a probability estimation.

11. The method of claim 6, further comprising clustering the words in the dictionary to reduce a number of comparisons.

12. The method of claim 1, further comprising:

generating one or more solutions, which include valid words in a dictionary and misspelled words;

analyzing the one or more solutions to correct the misspelled words in the one or more solutions; and

determining a best candidate solution for the misspelled words in the one or more solutions.

13. A computer program product comprising a tangible computer readable storage medium having readable program code embodied in the tangible computer readable storage medium, the computer program product includes at least one component operable to:

review an input text to detect spelling errors in one or more words;

calculate a variable Damerau-Levenshtein cost distance of letters associated with the one or more words;

determine a best candidate solution for correcting the spelling errors based on the variable Damerau-Levenshtein cost distance using an A* lattice search and an m-grams probability estimation; and

correct the spelling errors using the best candidate solution.

14. The computer program product of claim 13, wherein letters having similar shapes, similar pronunciation, or keyboard proximity are given a low variable Damerau-Levenshtein cost distance.

15. The computer program product of claim 14, wherein the determining the best candidate solution comprises comparing the spelling errors with all words in a dictionary using the variable Damerau-Levenshtein cost distance and selecting one or more words having a minimum variable Damerau-Levenshtein cost distance.

16. The computer program product of claim 15, wherein the determining the best candidate solution further comprises:

choosing a sequence of letters with a maximum marginal probability via the A* lattice search and the m-grams probability estimation, wherein;

the A* lattice search follows a best-first path strategy to select a path through a best candidate trellis;

the best-first path strategy is a statistical score of a path until its terminal expansion node; and

a heuristic score function is added to the best-first path strategy to expand during the A* lattice search, wherein, the heuristic score function stays above a minimum upper bound of a probability estimation.

17. The computer program product of claim 16, wherein the determining the best candidate solution further comprises disambiguating the one or more words having a minimum variable cost distance.

18. A computer system for tokenizing multilingual textual documents, the system comprising:

a CPU, a computer readable memory and a tangible computer readable storage media;

first program instructions to review an input text to detect spelling errors in one or more words;

second program instruction to calculate a variable cost distance of letters associated with the one or more words;

third program instructions to determine a best candidate solution for correcting the spelling errors based on the variable cost distance using an A* lattice search and an m-grams probability estimation; and

fourth program instructions to correct the spelling errors using the best candidate solution, wherein;

the first, second, third, and fourth program instructions are stored on the tangible computer readable storage media for execution by the CPU via the computer readable memory;

the calculating the variable cost distance comprises utilizing a Damerau-Levenshtein distance to determine a cost of correcting the spelling errors, wherein letters having similar shapes, similar pronunciation, or keyboard proximity are given a low variable cost distance; and

the determining the best candidate solution comprises comparing the spelling errors with all words in a dictionary using the variable cost distance and selecting one or more words having a minimum variable cost distance.

19. The computer system of claim 18, wherein the determining the best candidate solution further comprises:

disambiguating the one or more words having a minimum variable cost distance;

clustering the words in the dictionary to reduce a number of comparisons; and

choosing a sequence of letters with a maximum marginal probability via the A* lattice search and the m-grams probability estimation.