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

• US 6,018,735 A
• Filed: 08/22/1997
• Issued: 01/25/2000
• Est. Priority Date: 08/22/1997
• Status: Expired due to Term

• Current Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Original Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Inventors: Hunter, Kenneth M.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): HAVAN, THU THAO
• Application Number:
  US08/918,503
• Time in Patent Office: 886 Days
• Field of Search: 707/3, 707/5, 707/4, 707/102, 707/103, 707/532, 382/229, 382/306, 382/177, 382/209, 382/228, 382/226, 364/222, 364/226, 364/717, 706/20, 706/8, 706/5, 706/2, 706/23
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• 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 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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. The method of claim 5, wherein the second order is ASCII order.

7. 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.

8. 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.

9. The method of claim 8, wherein the breaking, identifying, and inserting substeps are performed by a deterministic automation.

10. 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.

11. 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.

12. 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.

13. The method of claim 1, wherein the applying step comprises the substep of:

applying one or more transition rules allowing exchanged adjacent characters.

14. 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.

15. 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.

16. The method of claim 15, wherein the N-best matching target strings are held in a priority queue.

17. The method of claim 1, wherein the search expression is a generalized regular expression.

18. The method of claim 1, wherein the search expression allows for fuzzy searching, exact searching, and multiple character specification.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. The system of claim 19, wherein the search expression is a generalized regular expression.

29. 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.

30. 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.

31. 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.

32. 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.