Approximate string matching

In computer science, approximate string matching (often colloquially referred to as fuzzy string searching) is the technique of finding strings that match a pattern approximately (rather than exactly). The problem of approximate string matching is typically divided into two sub-problems: finding approximate substring matches inside a given string and finding dictionary strings that match the pattern approximately.

Overview

The closeness of a match is measured in terms of the number of primitive operations necessary to convert the string into an exact match. This number is called the edit distance between the string and the pattern. The usual primitive operations are:^[1]

insertion: cot → coat
deletion: coat → cot
substitution: coat → cost

These three operations may be generalized as forms of substitution by adding a NULL character (here symbolized by *) wherever a character has been deleted or inserted:

insertion: co*t → coat
deletion: coat → co*t
substitution: coat → cost

Some approximate matchers also treat transposition, in which the positions of two letters in the string are swapped, to be a primitive operation.^[1]

transposition: cost → cots

Different approximate matchers impose different constraints. Some matchers use a single global unweighted cost, that is, the total number of primitive operations necessary to convert the match to the pattern. For example, if the pattern is coil, foil differs by one substitution, coils by one insertion, oil by one deletion, and foal by two substitutions. If all operations count as a single unit of cost and the limit is set to one, foil, coils, and oil will count as matches while foal will not.

Other matchers specify the number of operations of each type separately, while still others set a total cost but allow different weights to be assigned to different operations. Some matchers permit separate assignments of limits and weights to individual groups in the pattern.

Problem formulation and algorithms

One possible definition of the approximate string matching problem is the following: Given a pattern string $P=p_{1}p_{2}...p_{m}$ and a text string $T=t_{1}t_{2}\dots t_{n}$ , find a substring $T_{j',j}=t_{j'}\dots t_{j}$ in T, which, of all substrings of T, has the smallest edit distance to the pattern P.

A brute-force approach would be to compute the edit distance to P for all substrings of T, and then choose the substring with the minimum distance. However, this algorithm would have the running time O(n³ m).

