| Fuzzy String Searching |
Article Index for Fuzzy |
Website Links For Fuzzy |
Information AboutFuzzy String Searching |
| CATEGORIES ABOUT FUZZY STRING SEARCHING | |
| searching | |
| algorithms on strings | |
|
finding strings that approximately match some given pattern string. Fuzzy string searching has two different flavors: finding one or more matching substrings of a text, and finding similar strings in a string set often referred to as dictionary. Fuzzy string searching has many application areas including information retrieval, spellchecking and computational biology . The corner stone of any approximate searching method is a '''similarity function. Among most commonly used similarity functions are Levenshtein Distance and N-gram Distance . The latter is based on counting of the number of common N-gram s. It is used mostly for filtering. In contrast to n-gram distance, Levenshtein Distance is a de-facto standard similarity function. It has several extensions. One well known extension is Damerau-Levenshtein Distance that counts Transposition as a single edit operation. Another extension is the so-called generalized or weighted Levenshtein distance. It assigns different costs to elementary edit operations. Ukkonen described even more sophisticated similarity function where edit operations go beyond single-character insertions, deletions and substitutions and include substitutions of arbitrary-length strings. Traditionally, approximate string matching algorithms are classified into two categories: on-line and off-line. With on-line algorithms the pattern can be preprocessed before searching but the text cannot. In other words, on-line techniques do searching without indexation. Early algorithms for on-line approximate matching were suggested by Wagner and Fisher and by Sellers . Both algorithms are based on Dynamic Programming but solve different problems. Sellers' algorithm searches approximately for a substring in a text while the algorithm of Wagner and Fisher calculates Levenshtein Distance , being appropriate for dictionary fuzzy search only. On-line searching techniques were repeatedly improved. Perhaps, the most famous improvement is Bitap Algorithm (also known as shift-or and shift-and algorithm), which is very efficient for relatively short pattern strings. Bitap Algorithm is the heart of Unix searching Utility Agrep . An excellent review of on-line searching algorithms was done by G. Navarro . Although very fast on-line techniques exist their performance on large data is unacceptable. In its turn, text preprocessing, or in other words indexing, makes searching dramatically faster. Today, a variety of indexing algorithms are presented. Among them are Suffix Trees , Metric Trees and N-gram methods . For a detailed list of indexing techniques I would address the reader to the paper of Navarro et. al. SEE ALSO
REFERENCES |
|
|