Tries for Approximate String Matching.
AbstractTries offer text searches with costs which are independent of the size of the document being searched, and so are important for large documents requiring spelling checkers, case insensitivity, and limited approximate regular secondary storage. Approximate searches, in which the search pattern differs from the document by k substitutions, transpositions, insertions or deletions, have hitherto been carried out only at costs linear in the size of the document. We present a trie-based method whose cost is independent of document size. Our experiments show that this new method significantly outperforms the nearest competitor for are arguably the most important cases. The linear cost (in k) of the other methods begins to catch up, for our small files, only at 2. For larger files, complexity arguments indicate that tries will outperform the linear methods for larger values of k. Trie indexes combine suffixes and so are compact in storage. When the text itself does not need to be stored, as in a spelling checker, we even obtain negative overhead: 50% compression. We discuss a variety of applications and extensions, including best match (for spelling checkers), case insensitivity, and limited approximate regular expression matching.
Introduction
The need to find an approximate match to a string arises in many practical
problems. For example, if an optical character reader interprets a "D" as
an "O", an automatic checker would need to look up the resulting word, say
"eoit" in a dictionary to find that "edit" matches it up to one substitution. Or
a writer may transpose two letters at the keyboard, and the intended word,
worst-case run preproc. time extra space ref.
naive mn
Shift-or O(n) O(m+ j\Sigmaj) O(j\Sigmaj) [4]
Patricia O(m) O(n log n) O(n) [10]

Figure

1: Exact Match Algorithms
say "sent", should be detected instead of the error, "snet". Applications
occur with strings other than text: strings of DNA base pairs, strings of
musical pitch and duration, strings of edge lengths and displacements in a
diagram, and so on. In addition to substitutions and transpositions, as above,
errors can include insertions and deletions.
The approximate match problem in strings is a development of the simpler
problem of exact match: given a text, W n , of n characters from an alphabet
\Sigma, and a string, Pm , of m characters, of P in
W . Baeza-Yates [2] reviews exact match algorithms, and we summarize in

Figure

