Approximate string matching

Problem formulation and algorithms

One possible definition of the approximate string matching problem is the following: Given a pattern string ${\displaystyle P=p_1{p}_2...p_m}$ and a text string ${\displaystyle T=t_1{t}_2\dots t_n}$, find a substring ${\displaystyle T_{j^{\prime },j}=t_{j^{\prime }}\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, 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, ${\displaystyle P_i}$, and any substring ${\displaystyle T_{j^{\prime },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.

There are also algorithms whose running time depends on k, a bound on the edit distance of interest, and are better when k is small relative to the length of the strings. In 1989, Landau and Vishkin gave an ${\displaystyle O(nk)}$ algorithm. This algorithm is still based on the above dynamic-programming matrix, but fills it in a clever way, along diagonals. In 2002, using a more complex algorithm, Cole and Hariharan achieved a complexity of ${\displaystyle O(\frac{k^4}{m}+n+m)}$. Note that this is better when ${\displaystyle k^3\ll nm}$.

The specialized problem of pattern matching with k mismatches is defined by disallowing insertions and deletions in the matching of the pattern to the text. Thus, the Hamming distance of the pattern to the corresponding segment of the text has to be at most k. This problem has been solved with a complexity of ${\displaystyle O(n\sqrt{k\log k})}$.

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.

Online versus offline

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

Online searching techniques have been repeatedly improved. Perhaps the most famous improvement is the bitap algorithm (also known as the 'shift-or' or '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 online searching algorithms was done by G. Navarro.

Although very fast online techniques exist, their performance on large data is disfavored. Text preprocessing or indexing makes searching dramatically faster. Today, a variety of indexing algorithms have been presented. Among them are suffix trees, metric trees and n-gram methods. A detailed survey of indexing techniques that allows one to find an arbitrary substring in a text is given by Navarro et al. 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.

Applications

Common applications of approximate matching include spell checking. With the availability of large amounts of DNA data, matching of nucleotide sequences has become an important application. Approximate matching is also used in spam filtering. 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.