NON-LITERAL TEXTUAL SEARCH USING FUZZY FINITE-STATE LINEAR NON-DETERMINISTIC AUTOMATA

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.