In computer science, approximate string matching is the technique of finding strings that match
a pattern approximately. 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 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.
Changing cost to cots is an example of a transposition.[2] 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 and a text string , find
a substring 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(n3 m).
A better solution, which was proposed by Sellers [3], 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, , and any substring 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
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(x2, y2), and follow the
path of computation backwards, back to the row number 0. If the field we arrived at was
E(x1, 0), then T[x1 + 1] ... T[y2] 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. 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 Fisher[4] and
by Sellers. [5] 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 have been repeatedly
improved. Perhaps the most famous improvement is the bitap 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.[6]
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[7], metric trees[8] and n-gram
methods.[9][10] A detailed survey of indexing techniques that allows one to find an arbitrary
substring in a text is given by Navarro et al.[11]. A computational survey of dictionary
methods is given by Boytsov [12]. Applications
The most common application of approximate matchers until recently has been spell checking.[13]
With the availability of large amounts of DNA data, matching of nucleotide sequences
has become an important application.[14] Approximate matching is also used to identify pieces of
music from small snatches and in spam filtering.[15] See also
String metric Locality-sensitive hashing
Needleman–Wunsch algorithm Smith–Waterman algorithm
Jaro-Winkler distance Levenshtein distance
Concept Search Approximate matching with addition of regular
expressions ability Regular expressions for non-fuzzy matching
Metaphone Soundex
Agrep Plagiarism detection
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
References