New and faster filters for multiple approximate string matching.
We present three new algorithms for on-line multiple string matching allowing errors. These are extensions of previous algorithms that search for a single pattern. The average running time achieved is in all cases linear in the text size for moderate error level, pattern length, and number of patterns. They adapt (with higher costs) to the other cases. However, the algorithms differ in speed and thresholds of usefulness. We theoretically analyze when each algorithm should be used, and show their performance experimentally. The only previous solution for this problem allows only one error. Our algorithms are the first to allow more errors, and are faster than previous work for a moderate number of patterns (e.g. less than 50-100 on English text, depending on the pattern length).
Introduction
Approximate string matching is one of the main problems in classical string algorithms, with
applications to text searching, computational biology, pattern recognition, etc. Given a text T 1::n
of length n and a pattern P 1::m of length m (both sequences over an alphabet \Sigma of size oe), and a
maximal number of errors allowed, m, we want to find all text positions where the pattern
matches the text with up to k errors. Errors can be substituting, deleting or inserting a character.
We use the term "error level" to refer to
In this paper we are interested in the on-line problem (i.e. the text is not known in advance),
where the classical solution for a single pattern is based on dynamic programming and has a running
time of O(mn) [26].
In recent years several algorithms have improved the classical one [22]. Some improve the worst
or average case by using the properties of the dynamic programming matrix [30, 11, 16, 31, 9].
Others filter the text to quickly eliminate uninteresting parts [29, 28, 10, 14, 24], some of them
being "sublinear" on average for moderate ff (i.e. they do not inspect all the text characters).
Yet other approaches use bit-parallelism [3] in a computer word of w bits to reduce the number of
operations [33, 35, 34, 6, 19].
The problem of approximately searching a set of r patterns (i.e. the occurrences of anyone of
them) has been considered only recently. This problem has many applications, for instance
This work has been supported in part by FONDECYT grant 1990627.
ffl Spelling: many incorrect words can be searched in the dictionary at a time, in order to find
their most likely variants. Moreover, we may even search the dictionary of correct words in
the "text" of misspelled words, hopefully at much less cost.
ffl Information retrieval: when synonym or thesaurus expansion is done on a keyword and the
text is error-prone, we may want to search all the variants allowing errors.
Batched queries: if a system receives a number of queries to process, it may improve efficiency
by searching all them in a single pass.
ffl Single-pattern queries: some algorithms for a single pattern allowing errors (e.g. pattern
partitioning [6]) reduce the problem to the search of many subpatterns allowing less errors,
and they benefit from multipattern search algorithms.
A trivial solution to the multipattern search problem is to perform r searches. As far as we
know, the only previous attempt to improve the trivial solution is due to Muth & Manber [17], who
use hashing to search many patterns with one error, being efficient even for one thousand patterns.
In this work, we present three new algorithms that are extensions of previous ones to the
case of multiple search. In Section 2 we explain some basic concepts necessary to understand
the algorithms. Then we present the three new techniques. In Section 3 we present "automaton
which extends a bit-parallel simulation of a nondeterministic finite automaton
In Section 4 we present "exact partitioning", that extends a filter based on exact
searching of pattern pieces [7, 6, 24]. In Section 5 we present "counting", based on counting
pattern letters in a text window [14]. In Section 6 we analyze our algorithms and in Section 7 we
compare them experimentally. Finally, in Section 8 we give our conclusions. Some detailed analyses
are left for Appendices A and B.
Although [17] allows searching for many patterns, it is limited to only one error. Ours are the
first algorithms for multipattern matching allowing more than one error. Moreover, even for one
error, we improve [17] when the number of patterns is not very large (say, less than 50-100 on
English text, depending on the pattern length). Our multipattern extensions improve over their
sequential counterparts (i.e. one separate search per pattern using the base algorithm) when the
error level is not very high (about ff  0:4 on English text). The filter based on exact searching
is the fastest for small error levels, while the bit-parallel simulation of the NFA adapts better to
more errors on relatively short patterns.
Previous partial and preliminary versions of this work appeared in [5, 20, 21].
2 Basic Concepts
We review in this section some basic concepts that are used in all the algorithms that follow. In
the paper S i denotes the i-th character of string S (being S 1 the first character), and S i::j stands
for the substring S i S i+1 :::S j . In particular, if ffl, the empty string.
2.1 Filtering Techiques
All the multipattern search algorithms that we consider in this work are based in the concept of
filtering, and therefore it is useful to define it here.
Filtering is based on the fact that it is normally easier to tell that a text position does not
match than to ensure that it matches. Therefore, a filter is a fast algorithm that checks for a
simple necessary (though not sufficient) condition for an approximate match to occur. The text
areas that do not satisfy the necessary condition can be safely discarded, and a more expensive
algorithm has to be run on the text areas that passed the filter.
Since the filters can be much faster than approximate searching algorithms, filtering algorithms
can be very competitive (in fact, they dominate on a large range of parameters). The performance
of filtering algorithms, however, is very sensitive to the error level ff. Most filters work very well
on low error levels and very bad with more errors. This is related with the amount of text that the
filter is able to discard. When evaluating filtering algorithms, it is important not only to consider
time efficiency but also their tolerance to errors.
A term normally used when referring to filters is "sublinearity". It is said that a filter is sublinear
when it does not inspect all the characters of the text (like the Boyer-Moore [8] algorithms for exact
searching, which can be at best O(n=m)).
Throughout this work we make use of the two following lemmas to derive filtering conditions.
with at most k errors, and concatenation of
sub-patterns), then some substring of S matches at least one of the p i 's, with at most bk=jc errors.
Proof: Otherwise, the best match of each p i inside S has at least bk=jc errors. An
occurrence of P involves the occurrence of each of the p i 's, and the total number of errors in the
occurrences is at least the sum of the errors of the pieces. But here, just summing up the errors of
all the pieces we have more than errors and therefore a complete match is not possible.
Notice that this does not even consider that the matches of the p i must be in the proper order, be
disjoint, and that some deletions in S may be needed to connect them.
In general, one can filter the search for a pattern of length m with k errors by the search of j
subpatterns of length m=j with k=j errors. Only the text areas surrounding occurrences of pieces
must be checked for complete matches.
An important particular case of Lemma 1 arises when one considers since in this case
some pattern piece appears unaltered (zero errors).
Lemma 2: [32] If there are i  j such that ed(T i::j ; P )  k, then T j \Gammam+1::j includes at least m \Gamma k
characters of P .
Proof: Suppose the opposite. If then we observe that there are less than
characters of P in T i::j . Hence, more than k characters must be deleted from P to match the text.
we observe that there are more than k characters in T i::j that are not in P , and hence
we must insert more than k characters in P to match the text. A contradiction in both cases.
Note that in case of repeated characters in the pattern, they must be counted as different
occurrences. For example, if we search "aaaa" with one error in the text, the last four letters of
each occurrence must include at least three a's.
simplification of that in [32]) says essentially that we can design a filter for approximate
searching based on finding enough characters of the pattern in a text window (without
regarding their ordering). For instance, the pattern "survey" cannot appear with one error in the
text window "surger" because there are not five letters of the pattern in the text. However, the
filter cannot discard the possibility that the pattern appears in the text window "yevrus".
2.2 Bit-Parallelism
Bit-parallelism is a technique of common use in string matching [3]. It was first proposed in [2, 4].
The technique consists in taking advantage of the intrinsic parallelism of the bit operations inside
a computer word. By using cleverly this fact, the number of operations that an algorithm performs
can be cut down by a factor of at most w, where w is the number of bits in the computer word.
Since in current architectures w is 32 or 64, the speedup is very significant in practice (and
improves with technological progress). In order to relate the behavior of bit-parallel algorithms
to other works, it is normally assumed that dictated by the RAM model of
computation. We prefer, however, to keep w as an independent value.
Some notation we use for bit-parallel algorithms is in order. We denote as b ' :::b 1 the bits of a
mask of length ', which is stored somewhere inside the computer word. We use C-like syntax for
operations on the bits of computer words, e.g. "j" is the bitwise-or and "!!" moves the bits to
the left and enters zeros from the right, e.g. b m b We can also
perform arithmetic operations on the bits, such as addition and subtraction, which operates the
bits as if they formed a number. For instance, b ' :::b x
We explain now the first bit-parallel algorithm, since it is the basis of much of which follows
in this work. The algorithm searches a pattern in a text (without errors) by parallelizing the
operation of a non-deterministic finite automaton that looks for the pattern. Figure 1 illustrates
this automaton.
l
a h a

