Character string correction system and method using error pattern

• US 6,023,536 A
• Filed: 06/21/1996
• Issued: 02/08/2000
• Est. Priority Date: 07/03/1995
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Visser, Eric M.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US08/668,222
• Time in Patent Office: 1,327 Days
• Field of Search: 382/229, 382/231, 382/310, 382/311, 382/309, 382/185-187, 382/177, 395/793-796, 707/532, 707/533, 707/534
• US Class Current: 382/310
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

A character string correction system corrects a spelling error in a character string input through the keyboard, OCT, etc. An error pattern representing frequent occurrences of errors is preliminarily set and stored in the memory, etc. A processor reads an input character string character by character, and compares the read character with the error pattern. If the input character string matches an error pattern, it is assumed that an error exists. The input character is replaced with one of the alternative characters. Using the input character string or the character string corrected with an alternative character, a dictionary (TRIE table) is searched. If a corresponding word is detected in the dictionary, the word is output as one of the recognition results.

Claims

1. A character string correction system for use in an information processing system for analyzing a morpheme by comparing an input character string with a dictionary entry, comprising:

dictionary storage means for storing a dictionary having entries of input characters to be compared with characters in the input character string;

error pattern storage means for storing an error pattern prescribing a type of possible error in the input character string and for storing the error pattern comprising a fault pattern representing a character pattern of a possible error and a correct pattern representing a correct character pattern corresponding to the fault pattern; and

retrieval means for searching the dictionary stored in said dictionary storage means using the error pattern stored in said error pattern storage means retrieving the dictionary entry corresponding to the input character string, outputting the retrieved dictionary entry as a candidate for a recognized word, generating an alternative character replacing a first character by referring to the correct pattern when the first character corresponding to the fault pattern is input, and searching the dictionary using the alternative character.

2. The character string correction system according to claim 1, wherein

said retrieval means generates an alternative character string replacing the first character by referring to the correct pattern, and searches the dictionary using each character in the alternative character string as the alternative character.

3. The character string correction system according to claim 1, wherein

said retrieval means searches the dictionary using the alternative character under assumptions that a second character in the input character string is a beginning of the fault pattern even when the second character matches an entry of the input character in the dictionary.

4. The character string correction system according to claim 1, wherein

said retrieval means generates a plurality of alternative characters corresponding to the correct pattern, searches the dictionary using each alternative character, and retrieves the alternative character to obtain a candidate for the recognized word from among the plurality of alternative characters.

5. The character string correction system according to claim 1, wherein

said retrieval means selects the alternative character matching the input character string from among the plurality of alternative characters corresponding to the correct pattern by reading remaining characters in the input character string, and searches the dictionary using the selected alternative character.

6. The character string correction system according to claim 1, wherein

said retrieval means determines whether or not the error pattern matches the input character string by reading remaining characters in the input character string and comparing the characters with the plurality of alternative characters corresponding to the correct pattern.

7. The character string correction system for use in an information processing system for analyzing a morpheme by comparing an input character string with a dictionary entry, comprising:

dictionary storage means for storing a dictionary having a entries of input characters to be compared with characters in the input character string;

said dictionary storage means stores the dictionary containing a plurality of TRIE tables for use in retrieving each input character;

each of said plurality of TRIE tables comprises a character entry and a TRIE table link, corresponding to a character string from a first character to an intermediate character in a dictionary entry, wherein said character entry of the input character indicating a candidate for a next character, and wherein said TRIE table link specifying a next TRIE table;

a corresponding word entry in a dictionary representing a correspondence to the dictionary entry;

error pattern storage means for storing an error pattern having a type of possible error in the input character string, conditions and a weight comprising;

a fault pattern representing a character pattern of a possible error and a correct pattern representing a correct character pattern corresponding to the fault pattern; and

retrieval means for searching the dictionary stored in said dictionary storage means using the error pattern storage means retrieving the dictionary entry corresponding to the input character string, and outputting the retrieved dictionary entry as a candidate for a recognized word;

wherein

said retrieval means compares an alternative character obtained from the correct pattern with the character entry of the input character to retrieve the plurality of TRIE tables.

8. A character string correction system for use in an information processing system for analyzing a morpheme by comparing an input character string with a dictionary entry, comprising:

dictionary storage means for storing a dictionary having entries of input characters to be compared with characters in the input character string;

error pattern storage means for storing an error pattern prescribing a type of possible error in the input character string;

retrieval means for searching the dictionary stored in said dictionary storage means using the error pattern stored in said error pattern storage means retrieving the dictionary entry corresponding to the input character string, outputting the retrieved dictionary entry as a candidate for a recognized word, and for generating

a corresponding analysis path when a character in the input character string matches an entry of the input character in the dictionary; and

memory means for storing an analysis path indicating a retrieval path from a first character to an intermediate character of the dictionary entry.

9. The character string correction system according to claim 8, wherein

said retrieval means generates the analysis path including information about an error pattern in progress when said error pattern is applied to said input character string.

10. The character string correction system according to claim 8, wherein

when recognizing a morpheme as a result of searching the dictionary, said retrieval means stores information specifying the morpheme as being associated with the analysis path.