Method and apparatus for detecting error strings in a text

• US 5,715,469 A
• Filed: 07/11/1994
• Issued: 02/03/1998
• Est. Priority Date: 07/12/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Arning, Andreas
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/273,295
• Time in Patent Office: 1,303 Days
• Field of Search: 364/419.12, 364/419.13, 364/419.14, 364/419.1, 364/419.15, 364/419.16, 395/600, 395/795, 395/803, 395/793, 434/167, 434/169
• US Class Current: 715/210
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

A system for checking the spelling of words and character strings without the need for a stored dictionary of words and the memory required thereby. The system selects an error-free string and modifies it according to one or more rules which change the error-free string to a possible error string. The rules creating the possible error string can modify the error-free string by predictable character manipulation to yield usual and common errors of the character string. The frequency of occurrence of both the error and error-free strings within the text are determined. These frequencies are compared to each other and, based upon the comparison, the system decides whether the possible error string is an actual error string. The system can use modifying rules which are psychological or technically related to the computer system or operator, and rules which correspond to errors common with specialized input methods, such as character and speech recognition.

Claims

1. A method for detecting an error string F_i in a text using a computer system, the steps of the method comprising:

storing an error-free string S_i in the computer system,

modifying the error-free string S_i in accordance with a stored rule R_j, to generate a possible error string f_ij,

storing the possible error string f_ij in the computer system,

determining the frequency H(S_i) of the corresponding error-free string S_i in said text,

determining the frequency H(f_ij) of the string f_ij in said text,

comparing the frequencies H(f_ij) and H(S_i), using the formula Φ

_ij H(f_ij), H(S_i))=α

_ij, and

deciding, based upon the step of comparing α

_ij with a threshold value β

, whether the possible error string f_ij is an actual error string F_i.

8. A method for detecting and/or correcting error strings F_i in a text, including the steps of claim 2 and further including:

a) determining the frequencies H(Z_i) of different strings Z_i in the text and defining those strings Z_i having a frequency H(Z_i) exceeding a threshold value δ

are defined as error-free strings _Si,

b) detecting an error string F_i associated with an error-free string S_i in accordance with the method of claim 1.

9. A method including the steps of claim 8 further including the steps of sorting and storing strings Z_i with their corresponding frequencies H(Z_i) in the computer system and conducting a search of the sorted strings Z_i to determine the frequency H(f_ij).

10. A method including the steps of claim 9, wherein the step of storing of the strings Z_i with their corresponding frequencies H(Z_i) includes using a one of the methods chosen from a hashing method or a tree structure.

11. A method including the steps of claim 8, further including the step of calculating the corresponding values α

_ij for various possible error strings f_ij of various error-free strings S_i, and replacing those possible error strings f_ij that are error strings F_i.

12. A method including the steps of claim 11, further including the steps of

a) sorting the various possible error strings f_ij according to their corresponding values α

_ij, and

b) changing a threshold value for the values α

_ij such that only those possible error strings f_ij determined to be actual error strings are used whose value α

_ij satisfies the threshold value β

.

2. A method for detecting and/or correcting an error string F_i in a text using a computer system, the steps of the method comprising

storing an error-free string S_i and another string F_i in the computer system,

determining the frequency H(S_i) of the corresponding error-free string S_i in the text,

using the frequency H(S_i) to detect and/or correct the other string F_i

modifying the error-free string S_i in accordance with a stored rule R_j, generating a possible error string f_ij,

determining the frequency H(f_ij) of the string f_ij in the text,

comparing the frequencies H(f_ij) and H(S_i), using the formula Φ

_ij (H(f_ij), H(S_i))=α

_ij, and

deciding, based on the step of comparing α

_ij with a threshold value β

, whether the possible error string f_ij is an actual error string F_i.

3. A method including the steps of claim 2, wherein the step of modifying the string includes simulating possible error sources in the selection of the rules R_j including psychological and/or technically related to the computer system.

4. A method including the steps of claim 2, wherein the step of evaluating includes using the formula ##EQU2## where Ψ

is a factor and κ

an exponent, whereby the exponent is preferably 1 or -1.

5. A method including the steps of claim 4, wherein the step of evaluating includes using a factor Ψ

calculated according to the formula

space="preserve" listing-type="equation">Ψ

= L(S.sub.i)!.sup.p,

where L(S_i) is the number of characters in the error-free string S_j and p is an exponent, whereby the exponent p is preferably equal to 2 or 3.

6. A method including the steps of claim 2 wherein the method also includes using a dictionary-based method to determine valid strings G_i,

determining whether the string f_ij is a valid string G_i, using the dictionary-based method for a possible error string f_ij having a frequency H(f_ij)>

0, and

modifying the value α

_ij of the possible error string f_ij if the possible error string f_ij is a valid string G_i.

7. A method including the steps of claim 2 further including implementing a method for automated learning by assigning to a rule R_j a variable factor δ

_j (B) and using that factor to modify the value α

_ij of a possible error string f_ij generated by applying the rule R_j.

13. An apparatus including a word processing system and means for detecting and/or correcting an error string F_i in a text, whereby the corresponding error-free string S_i occurs in the text, the apparatus comprising:

first storage means for storing the text,

second storage means for storing the frequency H(_Si) of the error-free string _Si,

a processor for calculating a frequency H(_Si) of the error-free string S_i using the formula Φ

_ij (H(f_ij), H(_Si))=α

_ij and for using the frequency H(_Si) in detecting and/or correcting the error string F_ij,

means for storing the value α

_ij,

a third storage means for storing the frequency H(f_ij) of a possible error string f_ij,

a fourth storage means for storing a rule R_j,

means associated with the processor for modifying the error-free string S_i according to the rule R_j whereby a possible error string f_ij can be generated,

means associated with the processor for determining the frequency H(f_ij) of a possible error string f_ij,

means associated with the processor for comparing the frequencies H(_Si) and H(f_ij) and generating an output signal, and

means associated with the processor for associating the possible error string f_ij to the error string F_i based on the output signal from the means for comparing including means for storing a threshold value β

for comparison with the value α

_ij.

14. The apparatus of claim 13, whereby the means for comparing the frequencies H(_Si) and H(f_ij) associated with the processor include means for computing a value α

_ij in accordance with a computing rule

space="preserve" listing-type="equation">Φ

.sub.ij (H(f.sub.ij),H(.sub.Si))=α

.sub.ij

and means for storing the value α

_ij ;

and the means for associating the possible error includes means for Storing a threshold value β

for comparison with the value α

_ij.

15. The apparatus of claim 13 further comprising means for determining the frequency H(Z_i) of different strings Z_i in the text,

a fifth storage means for storing the frequency H(Z_i),

means for storing a threshold value γ

, and

means for comparing the threshold value γ

with a frequency H(Z_i), whereby those strings Z_i having a frequency H(Z_i) exceeding the threshold value δ

are defined to be error-free strings S_i.

16. An apparatus of the type described in claim 13 further including means for character recognition,

wherein the means for character recognition generates a raw text and enters the raw text into the computer system for detecting and/or correcting one or possibly more than one error string F_i.

17. An apparatus of the type described in claim 13 further including means for speech recognition,

wherein the means for speech recognition system generates a raw text and enters the raw text into the computer system for detecting and/or correcting one or possibly more than one error string F_i.