1.
Here, all algorithms except the naive approach require some preprocess-
ing. The Knuth-Morris-Pratt (KMP), Boyer-Moore (BM), and Shift-or algorithms
all preprocess the search string, P , to save comparisons. The Boyer-Moore
algorithms are sublinear in practice, and better the bigger m is, but
depend on n. The Patricia method builds a trie and is truly sublinear. 1 The
preprocessing is on the text, not the search strings, and although substantially
greater than for the linear algorithms, need be done only once for a
text. Note that tries of size n can be built in RAM in time O(n), but that
on secondary storage, memory differences make it better to use an n log n
method for all practical sizes of trie. So we quote that complexity.
Trie-based methods are best suited for very large texts, which require
secondary storage. We emphasize them in this paper, but will compare our
trie-based method experimentally with the linear methods.
Approximate string matching adds a parameter to the above, k: the
algorithm reports a match where the string differs from the text by not
1 The term "sublinear" in this literature has two meanings, which we distinguish as
sublinear and truly sublinear. Truly sublinear in n means O(f(n)) where f is a sublinear
function, e.g., log n or 1. Sublinear means truly sublinear or O(n) where the multiplicative
constant is less than 1.
more than k changes. A change can be a replacement (or substitution),
an insertion, or a deletion. It can also be a transposition, as illustrated
above. Such operations were formulated by Damerau [8] and the notion
of edit distances was given by Levenshtein [15]. A dynamic programming
(DP) algorithm was shown by Wagner and Fischer [26] with O(mn) worst
case. Ukkonen [24] improved this to O(kn) (and clearly k - m) by finding
a cutoff in the DP. Chang and Lawler [7] have the same worst case, but get
sublinear expected time, O((n=m)k log m)) and only O(m) space, as opposed
to O(m 2 ) or O(n) for earlier methods. This they do by building a suffix tree
[27, 16], which is just a "Patricia" trie (after Morrison [19]), on the pattern
as a method of detecting common substrings. Kim and Shawe-Taylor [12]
propose an O(m log n) algorithm with O(n) preprocessing. They generate n-grams
for the text and represent them as a trie for compactness. Baeza-Yates
and Perlberg [5] propose a counting algorithm which runs in time independent
of k, O(n +R), where R is bounded O(n) and is zero if all characters in Pm
are distinct. Figure 2 summarizes this discussion. Agrep [28] is a package
based on related ideas, which also does limited regular expression matching,
i.e., Pm is a regular expression.
(Regular expression matching and k-approximate string matching solve
worst-case run preproc. time extra space ref.
cutoff O(kn) O(k) O(kn) [24]
suffix tree O(kn) O(m) O(m) [7]
n-gram O(m log n) [12]

Figure

2: k-Approximate Match Algorithms
different problems. The problem areas overlap - e.g., P
# is a one-place wildcard, can be written as a regular expression, but is also
a 3-approximate match - but they do not coincide.)
A recent review of these techniques is in the book by Stephen [23]. Hall
and Dowling [11] give an early survey of approximate match techniques. The
work is all directed to searches in relatively small texts, i.e., those not too
large to fit into RAM. For texts that require secondary storage, O(n) is far
too slow, and we need O(log n) or faster methods, as with conventional files
containing separate records [17]. The price we must pay is to store an index,
which must be built once for the whole text (unless the text changes). If we
are interested in the text as an ordered sequence of characters, we must store
the text as well, and the index represents an additional storage requirement.
If we are interested in the text only for the substrings it contains, as in a
dictionary for spelling check, then we need only store the index, and we can
often achieve compression as well as retrieval speed.
Tries have been used to index very large texts [10, 18] and are the only
known truly sublinear way to do so. Tries are trees in which nodes are empty
but have a potential subtree for each letter of the alphabet, \Sigma, encoding the
data (e.g., 0 and 1 for binary tries). The data is represented not in the nodes
but in the path from root to leaf. Thus all strings sharing a prefix will be
represented by paths branching from a common initial path, and considerable
compression can be achieved. 2 Substring matching just involves finding a
path, and the cost is O(m log n) plus terms in the number of resulting
matches. (The log n component reflects only the number of bits required to
store pointers to the text, and is unimportant.) Regular expression matching
2 Note that this compression is on the index, which may still be larger than the text.
Typically, if we index every character in the text, as we do in Section 4, the index will
be five times the size of the text. If we index only every word, the index is smaller and
compression results.[18] If we do only dictionary searches, as in Section 6, there is great
compression.
simulates the regular expression on the trie, [9] and is also fast O(log m (n) n ff )
where ff!1.
This paper proposes a k-approximate match algorithm using Damerau-
Levenshtein DP on a text represented as a trie. The insight is that the trie
representation of the text drastically shortens the DP. A m \Theta n DP table is
used to match a given Pm with the text, W n . There would have to be a new
table for each suffix in W (of length n; But the trie representation
of W compresses these suffixes into overlapping paths, and the corresponding
column need be evaluated only once. Furthermore, the Ukkonen cutoff can be
used to terminate unsuccessful searches very early, as soon as the differences
exceed k. Chang and Lawler [7] showed Ukkonen's algorithm evaluated O(k)
columns, which implies searching a trie down to depth O(k). If the fanout
of a trie is \Sigma, the trie method needs only to evaluate O(k j\Sigmaj k ) DP table
entries.
We present this method in terms of full-text retrieval, for which both the
index and the text must be stored. In applications such as spelling checkers
[14], the text is a dictionary, a set of words, and need not be stored separately
from the index. These are special cases of what we describe. In such cases,
our method offers negative storage overhead, by virtue of the compression,
in addition to the very fast performance.
We compare our work experimentally with agrep [28], and show that tries
outperform agrep significantly for small k, the number of mismatches. Since
agrep complexity is linear in k, and trie search complexity is exponential in k,
agrep is expected to become better than tries for large k. Our experiments
show that the breakeven occurs beyond the practically important case of
1. Since the authors of agrep compare their work thoroughly with other
approximate search techniques [28], we make no other comparisons here.
This paper is organized as follows. The next section introduces Damerau-
Levenshtein DP for approximate string matches. Section 3 briefly describes
data structures, and gives our new algorithm for approximate search
on text tries. Then we give experimental results comparing approximate trie
methods with agrep. Sections 5 and 6 discuss extensions and advanced applications
of our method, including the important case of dictionary checking,
where we attain both speedup and compression. We conclude and discuss
further possible research.
Programming
be a pattern and a target string
respectively. We use D(Pm distance, the minimum number of
edit operations to change Pm to W ' . Here, an edit operation is either to
or to transpose two adjacent
symbols in Pm . We assume symbols are drawn from a finite alphabet, \Sigma.
Given an example example. We have D(P 7
3 since changing P 7 to W 7 needs to: (1) delete
l. The edit distance,
be recursively defined as follows:
@
A
else
(the null character), and
else
else
To evaluate D(Pm ; W ' ), we need to invoke D four times with both subscripts
decreasing by no more than two. Thus, a brute force evaluation must
take O(2 min(m;') ) calls. However, for D(Pm ; W ' ), there are only (m+1)\Theta('+1)
possible values. DP evaluates D(Pm ; W ' ) by storing each possible D value in
a m\Theta' table. Table 1 shows a 3\Theta4 DP table for P 2 =ab and W 3 =bbc.

Table

1: Dynamic Programming
Furthermore, it is not necessary to evaluate every D values (DP table
entries). Ukkonen [24] proposed an algorithm to reduce the table evalua-
tions. His algorithm works as follows: Let C j be the maximum i such that
for the given j (C j =0 if no such i). Given
and then set C j to the largest i (0-
such that D(P i proved that this algorithm evaluates
expected entries. As shown in Table 2, for P 4 =adfd and W 7 =acdfbdf
of 5\Theta8=40 entries, Ukkonen's algorithm evaluates only 23 entries for k=1.
Ukkonen's algorithm sets D(P 1 at initial
time. It evaluates the first column up to row C 0 +1=2. Since the largest
entry value of this column is at row 2, it sets C 1 =2. Then, it evaluates the
second column up to row C 1 +1=3. Since the largest entry value of this column
is at at row 2, it sets C 2 =2. Similarly, it evaluates the third column
up to row C 2 +1=3 to get C 3 =2, the fourth column to get C 4 =3, and the
fifth column to get C 5 =0, which indicates that it is impossible to change
any prefix of adfd to acdfb in less than one edit operation. Thus, we know
We can stop the evaluation if we do not want to know the
exact value of D(P 4
3 Trie and Approximate Search
We follow Gonnet et al. [9] in using semi-infinite strings, or sistrings. A
sistring is a suffix of the text starting at some position. A text consists
of many sistrings. If we assume sistrings start at word boundaries, the
text, "echo enfold sample enface same example," will have six sistrings
of this kind. Figure 3 shows these sistrings and an index trie constructed
over these sistrings. To make Figure 3 simpler, we truncate sistrings after
the first blank. To index full size sistrings, we simply replace leaf nodes by
sistring locations in the text. To prevent a sistring being a proper suffix of
another, we can append either arbitrary numbers of the null symbol after
the text or a unique end-of-text symbol. The index trie has many distinctive
properties:
ffl When conducting a depth-first traverse, we not only get all sistrings,
but also get them in lexicographical order.
ffl When searching a string, say example, branching decisions at each node
are given by each character of the string being sought. As the trie in

Figure

3, we test the first letter e to get to the left branch, and the
second letter x to get to the right branch. As a result, search time is
proportional only to the length of the pattern string, and independent
of the text size.
echo enfold sample enface same example
Sistrings:
echo enfold sample enface same example
enfold sample enface same example
sample enface same example
enface same example
same example
example
e s
a
f
ho
c
ce ld
ample
x
a
le
Trie:

Figure

3: Text, Sistring and Index Trie
ffl The common prefixes of all sistrings are stored only once in the trie.
This gives substantial data compression, and is important when indexing
very large texts.
Trie methods for text can be found in [10, 18, 22]. Here we describe them
only briefly. When constructing a trie over a large number of and extremely
long sistrings, we have to consider the representation of a huge trie on secondary
storage. Tries could be represented as trees, with pointers to subtrees,
as proposed by Morrison [19], who first came up with the Patricia trie for
text searches. Orenstein [21] has a very compact, pointerless representation,
which uses two bits per node and which he adapted for secondary storage.
Merrett and Shang [18, 22] refined this method and made it workable for
Patricia tries with one bit per node. Essentially, both pointerless representations
would entail sequential searches through the trie, except that the bits
are partitioned into secondary storage blocks, with trie nodes and blocks
each grouped into levels such that any level of nodes is either entirely on or
entirely off a level of blocks. With the addition of two integers per block, the
sequential search is restricted to within the blocks, which may be searched
as a tree. For more details of this representation, see [22].
3.1 Two Observations
Before introducing our approximate search algorithm, we give two observations
which will link the trie method with the DP technique.
Observation I
Each trie path is a prefix shared by all sistrings in the subtrie. When evaluating
DP tables for these sistrings, we will have identical columns up to the
prefix. Therefore, these columns need to be evaluated only once.
Suppose we are searching for string sane in a trie shown in Figure 3. To
calculate distances to each word, we need to evaluate six tables. Table 3
shows three of them. For each table, entries of the ith column depend only
on entries of the j-i th column, or the first i letters of the target word.
Words sample and same have the same prefix sam, and therefore, share the
table entries up to the third column. And so does the first column of words
echo, enface, enfold and example, the first three columns of words enface
and enfold. In general, given a path of length x, all DP entries of words in
the subtrie are identical up to the xth column.
This observation tells us that edit distances to each indexed word (sistring
in general) can be calculated by traversing the trie, and in the meantime,
storing and evaluating one DP table. Sharing of common prefixes in a trie
structure saves us not only index space but also search time.
Observation II
If all entries of a column are ? k, no word with the same prefix can have a
distance - k. Therefore, we can stop searching down the subtrie.
For the last table of Table 3, all entries of the second column are ? 1.
If searching for words with differences, we can stop evaluating strings
in the subtrie because for sure D(sane; en:::) ? 1. For the same reason,
after evaluating the fourth column of table sample, we find all entries of the
are ? 1, and therefore, stop the evaluation.
This observation tells us that it is not necessary to evaluate every sistring
in a trie. Many subtries will be bypassed. In an extreme case, the exact
search, all but one of the subtries are trimmed.
3.2 Search Algorithm
The algorithm of Figure 4 shows two functions: DFSearch( T rieRoot, 1)
traverses an index trie depth-first, and EditDist( j) evaluates the jth column
of the DP table for pattern string P and target string W . For the purpose
of illustration, we start and stop evaluation at the word boundary in the
following explanation.
Essentially, this algorithm is a trie walker with cutoffs (rejects before
reaching leaves). Given a node c, its root-to-c path, w 1 w 2 :::w x , is a prefix
shared by all strings in SubT rie(c). If changing w 1 w 2 :::w x to any possible
prefix of P costs more than k, there will be no string in SubT rie(c) with
:array [\Gamma1::max; \Gamma1::max] of integer; /* [i;
:array [0::max] of integer; /* variables for Ukkonen's cutoff,
:array [0::max] of character; /* pattern and target string, W
number of allowable errors */
Procedure DFSearch( T rieNode :Anode, Level :integer);
begin /* depth-first trie search */
if (T rieNode in a leaf node) then
for each character in the node do /* retrieve characters one by one */
W[Level] := the retrieved character;
find a target word */
output W[1]W[2].W[j-1];
return;
if (EditDist(
return;
Level
else
for each child node do /* retrieve child node one by one */
ChildNode := the retrieved node;
W[Level] := the retrieved character;
find a target word */
output W[1]W[2].W[j-1];
return;
if (EditDist( search subtrie down */
return;
DFSearch( ChildNode, Level+1) /* search down the subtrie */
Function
begin /* evaluate one column of DP table */
for i:=1 to Min( C[j-1]+1, length(p)) do
evaluate one table entry */
r := if (P[i-1]=W[j] and P[i]=W[j-1]) then 1 else
return (if (C[j]=0) then 1 else T[i-1,j]);

Figure

4: Approximate Trie Search Algorithm
mismatches. Hence, there is no need to walk down Subtrie(c). A cutoff
occurs. Each letter w j (1-j-x) on the path will cause a call to EditDist(j).
We use Ukkonen's algorithm to minimize row evaluations.
Suppose we have a misspelled word P=exsample and want all words with
mismatches. Figure 5 shows the index trie and some intermediate results
of the search. After evaluating D(P; ech), we find that entries on the third
column are all -2. According to observation II, no word W with the prefix
ech can have We reject word echo and continue traversing.
After evaluating D(P; enf), we know, once again, no word W with prefix enf
can have and therefore, there is no need to walk down this
subtrie. We cut off the subtrie. Since ech and enf share the same prefix e,
we copy the first column of ech when evaluating enf (observation I). After
evaluating path 3, we find accept the word. The
search stops after cutting at path 4, sa. Figure 5 shows some intermediate
results of the search.
Pattern String:
Search Path 2:
Search Path 3:
Search Path 4:
String Distance Action
exsample
ech
enf
example
sa
reject
cutoff
accept
cutoff
Depth First
e s
a
fho
c
ce ld
ample
x
a
le
Figure

5: Approximate Trie Search Example
4 Experimental Results
We built tries for five texts: (1) The King James' Bible retrieved from ak-
bar.cac.washington.edu, (2) Shakespeare's complete works provided by Oxford
University Press for NeXT Inc., (3) section one of UNIX manual pages
from Solbourne Computer Inc., (4) C source programs selected randomly
from a departmental teaching machine, and (5) randomly selected ftp file
names provided by Bunyip Information System. Sistrings start at any character
except the word boundary, such as blank and tab characters. Table 4
shows the sizes of the five texts and their index tries.
4.1 Search Time
We randomly picked up 5 substrings from each of the five texts, and then
searched for the substrings using both agrep [28] and our trie algorithm. Both
elapsed time and CPU time are measured on two 25MHz NeXT machines,
one with 28MB RAM and the other with 8MB RAM. Table 5 shows measured
times, averaged on the five substrings, in seconds.
The testing results show that our trie search algorithm significantly out-performs
agrep in exact match and approximate match with one error. For
the exact match, trie methods usually give search time proportional only to
the length of the search string. Our measurements show that trie search
times for exact match do not directly relate to the text size. It requires
few data transfers (only one search path), and therefore, is insensitive to the
RAM size.
Let ae(k) be the average trie search depth. It is the average number of
columns to be evaluated before assuring that k. It has been
proven that ae(k) ? k if k is less than the target string length, and
[24, 7]. For a complete trie, the worst case of a text trie, the trie search
algorithm can find all substrings with k mismatches in O(k j\Sigmaj k ) expected
time: there are j\Sigmaj k paths up to depth k, and each column of the DP table
has k rows. The time is independent of the trie size. In fact the trie algorithm
is better than the agrep for small k, but not for large k, because agrep scans
text linearly but the trie grows exponentially. For our measured texts, which
are relatively small, the trie search brings more data into RAM than agrep
When RAM size is larger than data size, measured CPU times are closer
to the elapsed times. Since each query is tested repeatedly, most of data (text
and trie) are cached in RAM, and therefore, the searches are CPU-bound.
However, for a smaller RAM size (or larger text data), the searches have to
wait for data to be transferred from secondary storage. Since agrep scans the
entire text, its search time is linearly proportional to the text size.
File names are different from the other tested texts. File names are all
distinct. Any two substrings resemble each other less, which helps
agrep to stop evaluation more quickly. This does not help the trie search
because it makes the trie shallow (toward a complete trie) and takes more
time to scan the top trie levels.
Extensions
Our trie search algorithm can be extended in various ways. For example,
spelling checkers are more likely to ask for the best matches, rather than
the words with a fixed number of errors. The optical character recognizers
may search for words with substitutions only. When searching for telephone
license numbers, postal codes, etc., users require not only penalties
for certain types of edit operations, but also a combination of the exact search
and the approximate search because they often remember some numbers for
sure. In text searching, patterns are more often expressed in terms of regular
expressions. Extensions described in this section (except Section 5.5) have
been discussed in [28]. We present them here using DP.
5.1 Best Match
In some applications, we do not know the exact number of errors before
a search. We want strings with the minimal number of mismatches, i.e.,
strings with 0-k mismatches and no other string in the text having k 0 !k
mismatches.
To use our algorithm, we define a preset k, which is a small number but
no less than the minimal distance, i.e., there exists a string, s, in the text
such that D(pattern; s) - k. A simple method to set k is to let s be an
arbitrary string in the text, and then set better way
is to search for the pattern using deletions (or insertions, or substitutions)
only. This is to traverse the trie by following the pattern string. Whenever
no subtrie corresponds to a character of the pattern, we skip the character
in the pattern and look for a subtrie for the next character, and so on. The
number of skipped characters will be used as an initial k.
During the traverse, we will have k
s is the path from the root to the leaf node. Whenever we have k ? k 0 , we set
clear the strings that have been found. For best match searching,
decreases monotonically.
5.2 Weighted Costs
The distances evaluated before are assumed to have cost 1 for any edit op-
eration. Sometimes, we may want to have a different cost. For example, to
have substitution costs at least the same as one deletion and one insertion,
or to disallow deletions completely.
To make edit operations cost differently, we need only to modify the
distance function. Let I, D, S and R be the costs of an insertion, a deletion,
a substitution, and a transposition respectively. We assume costs are all
To disallow an operation, say insertions, we set I = 1. As before,
Otherwise, we redefine
@
A
D, and
else
else
Furthermore, we may add a cost, C, for changing the case. For example,
for case insensitive searches, we set case sensitive searches, we
set We may even disallow case changes by setting
be checking the case difference, and let a - b mean that a and
b are of the same case. Now, we define, C ij
C else
, and replace:
else
else
The concept of changing cases can be extended even more generally. For
example, when searching a white page for telephone numbers, we don't want
an apartment number, such as 304B, to be recognized as a telephone number,
i.e., do not replace a character unless it is a digit to a digit. For the same
reason, we may not want to mix letters, digits and punctuation with each
other when searching for license plates, such as RMP-167, or postal codes,
such as H3A 2A7. For those applications, we can use above definitions for
but give a new interpretation of C. We will not elaborate them
here.
5.3 Combining Exact and Approximate Searches
We sometimes know in advance that only certain parts of the pattern may
have errors. For example, many spelling checkers may give no suggestions
for garantee. But suppose we knew the suffix rantee was spelled right. In
this case, we want to search part of the pattern exactly. By following agrep
standards [28], we denote this pattern as ga!rantee?. Characters inside a
!? cannot be edited using any one of the four operations.
To support both exact and approximate searches for the same pattern,
we need only modify I ij be a predicate
that determines whether p i is a member character inside an exact match !?.
Let function ? p i be a predicate that tells whether p i is the last character
inside a !?. The new definitions are:
I else
else
else
else
R P
else
By above definitions, string guarantees also matches ga!rantee? with
two insertions. To disallow insertions at the end of an exact match, we
introduce an anchor symbol, $ (borrowed from Unix standards). Pattern
ga!rantee?$ means that target strings must have the suffix rantee. What
needs to be changed is to set ?p i false when there is a
i.e., a pattern looks like In a similar way, we introduce another
anchor symbol, -, to prevent insertions at the beginning of an exact match.
For example, -!g?a!rantee?$ means that target strings must start with the
letter g and ended with the suffix rantee. This time, we set j p 0 true.
5.4 Approximate Regular Expression Search
The ability to match regular expressions with errors is important in prac-
tice. Regular expression matching and k-approximate string matching solve
different problems. They may overlap but do not coincide. For example, the
regular expression a#c, where # is a one-place wildcard, can be written as a
1-approximate match with substitutions and insertions on the second character
only. Baeza-Yates [5] proposed an search algorithm for the full regular
expression on tries.
In this section, we will extend our trie algorithm to deal with regular
expression operators with errors. However, the extension operators work
only for single characters, i.e., there is no group operator. For example, we
may search for a*b with mismatches, but not (ab)*. Searching tries for the
full regular expression with approximation is an open problem.
5.4.1 Alternative Operator
Suppose we want to find all postal codes, H3A 2A?, where ? is either 1, 3,
or 7. First, we introduce the notation, [137] (once again, borrowed from
Unix standard), to describe either 1, 3, or 7. Formally, operator [] defines a
set of alternative characters. Thus, H3A 2A7 matches pattern H3A 2A[137]
exactly; while H3A 2A4 matches the pattern with one mistake.
Substituting one character with a set of allowable characters can be easily
achieved by redefining the = and ' operators of Section 2 and Section 5.2
respectively. For pattern P 7 =H3A 2A[137], we have
as either 1= w j , or 3= w j , or 7= w j . In other
words, if p i is a set of allowable characters, matches one of
the characters defined by the [] operator. ' is the case insensitive version
of =.
As syntactic sugar (Unix standards), we may denote [a-z] for all lower
case letters, i.e., a range of characters; [-aeiou] for anything but vowels,
i.e., a complement of the listed characters; and . for all characters, i.e., the
wild card.
5.4.2 Kleen Star
The kleen star allows its associated characters to be deleted for free, or to
be replaced by more than one identical character for free. For example, ac,
abc, abbc and abbbc all match pattern ab*c exactly. a[0-9]*c means that
an unbounded number of digits can appear between a and c.
Let function \Lambdap i be a predicate which says there is a Kleen star associated
with the pattern character p i . To support the Kleen star operator, we need
only to change I ij and D ij . Remember, p i   means that we can delete p i at
no cost, and insert any number of at no cost. We now give
the new definition as follows:
I else
else
5.5 Counter
Our algorithm can also be extended to provide counters. Unlike a Kleen star,
e.g., ab*c, which means that unbounded number of bs can appear between
a and c, pattern ab?c says that only ac and abc match exactly. If we want
these strings abbc, abbbc, abbbbc and abbbbbc, i.e., two to five bs between a
and c, we can write the pattern as abbb?b?b?c, or abf2,5gc (Unix syntax).
To support counters, we need only to modify D ij since p? means character
can deleted for free. Let us define a function ?p i which says there is
a counter symbol, ?, associated with the pattern character p i . The new
definition is:
else
6 Dictionary Search
By a dictionary, we mean a text file which contains keywords only, i.e., a
set of strings that are pairwise distinguishable. For dictionary searches, we
are only interested in those keywords that relate to the pattern by some
measurements (in our case, the edit distance). The orders (or locations) of
those keywords are not important to us. For such applications, the text file
can be stored entirely in a trie structure. The trie in Figure 3 is a dictionary
trie. Experimental results in [22] show that dictionary trie sizes are about
50% of the file sizes for English words. In other words, we are providing
not only an algorithm for both exact and approximate searches, but also a
data structure for compressing the data up to 50%. Searches are done on the
structure without decompression operations.
Searching soundex codes [20] is an example of the dictionary search. By
replacing English words with their soundex codes and storing the codes in
the dictionary trie, we are able not only to search any given soundex code
efficiently (exact trie search) but also to reduce the soundex code size by half.
Searching an inverted file is another example of dictionary search. An
inverted file is a sorted list of keywords in a text. The trie structure keeps
the order of its keys. By storing keywords in the dictionary trie, we can either
search for the keywords or for their location. Furthermore, our trie algorithm
provides search methods for various patterns with or without mismatches.
7 Conclusion
Tries have been used to search for exact matches for a long time. In this
paper, we have expanded trie methods to solve the k approximate string
matching problem. Our approximate search algorithm finds candidate words
with k differences in a very large set of n words in O(k j\Sigmaj k ) expected worst
time. The search time is independent of n. No other algorithm which achieves
this time complexity is known.
Our algorithm searches a trie depth first with shortcuts. The smaller k
is, the more subtries will be cut off. When irrelevant subtries are
cut off, and this gives the exact string search in time proportional only to the
length of the string being sought. The algorithm can also be used to search
full regular expressions [3].
We have proposed a trie structure which uses two bits per node and
has no pointers. Our trie structure is designed for storing very large sets
of word strings on secondary storage. The trie is partitioned by pages and
neighboring nodes, such as parents, children and siblings, are clustered in
terms of pages. Pages are organized in a tree like structure and are searched
in time logarithmic the file size.
Our trie method outperforms agrep, as our results show, by an order of
magnitude for k=0, and by a factor of 4 for k=1. Only when k-2 does the
linear worst case performance of agrep begin to beat the trie method for the
moderately large documents measured.
8 Future Work
Spelling checkers based on searching minimal edit distance performs excellently
for typographic errors and for some phonetic errors. For example,
exsample to example has one difference, but sinary to scenery has three
differences. To deal with phonetic misspellings, we may follow Veronis's work
[25] by giving weights to edit operations based on phonetic similarity, or using
non-integer distances to obtain finer grained scores on both typographic
and phonetic similarities. Another solution is to follow the convention which
assumes no mistakes in the first two letters, or gives higher penalty for the
first few mistakes. Excluding the first few errors allows us to bypass many
subtries near the trie root. This not only gives quicker search time, but also
reduces the number of possible candidates. With a small set of candidate
words, we can impose a linear phonetic check.
Even with one difference, a short word, say of 2 letters, matches many
English words. There are more short words than long words. This type of
error is difficult to correct out of context.

Acknowledgments

This work was supported by the Canadian Networks of Centres of Excellence
(NCE) through the Institute of Robotics and Intelligent Systems (IRIS) under
projects B-3 and IC-2, and by the Natural Sciences and Engineering
Research Council of Canada under grant NSERC OGP0004365.



--R

The myriad virtues of suffix trees.
String searching algorithms.
Efficient text searching of regular expressions.
A new approach to text searching.
Fast and practical approximate string matching.
A fast string searching algorithm.
Approximate string matching in sublinear- expected time
A technique for computer detection and correction of spelling errors.
Efficient searching of text and pictures.
New indices for text: PAT trees and PAT arrays.
Approximate string matching.
An approximate string-matching algo- rithm
Fast pattern matching in strings.
Techniques for automatically correcting words in text.
Binary codes capable of correcting deletions
A space economical suffix tree construction algorithm.
Relational Information Systems.
Trie methods for representing text.

Patent Numbers
Multidimensional tries used for associative searching.
Trie Methods for Text and Spatial Data on Secondary Stor- age
String Searching Algorithms.
Finding approximate patterns in strings.
Computerized correction of phonographic errors.
The string-to-string correction problem
Linear pattern matching algorithms.
Fast text searching.
--TR

--CTR
Johan Rnnblom, High-error approximate dictionary search using estimate hash comparisons, SoftwarePractice & Experience, v.37 n.10, p.1047-1059, August 2007
Eike Schallehn , Kai-Uwe Sattler , Gunter Saake, Advanced grouping and aggregation for data integration, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
R. W. P. Luk, Time-Space Trade-Off Analysis of Morphic Trie Images, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1028-1032, November 2001
Kimmo Fredriksson, On-line Approximate String Matching in Natural Language, Fundamenta Informaticae, v.72 n.4, p.453-466, December 2006
Sreenivas Gollapudi , Rina Panigrahy, A dictionary for approximate string search and longest prefix search, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Liang Jin , Chen Li , Nick Koudas , Anthony K. H. Tung, Indexing mixed types for approximate retrieval, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Eike Schallehn , Kai-Uwe Sattler , Gunter Saake, Efficient similarity-based operations for data integration, Data & Knowledge Engineering, v.48 n.3, p.361-387, March 2004
Gonzalo Navarro , Ricardo Baeza-Yates , Joo Marcelo Azevedo Arcoverde, Matchsimile: a flexible approximate matching tool for searching proper names, Journal of the American Society for Information Science and Technology, v.54 n.1, p.3-15, January
Jung-Im Won , Sanghyun Park , Jee-Hee Yoon , Sang-Wook Kim, An efficient approach for sequence matching in large DNA databases, Journal of Information Science, v.32 n.1, p.88-104, February  2006
approximate matching;text search