Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-08-22
2000-01-25
Amsbury, Wayne
Data processing: database and file management or data structures
Database design
Data structure types
707 3, 707 4, 706 2, 706 23, G06F 1730
Patent
active
060187352
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.
REFERENCES:
patent: 5099425 (1992-03-01), Yuji et al.
patent: 5138669 (1992-08-01), Shimura et al.
patent: 5600835 (1997-02-01), Garland et al.
patent: 5606690 (1997-02-01), Hunter et al.
patent: 5610812 (1997-03-01), Schabes et al.
patent: 5825943 (1998-10-01), DeVito et al.
patent: 5943659 (1999-08-01), Giles et al.
Sun Wu and Udi Manber; Fast Text Searching Allowing Errors; Communcations of the ACM; Oct. 1992, vol. 35, No. 10; pp. 83-91.
Udi Manber and Sun Wu; Approximate String Matching With Arbitrary Cost For Text and Hypertext; Department of Computer Science University of Arizona; Feb. 1990; pp. 1-11.
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation; 1979; pp. 13-29.
H. J. Schek; Tolerating Fuzziness in Keywords by Similarity Searches; Kybernetes 1977, vol. 6; pp. 175-184.
Amsbury Wayne
Canon Kabushiki Kaisha
Havan Thu-Thao
LandOfFree
Non-literal textual search using fuzzy finite-state linear non-d does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Non-literal textual search using fuzzy finite-state linear non-d, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-literal textual search using fuzzy finite-state linear non-d will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2323234