Figure

1: Nondeterministic automaton that searches "aloha" exactly.
This automaton has m+ 1 states, and can be simulated in its non-deterministic form in O(mn)
time. The Shift-Or algorithm achieves O(mn=w) worst-case time (i.e. optimal speedup). Notice
that if we convert the non-deterministic automaton to a deterministic one to have O(n) search
time, we get an improved version of the KMP algorithm [15]. However, KMP is twice as slow for
The algorithm first builds a table B[ ] which for each character c stores a bit mask
The mask B[c] has the bit b i in zero if and only if P c. The state of the search is kept in a
machine word matches the end of the text read up to
now (i.e. the state numbered i in Figure 1 is active). Therefore, a match is reported whenever dm
is zero.
D is set to all ones originally, and for each new text character T j , D is updated using the formula
The formula is correct because the i-th bit is zero if and only if the (i \Gamma 1)-th bit was zero
for the previous text character and the new text character matches the pattern at position i. In
other words, T j It is possible to
relate this formula to the movement that occurs in the non-deterministic automaton for each new
text character: each state gets the value of the previous state, but this happens only if the text
character matches the corresponding arrow.
For patterns longer than the computer word (i.e. m ? w), the algorithm uses dm=we computer
words for the simulation (not all them are active all the time). The algorithm is O(mn=w) worst
case time, and the preprocessing is O(m On average, the algorithm is
O(n) even when m ? w, since only the first O(1) states of the automaton have active states on
average (and hence the first O(1) computer words need to be updated on average).
It is easy to extend Shift-Or to handle classes of characters. In this extension, each position
in the pattern matches with a set of characters rather than with a single character. The classical
string matching algorithms are not so easily extended. In Shift-Or, it is enough to set the i-th bit
of B[c] for every c 2 P i (P i is a set now). For instance, to search for "survey" in case-insensitive
form, we just set the first bit of B["s"] and of B["S"] to "match" (zero), and the same with the rest.
Shift-Or can also search for multiple patterns (where the complexity is O(mn=w) if we consider
that m is the total length of all the patterns) by arranging many masks B and D in the same
machine word. Shift-Or was later enhanced [34] to support a larger set of extended patterns and
even regular expressions. Recently, in [25], Shift-Or was combined with a sublinear string matching
algorithm, obtaining the same flexibility and an efficiency competitive against the best classical
algorithms.
Many on-line text algorithms can be seen as implementations of clever automata (classically, in
their deterministic form). Bit-parallelism has since its invention became a general way to simulate
simple non-deterministic automata instead of converting them to deterministic. It has the advantage
of being much simpler, in many cases faster (since it makes better usage of the registers of the
computer word), and easier to extend to handle complex patterns than its classical counterparts.
Its main disadvantage is the limitations it imposes with regard to the size of the computer word.
In many cases its adaptations to cope with longer patterns are not so efficient.
2.3 Bit-parallelism for Approximate Pattern Matching
We present now an application of bit-parallelism to approximate pattern matching, which is especially
relevant for the present work.
Consider the NFA for searching "patt" with at most errors shown in Figure 2. Every
row denotes the number of errors seen. The first one 0, the second one 1, and so on. Every column
represents matching the pattern up to a given position. At each iteration, a new text character is
considered and the automaton changes its states. Horizontal arrows represent matching a character
(they can only be followed if the corresponding match occurs). All the others represent errors, as
they move to the next row. Vertical arrows represent inserting a character in the pattern (since they
advance in the text and not in the pattern), solid diagonal arrows represent replacing a character
(since they advance in the text and the pattern), and dashed diagonal arrows represent deleting a
character of the pattern (since, as ffl-transitions, they advance in the pattern but not in the text).
The loop at the initial state allows considering any character as a potential starting point of a
match. The automaton accepts a character (as the end of a match) whenever a rightmost state
is active. Initially, the active states at row i (i 2 0::k) are those at the columns from 0 to i, to
represent the deletion of the first i characters of the pattern P 1::m .
a
a
a
no errors

Figure

2: An NFA for approximate string matching. We show the active states after reading the
text "pait".
An interesting application of bit-parallelism is to simulate this automaton in its nondeterministic
form. A first approach [34] obtained O(kdm=wen) time, by packing each automaton row in a
machine word and extending the Shift-Or algorithm to account for the vertical and diagonal arrows.
Note that even if all the states fit in a single machine word, the k have to be sequentially
updated because of the ffl-transitions. The same happens in the classical dynamic programming
algorithm [26], which can be regarded as a column-wise simulation of this NFA.
In this paper we are interested in a more recent simulation technique [6], where we show that by
packing diagonals of the automaton instead of rows or columns all the new values can be computed
in one step if they fit in a computer word. We give a brief description of the idea.
Because of the ffl-transitions, once a state in a diagonal is active, all the subsequent states in that
diagonal become active too, so we can define the minimal active row of each diagonal, D i (diagonals
are numbered by looking the column they start at, e.g. D 1 and D 2 are enclosed in dotted lines
in

Figure

2). The new values for D i (i after we read a new text character c can be
computed by
where it always holds
and we report a match whenever Dm\Gammak  k. The formula for
accounts for replacements, insertions and matches, respectively. Deletions are accounted for by
keeping the minimum active row. All the interesting matches are caught by considering only the
diagonals D 1 :::D m\Gammak .
We use bit-parallelism to represent the D i 's in unary. Each one is hold in k (plus an
overflow bit) and stored sequentially inside a bit mask D. Interestingly, the effect is the same if we
read the diagonals bottom-up and exchange 0 $ 1, with each bit representing a state of the NFA.
The update formula can be seen either as an arithmetic implementation of the previous formula in
unary or as a logical simulation of the flow of bits across the arrows of the NFA.
As in Shift-Or, a table of (m bits long) masks b[ ] is built representing match or mismatch
against the pattern. A table B[c] is built by mapping the bits of b[ ] to their appropriate positions
inside D. Figure 3 shows how the states are represented inside the masks D and B.
separator separator
final state
t a p
t t a

Figure

3: Bit-parallel representation of the NFA of Figure 2.
This representation requires k+2 bits per diagonal, so the total number of bits is (m \Gamma k)(k+2).
If this number of bits does not exceed the computer word size w, the update can be done in O(1)
operations. The resulting algorithm is linear and very fast in practice.
For our purposes, it is important to realize that the only connection between the pattern and
the algorithm is given by the b[ ] table, and that the pattern can use classes of characters just as in
the Shift-Or algorithm. We use this property next to search for multiple patterns.
3 Superimposed Automata
In this section we describe an approach based on the bit-parallel simulation of the NFA just described

Suppose we have to search r patterns . We are interested in the occurrences of any one
of them, with at most k errors. We can extend the previous bit-parallelism approach by building
the automaton for each one, and then "superimpose" all the automata.
Assume that all patterns have the same length (otherwise, truncate them to the shortest one).
Hence, all the automata have the same structure, differing only in the labels of the horizontal
arrows.
The superimposition is defined as follows: we build the b[ ] table for each pattern, and then take
the bitwise-and of all the tables (recall that 0 means match and 1 means mismatch). The resulting
table matches at position i with the i-th character of any of the patterns. We then build the
automaton as before using this table.
The resulting automaton accepts a text position if it ends an occurrence of a much more relaxed
pattern with classes of characters, namely
for example, if the search is for "patt" and "wait", as shown in Figure 4, the string "pait" is
accepted with zero errors.
or w
no errors
errors
a t
a t
t or i
a t
t or i
t or i
or w
or w

Figure

4: An NFA to filter the search for "patt" and "wait".
For a moderate number of patterns, the filter is strict enough at the same cost of a single search.
Each occurrence reported by the automaton has to be verified for all the involved patterns (we use
the single-pattern automaton for this step). That is, we have to retraverse the last m+
characters to determine if there is actually an occurrence of some of the patterns.
If the number of patterns is too large, the filter will be too relaxed and will trigger too many
verifications. In that case, we partition the set of patterns into groups of r 0 patterns each, build
the automaton of each group and perform dr=r 0 e independent searches. The cost of this search
is O(r=r 0 n), where r 0 is small enough to make the cost of verifications negligible. This r 0 always
exists, since for r we have a single pattern per automaton and no verification is needed.
When grouping, we use the heuristic of sorting the patterns and packing neighbors in the same
group, trying to have the same first characters.
3.1 Hierarchical Verification
The simplest verification alternative (which we call "plain") is that, once a superimposed automaton
reports a match, we try the individual patterns one by one in the candidate area. However, a smarter
verification technique (which we call hierarchical) is possible.
Assume first that r is a power of two. Then, when the automaton reports a match, run two
new automata over the candidate area: one which superimposes the first half of the patterns and
another with the second half. Repeat the process recursively with each of the two automata that
finds again a match. At the end, the automata will represent single patterns and if they find a
match we know that their patterns have been really found (see Figure 5). Of course the automata
for the required subsets of patterns are all preprocessed. Since they correspond to the internal
nodes of a binary tree of r leaves, they are so the space and preprocessing cost does
not change. If r is not a power of two then one of the halves may have one more pattern than the
other.2424

Figure

5: The hierarchical verification method for 4 patterns. Each node of the tree represents a
check (the root represents in fact the global filter). If a node passes the check, its two children are
tested. If a leaf passes the check, its pattern has been found.
The advantage of hierarchical verification is that it can remove a number of candidates from
consideration in a single test. Moreover, it can even find that no pattern has really matched before
actually checking any specific pattern (i.e. it may happen that none of the two halves match
in a spurious match of the whole group). The worst-case overhead over plain verification is just
a constant factor, that is, twice as many tests over the candidate area of r). On
average, as we show later analytically and experimentally, hierarchical verification is by far superior
to plain verification.
3.2 Automaton Partitioning
Up to now we have considered short patterns, whose NFA fit into a computer word. If this is not
the case (i.e. (m we partition the problem. In this subsection and the next we
adapt the two partitioning techniques described in [6].
The simplest technique to cope with a large automaton is to use a number of machine words
for the simulation. The idea is as follows: once the (large) automata have been superimposed,
we partition the superimposed automaton into a matrix of subautomata, each one fitting in a
computer word. Those subautomata behave slightly differently than the simple one, since they
must propagate bits to their neighbors. Figure 6 illustrates.
Once the automaton is partitioned, we run it over the text updating its subautomata. Each
step takes time proportional to the number of cells to update, i.e. O(k(m \Gamma k)=w). Observe,
however, that it is not necessary to update all the subautomata, since those on the right may not
have any active state. Following [31], we keep track of up to where we need to update the matrix
of subautomata, working only on the "active" cells.
Information flow
Affected area000000000111111111111111111000111111 I rows
J columns
c
r

Figure

large NFA partitioned into a matrix of I \Theta J computer words, satisfying (' r +1)' c  w.
3.3 Pattern Partitioning
This technique is based on Lemma 1 of Section 2.1. We can reduce the size of the problem if
we divide the pattern in j parts, provided we search all the sub-patterns with bk=jc errors. Each
match of a sub-pattern must be verified to determine if it is in fact a complete match.
To perform the partition, we pick the smallest j such that the problem fits in a single computer
word (i.e. (dm=je w). The limit of this method is reached for
since in that case we search with zero errors. The algorithm for this case is qualitatively different
and is described in Section 4.
We divide each pattern in j subpatterns as evenly as possible. Once we partition all the r
patterns, we are left with j \Theta r subpatterns to be searched with bk=jc errors. We simply group
them as if they were independent patterns to search with the general method. The only difference
is that, after determining that a subpattern has appeared, we have to verify its complete pattern.
Another kind of hierarchical verification, which we call "hierarchical piece verification", is applied
in this case too. As shown in [23, 24], the single-pattern algorithm can verify hierarchically
whether the complete pattern matches given that a piece matches (see Figure 7). That is, instead
of checking the complete pattern we check the concatenation of two pieces containing the one
that matched, and if it matches then we check the concatenation of four pieces, and so on. This
works because Lemma 1 applies at each level of the tree of Figure 7. The method is orthogonal to
our hierarchical verification idea because hierarchical piece verification works bottom-up instead of
top-down and operates on pieces of the pattern rather than on sets of patterns.
As we are using our hierarchical verification on the sets of pattern pieces to determine which
piece matched given that a superimposition of them matched, we are coupling two different hierarchical
verification techniques in this case: we first use our new mechanism to determine which piece
matched from the superimposed group and then use hierarchical piece verification to determine the
occurrence of the complete pattern the piece belongs to. Figure 8 illustrates the whole process.
aaabbbcccddd
aaabbb cccddd
ccc ddd
bbb
aaa

Figure

7: The hierarchical piece verification method for a pattern split in 4 parts. The boxes
(leaves) are the elements which are actually searched, and the root represents the whole pattern.
At least one pattern at each level must match in any occurrence of the complete pattern. If the
bold box is found, all the bold lines may be verified.
p22
p22
p22
each one is
split in 4
3 pieces to search
superimposed groups
the pieces are arranged in
hierarchical verif.
p22 is found
and searched
hierarchical piece verif.
P2 is finally found

Figure

8: The whole process of pattern partitioning with hierarchical verifications.
Partitioning into Exact Searching
This technique (called "exact partitioning" for short) is based on a single-pattern filter which
reduces the problem of approximate searching to a problem of multipattern exact searching. The
algorithm first appeared in [34], and was later improved in [7, 6, 24]. We first present the single-
pattern version and then our extension to multiple patterns.
4.1 A Filter Based on Exact Searching
A particular case of Lemma 1 shows that if a pattern matches a text position with k errors, and we
split the pattern in k+1 pieces, then at least one of the pieces must be present with no errors in each
occurrence (this is a folklore property which has been used several times [34, 18, 12]). Searching
with zero errors leads to a completely different technique.
Since there are efficient algorithms to search for a set of patterns exactly, we partition the
pattern in k similar length), and apply a multipattern exact search for the pieces.
Each occurrence of a piece is verified to check if it is surrounded by a complete match. If there are
not too many verifications, this algorithm is extremely fast.
From the many algorithms for multipattern search, an extension of Sunday's algorithm [27] gave
us the best results. We build a trie with the sub-patterns. From each text position we search the
text characters into the trie, until a leaf is found (match) or there is no path to follow (mismatch).
The jump to the next text position is precomputed as the minimum of the jumps allowed in each
sub-pattern by the Sunday algorithm.
As in [24], we use the same technique for hierarchical piece verification of a single pattern
presented in Section 3.3.
4.2 Searching Multiple Patterns
Observe that we can easily add more patterns to this scheme. Suppose we have to search for r
patterns We cut each one into search in parallel for all the r(k
pieces. When a piece is found in the text, we use a classical algorithm to verify its pattern in the
candidate area.
Note an important difference with superimposed automata. In this multipattern search we know
which piece has matched. This is not the case in superimposed automata, where not only we do
not know which piece matched, but it is even possible that no piece has really matched. The work
to determine which is the matching piece (carried out by hierarchical verification in superimposed
automata) is not necessary here. Moreover, we only detect real matches, so there are no more
matches in the union of patterns than the sum of the individual matches.
Therefore, there is no point in separating the search for the r(k in groups. The
only reason to superimpose less patterns is that the shifts of the Sunday algorithm are reduced as
the number of patterns grow, but as we show in the experiments, this never justifies in practice
splitting one search into two.
5 A Counting Filter
We present now a filter based on counting letters in common between the pattern and a text window.
This filter was first presented in [14] (a simple variant of [13]), but we use a slightly different version
here. Our variant uses a fixed-size instead of variable-size text window (a possibility already noted
in [32]), which makes it better suited for parallelization. We first explain the single-pattern filter
and then extend it to handle many patterns using bit-parallelism.
5.1 A Simple Counter
This filter is based in Lemma 2 of Section 2.1. It passes over the text examining an m-letters
long window. It keeps track of how many characters of P are present in the current text window
(accounting for multiplicities too). If, at a given text position j, more characters of P are
in the window T j \Gammam+1::j , the window area is verified with a classical algorithm.
We implement the filtering algorithm as follows. We keep a counter count of pattern characters
appearing in the text window. We also keep a table A[ ] where, initially, the number of times that
each character c appears in P is kept in A[c]. Throughout the algorithm, each entry A[c] indicates
how many occurrences of c can still be taken as belonging to P . For example, if 'h' appears once
in P , we count only one of the 'h's of the text window as belonging to P . When A[c] is negative,
it means that c must exit the text window \GammaA[c] times before we take it again as belonging to P .
For example, if we run the pattern "aloha" over the text "aaaaaaaa", it will hold
and the value of the counter will be 2. This is independent on k.
To advance the window, we must include the new character T j+1 and exclude the last character,
To include the new character, we subtract one from A[T j+1 ]. If it was greater than zero
before being decremented, it is because the new character T j+1 is in P , so we increment count. To
exclude the old character T j \Gammam+1 , we add one to A[T j \Gammam+1 ]. If its is greater than zero after being
incremented, it is because T j \Gammam+1 was considered to be in P , so we decrement count. Whenever
count reaches we verify the preceding area.
As can be seen, the algorithm is not only linear (excluding verifications), but the number of
operations per character is very small.
5.2 Keeping Many Counters in Parallel
To search r patterns in the same text, we use bit-parallelism to keep all the counters in a single
machine word. We must do that for the A[ ] table and for count.
The values of the entries of A[ ] lie in the range [\Gammam::m], so we need exactly
1)e bits to store them. This is also enough for count, since it is in the range [0::m]. Hence, we can
pack patterns of length m in a single search (recall that w
is the number of bits in the computer word). If the patterns have different lengths, we can either
truncate them to the shortest length or use a window size of the longest length. If we have more
patterns, we must divide the set in subsets of maximal size and search each subset separately. We
focus our attention on a single subset now.
The algorithm simulates the simple one as follows. We have a table MA[ ] that packs all the
tables. Each entry of MA[ ] is divided in bit areas of length ' + 1. In the area of the machine
word corresponding to each pattern, we store its normal A[ ] value, set to 1 the most significant bit
of the area, and subtract 1 (i.e. we store in the algorithm, we have to add or
subtract 1 to all A[ ]'s, we can easily do it in parallel without causing overflow from an area to the
next. Moreover, the corresponding A[ ] value is not positive if and only if the most significant bit
of the area is zero.
We have also a parallel counter Mcount, where the areas are aligned with MA[ ]. It is initialized
by setting to 1 the most significant bit of each area and then subtracting at each one, i.e. we
store Later, we can add or subtract 1 in parallel without causing overflow. Moreover,
the window must be verified for a pattern whenever the most significant bit of its area reaches 1.
The condition can be checked in parallel, but when some of the most significant bits reach 1, we
need to sequentially check which one it was.
Finally, observe that the counters that we want to selectively increment or decrement correspond
exactly to the MA[ ] areas that have a 1 in their most significant bit (i.e. those whose A[ ] value
is positive). This allows an obvious bit mask-shift-add mechanism to perform this operation in
parallel on all the counters. Figure 9 illustrates.
Mcount
MA [a]
MA [l]
MA [o]
MA [h]
MA [e]
count  m\Gammak ? (false)

Figure

9: The bit-parallel counters. The example corresponds to the pattern "aloha" searched with
1 error and the text window "hello". The A values are A[ 0 a
6 Analysis
We are interested in the complexity of the presented algorithms, as well as in the restrictions that
ff and r must satisfy for each mechanism to be efficient in filtering most of the unrelevant part of
the text.
To this effect, we define two concepts. First, we say that a multipattern search algorithm is
optimal if it searches r patterns in the same time it takes to search one pattern. If we call C n;r the
cost to search r patterns in a text of size n, then an algorithm is optimal if C
we say that a multipattern search algorithm is useful if it searches r patterns in less than the time
it takes to search them one by one with the corresponding sequential algorithm, i.e. C n;r ! r C n;1 .
As we work with filters, we are interested in the average case analysis, since in the worst case none
is useful.
We compare in Table 1 the complexities and limits of applicability of all the algorithms. Muth
& Manber are included for completeness. The analysis leading to these results is presented later in
this section.
Algorithm Complexity Optimality Usefulness
Simple Superimp. r
oe
Automaton Part. ffm 2 r
oe
Pattern Part. mr
oe
w(1\Gammaff)
Part. Exact Search
ffoe 1=ff
log oe (rm)+\Theta(log oe log oe (rm))
log oe m+\Theta(log oe log oe m)
Counting r log m
Muth & Manber mn

Table

1: Complexity, optimality and limit of applicability for the different algorithms.
We present in Figure 10 a schematical representation of the areas where each algorithm is the
best in terms of complexity. We show later how the experiments match those figures.
Exact partitioning is the fastest choice in most reasonable scenarios, for the error levels where
it can be applied. First, it is faster than counting for m= log m ! ffoe 1=ff =w, which does not
hold asymptotically but holds in practice for reasonable values of m. Second, it is faster
than superimposing automata for min(
which is true in most
practical cases.
ffl The only algorithm which can be faster than exact partitioning is that of Muth & Manber
[17], namely for r ? ffoe 1=ff . However, it is limited to
ffl For increasing m, counting is asymptotically the fastest algorithm since its cost grows as
O(log m) instead of O(m) thanks to its optimal use of the bits of the computer word. However,
its applicability is reduced as m grows, being useless at the point where it wins over exact
partitioning.
ffl When the error level is too high for exact partitioning, superimposing automata is the only
remaining alternative. Automaton partitioning is better for m
while pattern partitioning
is asymptotically better. Both algorithms have the same limit of usefulness, and for
higher error levels no filter can improve over a sequential search.
Pattern
Partitioning
Partitioning
Automaton
Partitioning into Exact Search
oe
1= log oe m
ff
oe
1= log oe m
Partitioning into Exact Search
Superimposed Automata
r
Muth-Manber
ffoe 1=ff
ff

Figure

10: The areas where each algorithm is better, in terms of ff, m and r. In the left plot
(varying m), we have assumed a moderate r (i.e. less than 50).
6.1 Superimposed Automata
Suppose that we search r patterns. As explained before, we can partition the set in groups of r 0
patterns each, and search each group separately (with its r 0 automata superimposed). The size of
the groups should be as large as possible, but small enough for the verifications to be not significant.
We analyze which is the optimal value for r 0 and which is the complexity of the search.
In [6] we prove that the probability of a given text position matching a random pattern with
error level ff is O(fl m ), where It is also proved that
oe, and experimentally shown that this holds very precisely in practice if we replace e
by 1.09. In fact, a very abrupt phenomenon occurs, since the matching probability is very low for
oe and very high otherwise.
In this formula, 1=oe stands for the probability of a character crossing a horizontal edge of the
automaton (i.e. the probability of two characters being equal). To extend this result, we note that
we have r 0 characters on each edge now, so the above mentioned probability is
which is smaller than r 0 =oe. We use this upper bound as a pessimistic approximation (which stands
for the case of all the r 0 characters being different, and is tight for r 0 !! oe).
As the single-pattern algorithm is O(n) time, the multipattern algorithm is optimal on average
whenever the total cost of verifications is O(1) per character. Since each verification costs O(m)
(because we use a linear-time algorithm on an area of length O(m)), we need that the
total number of verifications performed is O(1=m) per character, on average. If we used the plain
verification scheme, this would mean that the probability that a superimposed automaton matches
a text position should be O(1=(mr)), as we have to perform r verifications.
If hierarchical verification is not used we have that, as r increases, matching becomes more
probable (because it is easier to cross a horizontal edge of the automaton) and it costs more
(because we have to check the r patterns one by one). This results in two different limits on the
maximum allowable r, one for each of the two facts just stated. The limit due to the increased cost
of each verification is more stringent than that of increased matching probability.
The resulting analysis without hierarchical verification is very complex and is omitted here
because hierarchical verification yields considerably better results and a simpler analysis. As we
show in Appendix A, the average cost to verify a match of the superimposed automaton is O(m)
when hierarchical verification is used, instead of the O(rm) cost of plain verification. That is, the
cost does not grow as the number of patterns increases.
Hence, the only limit that prevents us from superimposing all the r patterns is that the matching
probability becomes higher. That is, if ff
r=oe, then the matching probability is too high
and we will spend too much time verifying almost all text positions. On the other hand, we can
superimpose as much as we like before that limit is reached. This tells that the best r (which we
call r   ) is the maximum one not reaching the limit, i.e.
r
(1)
Since we partition in sets small enough to make the verifications not significant, the cost is
simply O(r=r   n)
This means that the algorithm is optimal for (taking the error level as a constant), or
alternatively ff
r=oe. On the other hand, for
oe, the cost is O(rn), not better
than the trivial solution (i.e. r  hence no superimposition occurs and the algorithm is not
useful). Figure 11 illustrates.
Automaton Partitioning: the analysis for this case is similar to the simple one, except because
each step of the large automaton takes time proportional to the total number of subautomata, i.e.
rts
pr
oe
r ff
r
oe

Figure

11: Behavior of superimposed automata. On the left, the cost increases linearly with r, with
slope depending on ff. On the right, the cost of a parallel search (t p ) approaches r single searches
In fact, this is a worst case since on average not all cells are active, but we use
the worst case because we superimpose all the patterns we can until the worst case of the search is
almost reached. Therefore, the cost formula is
rn
This is optimal for constant ff), or alternatively for ff
r=oe. It is useful
for ff
oe.
Pattern Partitioning: we have now jr patterns to search with bk=jc errors. The error level is
the same for subproblems (recall that the subpatterns are of length m=j).
To determine which piece matched from the superimposed group, we pay O(m) independently
of the number of pieces superimposed (thanks to the hierarchical verification). Hence the limit for
our grouping is given by Eq. (1). In both the superimposed and in the single-pattern algorithm,
we also pay to verify if the match of the piece is part of a complete match. As we show in [23], this
cost is negligible for ff
oe, which is less strict than the limit given by Eq. (1).
As we have jr pieces to search, we need an analytical expression for j. Since j is just large
enough so that the subpatterns fit in a computer word,
where d(w; ff) can be shown to be O(1=
w) by maximizing it in terms of ff (see [23]).
Therefore, the complexity is
oe
rn
On the other hand, the search cost of the single-pattern algorithm is O(jrn). With respect to
the simple algorithm for short patterns, both costs have been multiplied by j, and therefore the
limits for optimality and usefulness are the same.
If we compare the complexities of pattern versus automaton partitioning, we have that pattern
partitioning is better for k ?
w. This means that for constant ff and increasing m, pattern
partitioning is asymptotically better.
6.2 Partitioning into Exact Searching
In [6] we analyze this algorithm as follows. Except for verifications, the search time can be made
O(n) in the worst case by using an Aho-Corasick machine [1], and O(ffn) in the best case if we use
a multipattern Boyer-Moore algorithm. This is because we search pieces of length m=(k+1)  1=ff.
We are interested in analyzing the cost of verifications. Since we cut the pattern in k +1 pieces,
they are of length bm=(k 1)e. The probability of each piece matching is at most
1=oe bm=(k+1)c . Hence, the probability of any piece matching is at most (k
We can easily extend that analysis to the case of multiple search, since we have now r(k
pieces of the same length. Hence, the probability of verifying is r(k We check
the matches using a classical algorithm such as dynamic programming. Note that in this case we
know which pattern to verify, since we know which piece matched. As we show in [23], the total
verification cost if the pieces are of length ' is O(' 2 ) (in our case, Hence, the search
cost is
O
ffoe 1=ff
where the "1" must be changed to "ff" if we consider the best case.
We consider optimality and usefulness now. An optimal algorithm should pay O(n) total search
time, which holds for
The algorithm is always useful, since it searches at the same cost independently on the number
of patterns, and the number of verifications triggered is exactly the same as if we searched each
pattern separately. However, if ff ? 1=(log oe m+ \Theta(log oe log oe m)), then both algorithms (single and
multipattern) work as much as dynamic programming and hence the multipattern search is not
useful. The other case when the algorithm could not be useful is when the shifts of a Boyer-Moore
search are shortened by having many patterns up to the point where it is better to perform separate
searches. This never happens in practice.
6.3 Counting
If the number of verifications is negligible, each pass of the algorithms is O(n). In the case of
multiple patterns, only O(w= log m) patterns can be packed in a single search, so the cost to search
r patterns is O(rn log(m)=w).
The difficult part of the analysis is the maximum error level ff that the filtration scheme can
tolerate while keeping the number of verifications low. We assume that we use dynamic programming
to verify potential matches. We call  the probability of verifying. If   log(m)=(wm 2 ) the
algorithm keeps linear (i.e. optimal) on average. The algorithm is always useful since the number
of verifications triggered with the multipattern search is the same as for the single-pattern version.
However, if   1=m both algorithms work O(rmn) as for dynamic programming and hence the
filter is not useful.
We derive in Appendix B a pessimistic bound for the limit of optimality and usefulness, namely
grows, we can tolerate smaller error levels. This limit holds
for any condition of the type independently of the constant c. In our case, we need
usefulness.
7 Experimental Results
We experimentally study our algorithms and compare them against previous work. We tested with
megabytes of lower-case English text. The patterns were randomly selected from the same text.
We use a Sun UltraSparc-1 running Solaris 2.5.1, with 64 megabytes of RAM, and Each
data point was obtained by averaging the Unix's user time over 10 trials. We present all the times
in tenths of seconds per megabyte.
We do not present results on random text to avoid an excessively lengthly exposition. In general,
all the filters improve as the alphabet size oe grows. Lower-case English text behaves approximately
as random text with which is the inverse of the probability that two random letters are
equal.

Figure

compares the plain and hierarchical verification methods against a sequential
application of the r searches, for the case of superimposed automata when the automaton fits in a
computer word. We show the cases of increasing r and of increasing k. It is clear that hierarchical
verification outperforms plain verification in all cases. Moreover, the analysis for hierarchical verification
is confirmed since the maximum r up to where the cost of the parallel algorithm does not
grow linearly is very close to r  . On the other hand, the algorithm with simple
verification degrades sooner, since the verification cost grows with r.
The mentioned maximum r   value is the point where the parallelism ratio is maximized. That
is, if we have to search for 2r   patterns, it is better to split them in two groups of size r   and search
each group sequentially. To stress this point, Figure 12 (right) shows the quotient between the
parallel and the sequential algorithms, where the optimum is clear for superimposed automata. On
the other hand, the parallelism ratio of exact partitioning keeps improving as r grows, as predicted
by the analysis (there is an optimum for larger m, related to the Sunday shifts, but it still does not
justify to split a search in two).
When we compare our algorithms against the others, we consider only hierarchical verification
and use this r   value to obtain the optimal grouping for the superimposed automata algorithms.
The exact partitioning, on the other hand, performs all the searches in a single pass. In counting,
it is clear that the speedup is optimal and we pack as many patterns as we can in a single search.
Notice that the plots which depend on r show the point where r   should be selected. Those
which depend on k (for fixed r), on the other hand, just show how the parallelization works as the
error level increases, which cannot be controlled by the algorithm.
We compare now our algorithms among them and against others. We begin with short patterns
whose NFA fit in a computer word. Figure 13 shows the results for increasing r and for increasing
k. For low and moderate error levels, exact partitioning is the fastest algorithm. In particular, it is
faster than previous work [17] when the number of patterns is below 50 (for English text). When
r
r
rts
r
r
rts
rts
Sequential NFA Superimposed, plain verif.
Exact Partitioning Superimposed, hierarchical verif.

Figure

12: Comparison of sequential and multipattern algorithms for 9. The rows correspond
to respectively. The left plots show search time and the right plots show
the ratio between the parallel (t p ) and the sequential time (r \Theta t s ).
the error level increases, superimposed automata is the best choice. This agrees with the analysis.
r
r
Exact Partitioning Superimposed Automata
Counting

Figure

13: Comparison among algorithms for 9. The top plots show increasing r for
3. The bottom plots show increasing k for
We consider longer patterns now 14 shows the results for increasing r and
for increasing k. As before, exact partitioning is the best where it can be applied, and improves
over previous work [17] for r up to 90-100. For these longer patterns the superimposed automata
technique also degrades, and only rarely is it able to improve over exact partitioning. In most cases
it only begins to be the best when it (and all the others) are no longer useful.

Figure

summarizes some of our experimental results, becoming a practical version of the
theoretical Figure 10. The main differences are that exact partitioning is better in practice than
what its complexity suggests, and that there is no clear winner between pattern and automaton
Exact Partitioning Pattern Partitioning Automaton Partitioning
Counting

Figure

14: Comparison among algorithms for 30. The top plots show, for increasing r,
4. The bottom plots show, for increasing k, partitioning is not
run for would resort to exact partitioning.
Partitioning into Exact Search
Superimposed Automata
r
Muth-Manber
aPartitioning into Exact Search
9
Superimposed Automata

Figure

15: The areas where each algorithm is better, in practice, on English text. In the right plot
we assumed 9. Compare with Figure 10.
Conclusions
We have presented a number of different filtering algorithms for multipattern approximate search-
ing. These are the only algorithms that allow an arbitrary number of errors. On the other hand,
the only previous work allows just one error and we have outperformed it when the number of
patterns to search is below 50-100 on English text, depending on the pattern length.
We have explained, analyzed and experimentally tested our algorithms. We have also presented
a map of the best algorithms for each case. Many of the ideas we propose here can be used to
adapt other single-pattern approximate searching algorithms to the case of multipattern searching.
For instance, the idea of superimposing automata can be adapted to most bit-parallel algorithms,
such as [19]. Another fruitful idea is that of exact partitioning, where a multipattern exact search
is easily adapted to search the pieces of many patterns. There are many other filtering algorithms
of the same type, e.g. [28]. On the other hand, other exact multipattern search algorithms may be
better suited to other search parameters (e.g. working better on many patterns).
A number of practical optimizations to our algorithms are possible, for instance
ffl If the patterns have different lengths, we truncate them to the shortest one when superimposing
automata. We can select cleverly the substrings to use, since having the same character
at the same position in two patterns improves the filtering mechanism.
ffl We used simple heuristics to group subpatterns in superimposed automata. These can be
improved to maximize common letters too. A more general technique could group patterns
which are similar in terms of number of errors needed to convert one into the other (i.e. a
clustering technique).
ffl We are free to partition each pattern in k pieces as we like in exact partitioning. This is
used in [24] to minimize the expected number of verifications when the letters of the alphabet
do not have the same probability of occurrence (e.g. in English text). An O(m 3 ) dynamic
programming algorithm is presented there to select the best partition, and this could be
applied to multipattern search.

Acknowledgements

We thank Robert Muth and Udi Manber for their implementation of [17]. We also thank the
anonymous referees for their detailed comments that improved this work.



--R

Efficient string matching: an aid to bibliographic search.
Efficient Text Searching.
Text retrieval: Theory and practice.
A new approach to text searching.
Multiple approximate string matching.
Faster approximate string matching.
Fast and practical approximate pattern matching.
A fast string searching algorithm.
Theoretical and empirical comparisons of approximate string matching algorithms.
Sublinear approximate string matching and biological applications.
An improved algorithm for approximate string matching.

Simple and efficient string matching with k mismatches.
A comparison of approximate string matching algo- rithms

Fast parallel and serial approximate string matching.
Approximate multiple string search.
A sublinear algorithm for approximate keyword searching.
A fast bit-vector algorithm for approximate pattern matching based on dynamic progamming
Multiple approximate string matching by counting.
Approximate Text Searching.
A guided tour to approximate string matching.
Improving an algorithm for approximate pattern matching.
Very fast and simple approximate string matching.

The theory and computation of evolutionary distances: pattern recognition.
A very fast substring search algorithm.
On using q-gram locations in approximate string matching
Approximate Boyer-Moore string matching
Algorithms for approximate string matching.
Finding approximate patterns in strings.
Approximate string matching with q-grams and maximal matches
Approximate string matching using within-word parallelism
Fast text searching allowing errors.

--TR
Algorithms for approximate string matching
Fast parallel and serial approximate string matching
Efficient text searching
A very fast substring search algorithm
An improved algorithm for approximate string matching
A new approach to text searching
Fast text searching
Approximate string-matching with <italic>q</italic>-grams and maximal matches
Approximate Boyer-Moore string matching
Approximate string matching using within-word parallelism
A comparison of approximate string matching algorithms
Very fast and simple approximate string matching
A fast string searching algorithm
Efficient string matching
A guided tour to approximate string matching
Text-Retrieval
Multiple Approximate String Matching
Fast and Practical Approximate String Matching
Theoretical and Empirical Comparisons of Approximate String Matching Algorithms
Approximate Multiple Strings Search
A Bit-Parallel Approach to Suffix Automata
A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming
On Using q-Gram Locations in Approximate String Matching

--CTR
Atsuhiro Takasu, An approximate multi-word matching algorithm for robust document retrieval, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Kimmo Fredriksson, On-line Approximate String Matching in Natural Language, Fundamenta Informaticae, v.72 n.4, p.453-466, December 2006
Kimmo Fredriksson , Gonzalo Navarro, Average-optimal single and multiple approximate string matching, Journal of Experimental Algorithmics (JEA), v.9 n.es, 2004

Josu Kuri , Gonzalo Navarro , Ludovic M, Fast Multipattern Search Algorithms for Intrusion Detection, Fundamenta Informaticae, v.56 n.1-2, p.23-49, January
Josu Kuri , Gonzalo Navarro , Ludovic M, Fast multipattern search algorithms for intrusion detection, Fundamenta Informaticae, v.56 n.1,2, p.23-49, July
Federica Mandreoli , Riccardo Martoglia , Paolo Tiberio, A syntactic approach for searching similarities within sentences, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
multipattern search;search allowing errors;string matching