A better solution, which was proposed by Sellers,^[2] relies on dynamic programming. It uses an alternative formulation of the problem: for each position j in the text T and each position i in the pattern P, compute the minimum edit distance between the i first characters of the pattern, $P_{i}$ , and any substring $T_{j',j}$ of T that ends at position j.

For each position j in the text T, and each position i in the pattern P, go through all substrings of T ending at position j, and determine which one of them has the minimal edit distance to the i first characters of the pattern P. Write this minimal distance as E(i, j). After computing E(i, j) for all i and j, we can easily find a solution to the original problem: it is the substring for which E(m, j) is minimal (m being the length of the pattern P.)

Computing E(m, j) is very similar to computing the edit distance between two strings. In fact, we can use the Levenshtein distance computing algorithm for E(m, j), the only difference being that we must initialize the first row with zeros, and save the path of computation, that is, whether we used E(i − 1,j), E(i,j − 1) or E(i − 1,j − 1) in computing E(i, j).

In the array containing the E(x, y) values, we then choose the minimal value in the last row, let it be E(x₂, y₂), and follow the path of computation backwards, back to the row number 0. If the field we arrived at was E(0, y₁), then T[y₁ + 1] ... T[y₂] is a substring of T with the minimal edit distance to the pattern P.

Computing the E(x, y) array takes O(mn) time with the dynamic programming algorithm, while the backwards-working phase takes O(n + m) time.

Another recent idea is the similarity join. When matching database relates to a large scale of data, the O(mn) time with the dynamic programming algorithm cannot work within a limited time. So, the idea is to reduce the number of candidate pairs, instead of computing the similarity of all pairs of strings. Widely used algorithms are based on filter-verification, hashing, Locality-sensitive hashing (LSH), Tries and other greedy and approximation algorithms. Most of them are designed to fit some framework (such as Map-Reduce) to compute concurrently.

On-line versus off-line

Traditionally, approximate string matching algorithms are classified into two categories: on-line and off-line. With on-line algorithms the pattern can be processed before searching but the text cannot. In other words, on-line techniques do searching without an index. Early algorithms for on-line approximate matching were suggested by Wagner and Fischer^[3] and by Sellers.^[2] 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 Fischer calculates Levenshtein distance, being appropriate for dictionary fuzzy search only.

On-line searching techniques have been repeatedly improved. Perhaps the most famous improvement is the bitap algorithm (also known as the shift-or and shift-and algorithm), which is very efficient for relatively short pattern strings. The Bitap algorithm is the heart of the Unix searching utility agrep. A review of on-line searching algorithms was done by G. Navarro.^[4]

Although very fast on-line techniques exist, their performance on large data is unacceptable. Text preprocessing or indexing makes searching dramatically faster. Today, a variety of indexing algorithms have been presented. Among them are suffix trees,^[5] metric trees^[6] and n-gram methods.^[7]^[8] A detailed survey of indexing techniques that allows one to find an arbitrary substring in a text is given by Navarro et al.^[7] A computational survey of dictionary methods (i.e., methods that permit finding all dictionary words that approximately match a search pattern) is given by Boytsov.^[9]

Applications

Common applications of approximate matching include spell checking.^[5] With the availability of large amounts of DNA data, matching of nucleotide sequences has become an important application.^[1] Approximate matching is also used in spam filtering.^[5] Record linkage is a common application where records from two disparate databases are matched.

String matching cannot be used for most binary data, such as images and music. They require different algorithms, such as acoustic fingerprinting.

A common command-line tool fzf is often used to integrate approximate string searching into various command-line applications.^[10]

References

Citations

^ ^a ^b ^c Cormen & Leiserson 2001.
^ ^a ^b Sellers 1980.
^ Wagner & Fischer 1974.
^ Navarro 2001.
^ ^a ^b ^c Gusfield 1997.
^ Baeza-Yates & Navarro 1998.
^ ^a ^b Navarro et al. 2001.
^ Zobel & Dart 1995.
^ Boytsov 2011.
^ "Fzf - A Quick Fuzzy File Search from Linux Terminal". www.tecmint.com. 2018-11-08. Retrieved 2022-09-08.

Works cited

Baeza-Yates, R.; Navarro, G. (1998). "Fast Approximate String Matching in a Dictionary" (PDF). Proc. SPIRE'98. IEEE CS Press. pp. 14–22.
Boytsov, Leonid (2011). "Indexing methods for approximate dictionary searching: Comparative analysis". Journal of Experimental Algorithmics. 16 (1): 1–91. doi:10.1145/1963190.1963191. S2CID 15635688.
Cormen, Thomas; Leiserson, Rivest (2001). Introduction to Algorithms (2nd ed.). MIT Press. pp. 364–7. ISBN 978-0-262-03293-3.
Gusfield, Dan (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-58519-4.
Navarro, Gonzalo (2001). "A guided tour to approximate string matching". ACM Computing Surveys. 33 (1): 31–88. CiteSeerX 10.1.1.96.7225. doi:10.1145/375360.375365. S2CID 207551224.
Navarro, Gonzalo; Baeza-Yates, Ricardo; Sutinen, Erkki; Tarhio, Jorma (2001). "Indexing Methods for Approximate String Matching" (PDF). IEEE Data Engineering Bulletin. 24 (4): 19–27.
Sellers, Peter H. (1980). "The Theory and Computation of Evolutionary Distances: Pattern Recognition". Journal of Algorithms. 1 (4): 359–73. doi:10.1016/0196-6774(80)90016-4.
^ Skiena, Steve (1998). Algorithm Design Manual (1st ed.). Springer. ISBN 978-0-387-94860-7.
Wagner, R.; Fischer, M. (1974). "The string-to-string correction problem". Journal of the ACM. 21: 168–73. doi:10.1145/321796.321811. S2CID 13381535.
Zobel, Justin; Dart, Philip (1995). "Finding approximate matches in large lexicons". Software: Practice and Experience. 25 (3): 331–345. CiteSeerX 10.1.1.14.3856. doi:10.1002/spe.4380250307. S2CID 6776819.

External links

Flamingo Project
Efficient Similarity Query Processing Project with recent advances in approximate string matching based on an edit distance threshold.
StringMetric project a Scala library of string metrics and phonetic algorithms
Natural project a JavaScript natural language processing library which includes implementations of popular string metrics

[FOOTNOTECormenLeiserson2001-1] Cormen & Leiserson 2001.

[FOOTNOTESellers1980-2] Sellers 1980.

[FOOTNOTEWagnerFischer1974-3] Wagner & Fischer 1974.

[FOOTNOTENavarro2001-4] Navarro 2001.

[FOOTNOTEGusfield1997-5] Gusfield 1997.

[FOOTNOTEBaeza-YatesNavarro1998-6] Baeza-Yates & Navarro 1998.

[FOOTNOTENavarroBaeza-YatesSutinenTarhio2001-7] Navarro et al. 2001.

[FOOTNOTEZobelDart1995-8] Zobel & Dart 1995.

[FOOTNOTEBoytsov2011-9] Boytsov 2011.

[10] "Fzf - A Quick Fuzzy File Search from Linux Terminal". www.tecmint.com. 2018-11-08. Retrieved 2022-09-08.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt pattern matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm Raita algorithm Trigram search Two-way string-matching algorithm Zhu–Takaoka string matching algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	BLAST Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting String rewriting systems String operations