Non-literal textual search using fuzzy finite non-deterministic automata

• US 5,606,690 A
• Filed: 10/28/1994
• Issued: 02/25/1997
• Est. Priority Date: 08/20/1993
• Status: Expired due to Term

• Current Assignee: Canon Inc.
• Original Assignee: Canon Inc.
• Inventors: Roberts, Michael G., Garland, Harry T., Hunter, Kenneth M.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/330,968
• Time in Patent Office: 851 Days
• Field of Search: 395/600, 382/37, 364/419.13, 364/300
• US Class Current: 715/255
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Method and system for selectively retrieving information contained in a stored document set using a metric-based or "fuzzy" finite-state non-deterministic automaton. An automaton is constructed (501) corresponding to a text string query, text strings are read (502) from storage and corresponding dissimilarity values are generated (505). Those strings resulting in values less than a given threshold are recorded (508) and listed for the user. Dissimilarity values are determined based on penalties associated with missing characters, extra characters, incorrect characters, and other differences between the text string query and a text string read from storage.

Claims

1. A computer-implemented method for selectively retrieving information, including a plurality of stored text strings that do not have to be presorted, said stored text strings contained in a document set stored on a data storage medium and accessible by a computer processor, the method comprising the steps of:

A. transmitting a user-defined text string query to the processor;

B. constructing a fuzzy finite non-deterministic fixed-size automaton corresponding to said query, wherein said automaton has at least two states, each state can have more than two values, and more than one state can be active simultaneously;

C. applying each distinct stored text string individually and sequentially to said automaton just once and generating thereby an accumulated dissimilarity metric associated with each distinct text string in the stored document set; and

D. displaying a subset of the distinct stored text strings, said subset based upon values of the accumulated dissimilarity metrics.

2. The method of claim 1, wherein constructing the automaton includes providing a facility for adding a transition penalty value to the accumulated dissimilarity metric associated with a text string in the stored document set for predetermined differences between said query and said text string, which differences can exist with respect to any point within said text string.

3. The method of claim 2, wherein the predetermined differences include missing characters.

4. The method of claim 2, wherein the predetermined differences include extra characters.

5. The method of claim 2, wherein the predetermined differences include ambiguous characters.

6. The method of claim 2, wherein the predetermined differences include phonetic replacements.

7. The method of claim 2, wherein the predetermined differences include grammatical replacements.

8. The method of claim 2, wherein the predetermined differences include changes in capitalization.

9. The method of claim 2, wherein the predetermined differences include misspellings.

10. The method of claim 2, wherein the predetermined differences include exchanged adjacent characters.

11. The method of claim 2, further comprising terminating processing of said automaton with respect to one of said text strings in response to said accumulated dissimilarity metric associated with said one string achieving a maximum dissimilarity threshold value.

12. The method of claim 2, further comprising establishing an aggregate dissimilarity metric for a document in the stored document set by summing the dissimilarity metrics associated with each of the strings in the subset corresponding to the document.

25. The method of claim 1 wherein said text string query can contain non-literal expressions.

13. A computer system for selectively retrieving information, including a plurality of stored text strings that do not have to be presorted, said text strings contained in a document set stored on a data storage medium and accessible by a computer processor, the system comprising:

A. a data input device providing a user-defined text string query to the processor;

B. a fuzzy non-deterministic fixed-size automaton corresponding to said query, adapted to accept as input each distinct stored text string and to produce in response a dissimilarity metric associated with each distinct stored text string, wherein said automaton has at least two states, each state can have more than two values, and more than one state can be active simultaneously; and

C. a display device displaying a subset of the distinct stored text strings, said subset based upon values of the dissimilarity metrics.

14. The system of claim 13, wherein the automaton is constructed to add a penalty value to the dissimilarity metric associated with a text string in the stored document set for predetermined differences between said query and said text string, which differences can exist with respect to any point within the text string.

15. The system of claim 14, wherein the predetermined differences include missing characters.

16. The system of claim 14, wherein the predetermined differences include extra characters.

17. The system of claim 14, wherein the predetermined differences include unrecognizable characters.

18. The system of claim 14, wherein the predetermined differences include phonetic replacements.

19. The system of claim 14, wherein the predetermined differences include grammatical replacements.

20. The system of claim 14, wherein the predetermined differences include changes in capitalization.

21. The system of claim 14, wherein the predetermined differences include misspellings.

22. The system of claim 14, wherein the predetermined differences include exchanged adjacent characters.

23. The system of claim 14, wherein the automaton terminates processing with respect to one of said text strings in response to said dissimilarity metric associated with said one string achieving a maximum dissimilarity threshold value.

24. The system of claim 14, wherein the automaton establishes an aggregate dissimilarity metric for a document in the stored document set by summing the dissimilarity metrics associated with each of the strings in the subset corresponding to the document.

26. The system of claim 13 wherein said text string query can contain non-literal expressions.