US6018735A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Non-literal textual search using fuzzy finite-state linear non-deterministic automata
Assignee: Canon Inc
•
Filing: 1997-08-22
•
Granted: 2000-01-25
•
Expires: 2017-08-22
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 automation. The system receives a generalized regular search expression from a user. The system then performs prematching during which it estimates a dissimilarity metric for each target string in the stored document set with respect to the search expression. The strings are then sorted by dissimilarity metric, with the best matches, i.e., the strings having the lowest dissimilarity metrics, first. The search expression is broken down into one or more segments. A linear fizzy finite-state non-deterministic automation is constructed (501) by matching each segment of the search expression with a corresponding set of states and transitions. The automation is initialized and then processes target strings read (502) from the sorted list, thereby generating a dissimilarity value for each target string. A dissimilarity value for each string is determined based upon penalties associated with one-to-one fuzzy character substitution, exchanged adjacent characters, one-to-many, many-to-one, and many-to-many character substitution, and other differences between the search expression and a target string read from storage.
Inventors
- 👤 Kenneth M. Hunter
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 06:43
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
125 words
A computer-implemented method for selectively retrieving information, including a plurality of stored target strings contained in a document set stored on a data storage medium and accessible by a computer processor, the method comprising the steps of: transmitting a search expression to the processor; constructing a linear finite-state non-deterministic automation corresponding to the search expression wherein the automation permits transitions only from a state to itself and from the state to a next state and wherein a linear finite-state non-deterministic automation is constructed for any transmitted search expression; applying the plurality of target strings to the automation and generating thereby a dissimilarity metric for each target string; and producing a list of matching target strings based upon a true dissimilarity metric of each target string.
Claim 2
Dependent Claim
125 words
A computer-implemented method for selectively retrieving information, including a plurality of stored target strings contained in a document set stored on a data storage medium and accessible by a computer processor, the method comprising the steps of: transmitting a search expression to the processor; constructing a linear finite-state non-deterministic automation corresponding to the search expression wherein the automation permits transitions only from a state to itself and from the state to a next state and wherein a linear finite-state non-deterministic automation is constructed for any transmitted search expression; applying the plurality of target strings to the automation and generating thereby a dissimilarity metric for each target string; and producing a list of matching target strings based upon a true dissimilarity metric of each target string.
Claim 3
Dependent Claim
36 words
The method of claim 1, wherein the applying step terminates application of a particular target string to the automation in response to the dissimilarity metric for the particular target string achieving a maximum dissimilarity threshold value.
Claim 4
Dependent Claim
40 words
The method of claim 1, wherein the applying step terminates application of a particular target string to the automation in response to the dissimilarity metric for the particular target string exceeding a dissimilarity metric of a previously applied target string.
Claim 5
Dependent Claim
55 words
The method of claim 1, further comprising the substeps of: estimating an estimated dissimilarity metric for each of the plurality of target strings from the search expression; and sorting the plurality of target strings by estimated dissimilarity metric in a first order, wherein the target strings are applied to the automation in the first order.
Claim 6
Dependent Claim
56 words
The method of claim 4, wherein the estimating step comprises the substeps of: sorting search characters for which the search expression searches in a second order; sorting target characters from each of the plurality of target strings in the second order; and determining a prematch score from the sorted search characters and the sorted target characters.
Claim 7
Dependent Claim
12 words
The method of claim 5, wherein the second order is ASCII order.
Claim 8
Dependent Claim
54 words
The method of claim 5, wherein the prematch score is the sum of: a number of the target characters that are different than the search characters, multiplied by a standard character deletion penalty; and a number of the search characters that are different than the target characters, multiplied by a standard character insertion penalty.
Claim 9
Dependent Claim
52 words
The method of claim 1, wherein the constructing step comprises the substeps of: breaking the search expression into one or more segments; identifying a syntax category for each of the one or more segments; and inserting one or more transitions corresponding to each identified syntax category into the linear finite-state non-deterministic automation.
Claim 10
Dependent Claim
18 words
The method of claim 8, wherein the breaking, identifying, and inserting substeps are performed by a deterministic automation.
Claim 11
Dependent Claim
33 words
The method of claim 8, wherein each of the one or more transitions applies a penalty value dependent upon a character of the target string being applied to the linear finite-state non-deterministic automation.
Claim 12
Dependent Claim
78 words
The method of claim 1, wherein the applying step comprises the substeps of: initializing the automation by assigning a value to each state in the automation dependent upon a location of each state in the automation and a standard insertion penalty, and assigning a state following an exact transition and all subsequent states an infinite value; processing each character of the target string being applied with the initialized automation; and retrieving the true dissimilarity metric from the automation.
Claim 13
Dependent Claim
24 words
The method of claim 1, wherein the applying step comprises the substep of: applying one or more transition rules allowing one-to-one fuzzy character substitution.
Claim 14
Dependent Claim
23 words
The method of claim 1, wherein the applying step comprises the substep of: applying one or more transition rules allowing exchanged adjacent characters.
Claim 15
Dependent Claim
27 words
The method of claim 1, wherein the applying step comprises the substep of: applying one or more transition rules allowing one-to-many, many-to-one, and many-to-many fuzzy character substitutions.
Claim 16
Dependent Claim
36 words
The method of claim 1, wherein the producing step produces N-best matching target strings and further comprises the step of: storing the N-best matching target strings ranked by the true dissimilarity metric of each target string.
Claim 17
Dependent Claim
17 words
The method of claim 15, wherein the N-best matching target strings are held in a priority queue.
Claim 18
Dependent Claim
14 words
The method of claim 1, wherein the search expression is a generalized regular expression.
Claim 19
Dependent Claim
19 words
The method of claim 1, wherein the search expression allows for fuzzy searching, exact searching, and multiple character specification.
Claim 20
Dependent Claim
107 words
A computer system for selectively retrieving information, including a plurality of stored target strings contained in a document set stored on a data storage medium and accessible by a computer processor, the system comprising: a data input device providing a user-defined search expression to the processor; a finite-state deterministic automation adapted for receiving the search expression and generating a linear finite-state non-deterministic automation therefrom adapted to accept as input each distinct stored target string and to produce in response a dissimilarity metric associated with each distinct stored target string; and an output device producing a subset of the distinct stored text strings based upon the dissimilarity metrics.
Claim 21
Dependent Claim
107 words
A computer system for selectively retrieving information, including a plurality of stored target strings contained in a document set stored on a data storage medium and accessible by a computer processor, the system comprising: a data input device providing a user-defined search expression to the processor; a finite-state deterministic automation adapted for receiving the search expression and generating a linear finite-state non-deterministic automation therefrom adapted to accept as input each distinct stored target string and to produce in response a dissimilarity metric associated with each distinct stored target string; and an output device producing a subset of the distinct stored text strings based upon the dissimilarity metrics.
Claim 22
Dependent Claim
27 words
The system of claim 19, wherein the dissimilarity metric produced by the fuzzy finite-state non-deterministic automation accounts for fuzzy exchange of adjacent characters in the target string.
Claim 23
Dependent Claim
22 words
The system of claim 19, wherein the dissimilarity metric produced by the fuzzy finite-state non-deterministic automation accounts for fuzzy one-to-one character exchange.
Claim 24
Dependent Claim
29 words
The system of claim 19, wherein the dissimilarity metric produced by the fuzzy finite-state non-deterministic automation accounts for one-to-many, many-to-one, and many-to-many fuzzy character substitutions in the target string.
Claim 25
Dependent Claim
36 words
The system of claim 19, wherein the finite-state deterministic automation parses the received search expression into one or more segments and wherein each segment corresponds to a set of transitions in the fuzzy finite-state non-deterministic automation.
Claim 26
Dependent Claim
42 words
The system of claim 23, wherein the correspondence between a particular segment and the set of transitions is determined by whether the particular segment is fuzzy, whether the particular segment contains a wild card, and whether the particular segment includes a quantifier.
Claim 27
Dependent Claim
57 words
The system of claim 19, further comprising: a prematching module for: extracting one or more search characters from the search expression; extracting one or more target characters from each distinct target string; and estimating an estimated dissimilarity metric for each distinct target string from the one or more search characters and the one or more target characters.
Claim 28
Dependent Claim
31 words
The system of claim 25, wherein the prematch module sorts the target strings by estimated dissimilarity metric and wherein the fuzzy finite-state non-deterministic automation accepts as input the sorted target strings.
Claim 29
Dependent Claim
43 words
The system of claim 19, wherein the search expression searches for the N-best matching target strings, the system fiurther comprising: a priority module for holding in order the distinct target strings processed by the fuzzy finite-state non-deterministic automation having the N-lowest dissimilarity metrics.
Claim 30
Dependent Claim
14 words
The system of claim 19, wherein the search expression is a generalized regular expression.
Claim 31
Dependent Claim
26 words
The system of claim 28, wherein the search expression is comprised of one or more segments and at least one of the segments specifies multiple characters.
Claim 32
Dependent Claim
132 words
A computer-program method for selectively retrieving information, including a plurality of stored target strings contained in a document set stored on a data storage medium and accessible by a computer processor, the method comprising the steps of: transmitting a search expression to the processor; sorting the plurality of stored target strings by an estimated dissimilarity metric; constructing a linear finite-state non-deterministic automation corresponding to the search expression; applying the sorted target strings to the automation and generating thereby a true dissimilarity metric for each target string, wherein the true dissimilarity metric reflects predetermined differences between each target string and the search expression including: one-to-one fuzzy character substitutions; exchanged adjacent characters; and one-to-many, many-to-one, and many-to-many character substitutions; and storing target strings having the N-lowest true dissimilarity metrics in an N-item data structure.
Claim 33
Dependent Claim
132 words
A computer-program method for selectively retrieving information, including a plurality of stored target strings contained in a document set stored on a data storage medium and accessible by a computer processor, the method comprising the steps of: transmitting a search expression to the processor; sorting the plurality of stored target strings by an estimated dissimilarity metric; constructing a linear finite-state non-deterministic automation corresponding to the search expression; applying the sorted target strings to the automation and generating thereby a true dissimilarity metric for each target string, wherein the true dissimilarity metric reflects predetermined differences between each target string and the search expression including: one-to-one fuzzy character substitutions; exchanged adjacent characters; and one-to-many, many-to-one, and many-to-many character substitutions; and storing target strings having the N-lowest true dissimilarity metrics in an N-item data structure.
Claim 34
Dependent Claim
40 words
The method of claim 30, further comprising the substep of: terminating the application of one of the target strings to the automation when a true dissimilarity metric associated with the one of the target strings exceeds a maximum dissimilarity value.
Claim 35
Dependent Claim
45 words
The method of claim 30, further comprising the substep of: terminating the application of one of the target strings to the automation when a true dissimilarity metric associated with the one of the target strings exceeds a dissimilarity metric of a previously applied target string.
References Cited (Backward Citations)
US5099425A
Cited
US5138669A
Cited
US5825943A
Cited
US5600835A
Cited
US5606690A
Cited
US5610812A
Cited
US5943659A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-24 | 2003-07-26 | 2004-01-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-24 | 2007-07-26 | 2008-01-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-24 | 2011-07-26 | 2012-01-25 | $7700.00 | Window Closed / Lapsed |