Character-based correction arrangement with correction propagation

• US 5,761,687 A
• Filed: 10/05/1995
• Issued: 06/02/1998
• Est. Priority Date: 10/04/1995
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Hulteen, Eric A., Beauregard, Gerald T., Hon, Hsiao-Wuen
• Primary Examiner(s): Weinhardt, Robert A.
• Application Number:
  US08/539,342
• Time in Patent Office: 971 Days
• Field of Search: 395/2.49, 395/2.53, 395/2.62-2.66, 395/2.55, 395/759, 704/9, 704/240, 704/244, 704/246, 704/251, 704/257, 707/533, 707/535, 707/531
• US Class Current: 715/271
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

A method of correcting a text in a data processing system is described. The method includes the step of locating a first incorrect character in the text. A character list of alternative characters for the first incorrect character is then shown to the user who replaces the first incorrect character with a correct character from the character list. The change of the first incorrect character is then propagated through a remainder of the text in accordance with a matching score and a language probability score of the remainder of the text with respect to the correct character to correct any subsequent incorrect character in the text.

Claims

1. A method of correcting a text in a data processing system, comprising the steps of:

(A) recognizing an input pattern using a pattern recognition system and locating a first incorrect character which is a portion of a word in the text;

(B) showing to the user a character list of alternative characters for the first incorrect character and allowing the user to select a correct character which is a portion of a word to replace the first incorrect character from the character list, each of said alternative characters being a portion of a word;

(C) propagating a change of the first incorrect character through a remainder of the text in accordance with a matching score and a language probability score of the remainder of the text with respect to the correct character to correct any subsequent incorrect character in the text.

2. The method of claim 1, wherein the step (C) further comprises the steps of

(I) determining if the first incorrect character is a last character of a word of the text;

(II) if the first incorrect character is not the last character of the word, then performing an in-word propagation of the change of the first incorrect character through at least one remaining character of the word in accordance with the matching score and an unigram probability score of the remaining character, and in accordance with a bigram probability score of the remaining character with respect to the correct character.

3. The method of claim 2, wherein the step (C) further comprises the steps of

(III) performing a between-word propagation of the change of the word through the text to change the adjacent word of the word in accordance with the matching score and the unigram probability score of the adjacent word, and a long distance language probability score of the adjacent word with respect to the corrected word.

4. The method of claim 3, wherein the long distance language probability score includes a bigram probability score and a trigram probability score, wherein the matching score includes an acoustic matching score.

5. The method of claim 4, wherein the step (C) further comprises the steps of

(IV) determining if the adjacent word is a last word of the text;

(V) if the adjacent word is the last word of the text, then stopping the between-word propagation;

(VI) if the adjacent word is not the last word of the text, then repeating the steps (III) and (IV).

6. The method of claim 1, wherein the text is a Chinese text that includes a number of words, each being formed by at least one Chinese character.

7. The method of claim 1, wherein the text is an English text that includes a number of words, each being formed by at least one English character/letter.

8. The method of claim 1, wherein the data processing system is a computer system having a text processing user interface.

23. A method as in claim 1 wherein the text is a single word.

24. A method as in claim 1 wherein the text comprises a plurality of words.

9. A method of correcting a text in a data processing system, comprising the steps of:

(A) recognizing an input pattern using a pattern recognition system and locating a first erroneous word of the text that needs to be corrected;

(B) changing a first erroneous character of the first erroneous word with a correct character which is a portion of a word from a character list of alternative characters for the first erroneous character, each of said alternative characters being a portion of a word;

(C) propagating a change of the first erroneous character through the first erroneous word by rearranging a word list of alternative words of the first erroneous word in accordance with the correct character such that a correct word can appear high on the word list to replace the first erroneous word.

10. The method of claim 9, wherein the word list of the first erroneous word initially lists the alternative words of the first erroneous word in accordance with a matching score and a language model probability score with respect to the first erroneous word, wherein the step (C) further comprises the steps of

(a) re-calculating the language model probability score for each of the alternative words of the word list in accordance with the correct character in order to promote the correct word of the first erroneous word from the word list, wherein the language model probability score includes at least one of a unigram probability score and a bigram probability score;

(b) moving the words that contain the correct character in corresponding position and in accordance with the re-calculated language model probability score of each of those words to top of the word list without rearranging remaining alternative words in the word list.

11. The method of claim 10, further comprising the step of

(D) propagating change of the first erroneous word through the text by rearranging the word list of alternative words for each of subsequent words of the first erroneous word in accordance with the correct word of the first erroneous word such that the correct word for each of the subsequent words of the text that need to be corrected can appear high on the respective word list.

12. The method of claim 9, wherein the data processing system is a computer system having a text processing user interface.

13. The method of claim 12, wherein the text is a Chinese text that includes a number of words, each being formed by at least one Chinese character.

14. The method of claim 12, wherein the text is a English text that includes a number of words, each being formed by at least one English character/letter.

15. A method of correcting a text in a data processing system, comprising the steps of:

(A) recognizing an input pattern using a pattern recognition system and locating a first erroneous word of the text that needs to be corrected;

(B) changing the first erroneous word with a correct character which is a portion of a word;

(C) propagating a change of the first erroneous word through the text by rearranging a word list of alternative words for an adjacent erroneous word which is proximate to the first erroneous word in accordance with the correct character such that a correct word for the adjacent erroneous word can appear high on the word list of the adjacent erroneous word.

16. The method of claim 15, wherein the step (C) further comprises the steps of

(I) re-calculating the language model probability score for each of the alternative words of the word list of the adjacent erroneous word in accordance with a unigram probability score of the correct character with respect to the adjacent erroneous word and a long distance language probability score of the correct word of the adjacent erroneous word with respect to a correct word of the first erroneous word.

17. The method of claim 16, wherein the long distance language probability score includes at least one of a bigram probability score and a trigram probability score.

18. The method of claim 17, wherein the step (C) further comprises the steps of

(III) determining if the adjacent erroneous word is a last word of a sentence;

(IV) if the adjacent erroneous word is not the last word of the sentence, then making the adjacent erroneous word as the first erroneous word and repeating the steps of (C)(I) and (C)(II).

19. The method of claim 15, wherein the data processing system is a computer system having a text processing user interface.

20. The method of claim 19, wherein the text is a Chinese text that includes a number of words, each being formed by at least one Chinese character.

21. The method of claim 19, wherein the text is a English text that includes a number of words, each being formed by at least one English character/letter.

22. A method of correcting a text in a data processing system, comprising the steps of:

(A) recognizing an input pattern using a pattern recognition system and locating a first incorrect character which is a portion of a word in the text;

(B) allowing the user to input a correct character which is a portion of a word to replace the first incorrect character;

(C) propagating a change of the first incorrect character through a remainder of the text in accordance with a score of the remainder of the text with respect to the correct character to correct any subsequent incorrect character in the text wherein said score is one of a matching score based upon a viterbi search or a language probability score.

25. A method as in claim 22 wherein the text is a single word.

26. A method as in claim 22 wherein the text comprises a plurality of words.

27. A method of correcting a text in a data processing system, comprising the steps of:

(A) locating a first incorrect character which is a portion of a word in the text;

(B) showing to the user a character list of alternative characters for the first incorrect character and allowing the user to select a correct character which is a portion of a word to replace the first incorrect character from the character list, each of said alternative characters being a portion of a word;

(C) propagating a change of the first incorrect character through a remainder of the text in accordance with a matching score and a language probability score of the remainder of the text with respect to the correct character to correct any subsequent incorrect character in the text.