US5606690A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Non-literal textual search using fuzzy finite non-deterministic automata
Assignee: Canon Inc
•
Filing: 1994-10-28
•
Granted: 1997-02-25
•
Expires: 2014-10-28
Abstract
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.
Inventors
- 👤 Kenneth M. Hunter
- 👤 Michael G. Roberts
- 👤 Harry T. Garland
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 08:28
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/268; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; G06F16/30; G06F16/33; G06F16/3331; G06F16/334; G06F40/232; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/917; Y10S707/99931; Y10S707/99933; Y10S707/99935
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
149 words
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.
Claim 2
Dependent Claim
149 words
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.
Claim 3
Dependent Claim
57 words
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.
Claim 4
Dependent Claim
12 words
The method of claim 2, wherein the predetermined differences include missing characters.
Claim 5
Dependent Claim
12 words
The method of claim 2, wherein the predetermined differences include extra characters.
Claim 6
Dependent Claim
12 words
The method of claim 2, wherein the predetermined differences include ambiguous characters.
Claim 7
Dependent Claim
12 words
The method of claim 2, wherein the predetermined differences include phonetic replacements.
Claim 8
Dependent Claim
12 words
The method of claim 2, wherein the predetermined differences include grammatical replacements.
Claim 9
Dependent Claim
13 words
The method of claim 2, wherein the predetermined differences include changes in capitalization.
Claim 10
Dependent Claim
11 words
The method of claim 2, wherein the predetermined differences include misspellings.
Claim 11
Dependent Claim
13 words
The method of claim 2, wherein the predetermined differences include exchanged adjacent characters.
Claim 12
Dependent Claim
38 words
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.
Claim 13
Dependent Claim
38 words
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.
Claim 14
Dependent Claim
141 words
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.
Claim 15
Dependent Claim
141 words
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.
Claim 16
Dependent Claim
52 words
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.
Claim 17
Dependent Claim
12 words
The system of claim 14, wherein the predetermined differences include missing characters.
Claim 18
Dependent Claim
12 words
The system of claim 14, wherein the predetermined differences include extra characters.
Claim 19
Dependent Claim
12 words
The system of claim 14, wherein the predetermined differences include unrecognizable characters.
Claim 20
Dependent Claim
12 words
The system of claim 14, wherein the predetermined differences include phonetic replacements.
Claim 21
Dependent Claim
12 words
The system of claim 14, wherein the predetermined differences include grammatical replacements.
Claim 22
Dependent Claim
13 words
The system of claim 14, wherein the predetermined differences include changes in capitalization.
Claim 23
Dependent Claim
11 words
The system of claim 14, wherein the predetermined differences include misspellings.
Claim 24
Dependent Claim
13 words
The system of claim 14, wherein the predetermined differences include exchanged adjacent characters.
Claim 25
Dependent Claim
35 words
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.
Claim 26
Dependent Claim
39 words
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.
Claim 27
Dependent Claim
14 words
The method of claim 1 wherein said text string query can contain non-literal expressions.
Claim 28
Dependent Claim
14 words
The system of claim 13 wherein said text string query can contain non-literal expressions.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-25 | 2000-08-26 | 2001-02-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-25 | 2004-08-26 | 2005-02-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-25 | 2008-08-26 | 2009-02-25 | $7700.00 | Window Closed / Lapsed |