1
DSaA 2012/2013
String matching
Data Structures and Algorithms
1
DSaA 2012/2013
String matching
Data Structures and Algorithms
2
DSaA 2012/2013
String matching
String matching algorithms:
• Naive
• Rabin-Karp
• Finite automaton
• Knuth-Morris-Pratt (KMP)
ε – epsilon, δ – delta, φ – phi, σ – sigma, π - pi
3
DSaA 2012/2013
String matching problem
•
We assume that the text is an array T [1..n] of length n and that the pattern
is an array P[1..m] of length m
≤ n. We further assume that the elements of
P and T are characters drawn from a finite alphabet
S
. For example, we
may have
S
= {0, 1} or
S
= {a, b,. . . , z}. The character arrays P and T are
often called strings of characters.
•
We say that pattern P occurs with shift s in text T (or, equivalently, that
pattern P occurs beginning at position s + 1 in text T) if 0
≤ s ≤ n - m and
T [s + 1..s + m] = P[1..m] (that is, if T [s + j] = P[ j], for 1
≤ j ≤ m). If P occurs
with shift s in T , then we call s a valid shift; otherwise, we call s an invalid
shift. The string-matching problem is the problem of finding all valid shifts
with which a given pattern P occurs in a given text T
Text T
Pattern P
b a b a
a c b a
a a b a
a b a
b b a
a b a
a b a
a b a
3 occurrences
of pattern with shifts
3, 5, 9
15
1
2
3
4
5
6
7
8
9 10 11 12 13 14
1
2
3
4
DSaA 2012/2013
Complexity - comparison
Algorithm
Preprocessing time
Worse case
Matching time
Naive
0
O((n-m+1)m)
Rabin-Karp
(m)
O((n-m+1)m)
Finite automaton
O(m|
S
|)
(n)
Knutt-Morris-Pratt
(m)
(n)
5
DSaA 2012/2013
Notation and terminology
• We shall let
S
* (read "sigma-star") denote the set of all
finite-length strings formed using characters from the
alphabet
S
. In this lecture, we consider only finite-length
strings. The zero-length empty string, denoted
e
, also
belongs to
S
*. The length of a string x is denoted |x|. The
concatenation of two strings x and y, denoted xy, has
length |x| + |y| and consists of the characters from x
followed by the characters from y.
• We say that a string w is a prefix of a string x, denoted w
⊏ x, if x = wy for some string y
S
*. Note that if w
⊏ x,
then |w|
≤ |x|. Similarly, we say that a string w is a suffix
of a string x, denoted w
⊐ x, if x = yw for some y
S
*. It
follows from w
⊐ x that |w| ≤ |x|. The empty string
e
is
both a suffix and a prefix of every string. For example,
we have ab
⊏ abcca and cca ⊐ abcca. It is useful to note
that for any strings x and y and any character a, we have
x
⊐y if and only if xa⊐ya. Also note that ⊏ and ⊐ are
transitive relations.
6
DSaA 2012/2013
Notation and terminology
• Overlapping-suffix lemma:
Suppose that x, y, and z are strings such
that x
⊐z and y⊐z. If |x| ≤ |y|, then x⊐y. If
|x|
≥|y|, then y⊐x. If |x| = |y|, then x = y.
For brevity of notation, we shall denote the k-character prefix P[1..k]
of the pattern P[1..m] by P
k
. Thus, P
0
=
e
and P
m
= P = P[1..m]. Similarly,
we denote the k-character prefix of the text T as T
k
. Using this notation,
we can state the string-matching problem as that of finding all shifts s in
the range 0
≤ s ≤ n-m such that P ⊐T
s+m
.
The test "x = y" is assumed to take time
(t + 1), where t is the length of the
longest string z such that z
⊏x and z⊏y.
7
DSaA 2012/2013
Naive algorithm - code
{ 1}
{ 2}
{ 3}
{ 4}
{ 5}
Naive_String_Matcher(T,P)
n := length[T]
m := length[P]
for s:=0 to n-m do
if P[1..m]=T[s+1..s+m] then
print „patter occurs with shift” s
T=a
n
, P=a
m
(n-m+1)m character comparisons
Worse-case complexity: O((n-m+1)m)
T=„random”, P=„random”
average ≤2(n-m+1)
character comparisons
Average complexity: O(n-m+1)
T=a
n
, P=a
m-1
b
8
DSaA 2012/2013
The Rabin-Karp algorithm - idea
•
For expository purposes, let us assume that
S
= {0, 1, 2, . . . , 9}, so that each
character is a decimal digit. (In the general case, we can assume that each character
is a digit in radix-d notation, where d = |
S
|.) We can then view a string of k
consecutive characters as representing a length-k decimal number. The character
string
„31415” thus corresponds to the decimal number 31,415.
•
Given a pattern P[1..m], we let p denote its corresponding decimal value. In a similar
manner, given a text T[1..n], we let t
s
denote the decimal value of the length-m
substring T[s + 1..s + m], for s = 0, 1, . . . , n-m. Certainly, t
s
= p if and only if
T[s+1..s+m] = P[1..m]; thus, s is a valid shift if and only if t
s
= p. If we could compute
p in time
(m) and all the t
s
values in a total of
(n - m + 1) time, then we could
determine all valid shifts s in time
(m) +
(n-m+1) =
(n) by comparing p with each
of the t
s
's. We can compute p in time
(m) using Horner's rule:
p = P[m] + 10 (P[m - 1] + 10(P[m -
2] + · · · + 10(P[2] + 10P[1]) )).
•
The value t
0
can be similarly computed from T[1..m] in time
(m). To compute the
remaining values t
1
, t
2
, . . . , t
n-m
in time
(n - m), it suffices to observe that t
s+1
can be
computed from t
s
in constant time, since
]
1
[
]
1
[
10
10
1
1
m
s
T
s
T
t
t
m
s
s
T=..314152.., m=5, t
s
=31415
t
s+1
=10(31415-10000
*
3)+2=14152
Problem! : p and t
s
may be too large to work with conveniently.
9
DSaA 2012/2013
The Rabin-Karp algorithm
• We can compute p and the t
s
's modulo a
suitable modulus q.
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
3 1 4 1 5
7
8 9 3 11 0 1 7 8 4 5 10 11 7 9
…
…
11
q=13
valid
match
spurious
hit
2 3 5 9 0 2
8 9
35902 ≡ (23590 – 3*10000)*10+2 (mod 13)
≡ (8 – 2*3)*10 + 2 (mod 13)
≡ 9
q
m
s
T
h
s
T
t
d
t
s
s
mod
1
1
1
where
q
d
h
m
mod
1
10
DSaA 2012/2013
The Rabin-Karp algorithm - code
{ 1}
{ 2}
{ 3}
{ 4}
{ 5}
{ 6}
{ 7}
{ 8}
{ 9}
{10}
{11}
{12}
{13}
{14}
Rabin_Karp_Matcher(T,P)
n := length[T]
m := length[P]
h := d
m-1
mod q
p := 0
t
0
:= 0
for i:=1 to m do
p := (d*p+P[i]) mod q
t
o
:= (d*t
0
+T[i]) mod q
for s:=0 to n-m do
if p=t
s
then
if P[1..m]=T[s+1..s+m] then
print „patter occurs with shift” s
if s < n-m then
t
s+1
:=(d*(t
s
-T[s+1]*h)+T[s+m+1]) mod q
The modulus q is typically chosen as a prime such that dq just fits within
one computer word (double word)
11
DSaA 2012/2013
The Rabin-Karp algorithm - analysis
• RABIN-KARP-MATCHER takes
(m) preprocessing time, and its
matching time is
((n - m + 1)m) in the worst case, since (like the naive
string-matching algorithm) the Rabin-Karp algorithm explicitly verifies
every valid shift. If P = a
m
and T = a
n
, then the verifications take time
((n - m + 1)m), since each of the n - m + 1 possible shifts is valid.
• In many applications, we expect few valid shifts (perhaps some
constant c of them); in these applications, the expected matching time
of the algorithm is only O((n - m + 1) + cm) = O(n+m), plus the time
required to process spurious hits. After a heuristic analysis on an
assumption we can then expect that the number of spurious hits is
O(n/q), since the chance that an arbitrary t
s
will be equivalent to p,
modulo q, can be estimated as 1/q. Since there are O(n) positions at
which the test of line 10 fails and we spend O(m) time for each hit, the
expected matching time taken by the Rabin-Karp algorithm is
O(n) + O(m(v + n/q)),
where v is the number of valid shifts. This running time is O(n) if v=O(1)
and we choose q = m. That is, if the expected number of valid shifts is
small (O(1)) and the prime q is chosen to be larger than the length of
the pattern, then we can expect the Rabin-Karp procedure to use only
O(n + m) matching time. Since m
n, this expected matching time is
O(n).
12
DSaA 2012/2013
Finite automaton
• A finite automaton M is a 5-tuple (Q, q
0
, A,
S
,
d
), where:
– Q is a finite set of states,
– q
0
Q is the start state,
– A
Q is a distinguished set of accepting states,
–
S
is a finite input alphabet,
–
d
is a function from Q
×
S
into Q, called the transition function of M.
The finite automaton begins in state q
0
and reads the characters of its
input string one at a time. If the automaton is in state q and reads
input character a, it moves ("makes a transition") from state q to
state
d
(q, a). Whenever its current state q is a member of A, the
machine M is said to have accepted the string read so far. An input
that is not accepted is said to be rejected.
1 0
0 0
0
1
b
a
d
Q = {0, 1}, q
o
=0, A={1}
S
= { a, b},
0
1
a
a
b
b
13
DSaA 2012/2013
Automaton
– cont.
• A finite automaton M induces a function
f
, called the final-state
function, from
S
* to Q such that
f
(w) is the state M ends up in after
scanning the string w. Thus, M accepts a string w if and only if
f
(w)
A. The function
f
is defined by the recursive relation:
S
S
a
w
for
a
w
wa
q
,
,
,
*
0
f
d
f
e
f
We define an auxiliary function
s
, called the suffix function corresponding to P.
The function
s
is a mapping from
S
* to {0, 1, . . . , m} such that
s
(x) is the length
of the longest prefix of P that is a suffix of x:
s
(x) = max { k: P
k
⊐ x}
We define the string-matching automaton that corresponds to a given pattern
P[1..m] as follows:
- The state set Q is {0, 1, . . . , m}. The start state q
0
is state 0, and state m is the
only accepting state.
- The transition function
d
is defined by the following equation, for any state q
and character a:
a
P
a
q
q
s
d
,
14
DSaA 2012/2013
Automaton - example
0
7
1
2
3
4
5
6
a
b
a
b
a
c
a
b
b
a
a
a
1 0
1 2
0
1
b
a
d
0
0
c
a
b
P
3 0
2
0 a
1 4
3
0 b
5 0
1 4
4
5
0
6
a
c
7 0
6
0 a
1 2
7
0
9 10 11
a b a
7 2 3
6 7 8
b a c
4 5 6
3 4 5
a b a
3 4 5
- 1 2
- a b
0 1 2
i
T[i]
state
f
(T[i])
b,c
a
c
b,c
c
b,c
b,c
c
15
DSaA 2012/2013
Finite automaton matcher - code
{ 1}
{ 2}
{ 3}
{ 4}
{ 5}
{ 6}
{ 7}
Finite_Automaton_Matcher(T,P)
n := length[T]
q := 0
for i:=1 to n do
q :=
d
(q,T[i])
if q = m then
s := i - m
print „patter occurs with shift” s
{ 1}
{ 2}
{ 3}
{ 4}
{ 5}
{ 6}
{ 7}
{ 8}
{ 9}
Compute_Transition_Function(P,
S
)
m := length[P]
for q:=0 to m do
for a
S
do
k := min(m+1,q+2)
repeat
k := k – 1
until P
k
⊐ P
q
a
d
(q,a) := k
return
d
16
DSaA 2012/2013
Finite automaton matcher - analysis
• The running time of COMPUTE-TRANSITION-
FUNCTION is O(m
3
|
S
|), because the outer loops
contribute a factor of m|
S
|, the inner repeat loop
can run at most m + 1 times, and the test P
k
⊐
P
q
a on line 6 can require comparing up to m
characters.
• Much faster procedures exist; the time required to
compute
d
from P can be improved to O(m|
S
|) by
utilizing some cleverly computed information
about the pattern P. With this improved
procedure for computing
d
, we can find all
occurrences of a length-m pattern in a length-n
text over an alphabet
S
with O(m |
S
|)
preprocessing time and
(n) matching time.
17
DSaA 2012/2013
Knuth-Morris-
Pratt’s idea
b a c b a b a b a a b c b a b
a b a b a c a
s
q
P
T
b a c b a b a b a a b c b a b
a b a b a c a
s’
k
P
T
a b a b a
a b a
P
q
P
k
?
• Given a pattern P[1..m], the
prefix function for the pattern
P is the function
p
: {1, 2, . . . ,
m}
{0, 1, . . . , m - 1} such
that
p
[q]=max{k: k<q and P
k
⊐ P
q
}
• That is,
p
[q] is the length of the
longest prefix of P that is a
proper suffix of P
q
.
9 10
c a
0 1
6 7 8
b a b
4 5 6
3 4 5
a b a
1 2 3
1 2
a b
0 0
i
P[i]
p
[i]
18
DSaA 2012/2013
KMP - code
{ 1}
{ 2}
{ 3}
{ 4}
{ 5}
{ 6}
{ 7}
{ 8}
{ 9}
{10}
{11}
{12}
KMP_Matcher(T,P)
n := length[T]
m := length[P]
p
:= Compute_Prefix_Function(P)
q :=0
for i:=1 to n do
while q>0 and P[q+1]≠T[i] do
q :=
p
[q]
if P[q+1] = T[i] then
q := q+1
if q=m then
print „patter occurs with shift” i-m
q :=
p
[q]
{ 1}
{ 2}
{ 3}
{ 4}
{ 5}
{ 6}
{ 7}
{ 8}
{ 9}
{10}
Compute_Prefix_Function(P)
m := length[P]
p
[1] := 0
k := 0
for q:=2 to m do
while k>0 and P[k+1]
≠P[q] do
k :=
p
[k]
if P[k+1]=P[q] then
k := k+1
p
[q] := k
return
p
9 10
c a
0 1
6 7 8
b a b
4 5 6
3 4 5
a b a
1 2 3
1 2
a b
0 0
i
P[i]
p
[i]
19
DSaA 2012/2013
KMP - analysis
• The running time of COMPUTE-PREFIX-FUNCTION is
(m), using
the potential method of amortized analysis. We associate a potential
of k with the current state k of the algorithm. This potential has an
initial value of 0, by line 3. Line 6 decreases k whenever it is
executed, since
p
[k] < k. Since
p
[k] = 0 for all k, however, k can
never become negative. The only other line that affects k is line 8,
which increases k by at most one during each execution of the for
loop body. Since k < q upon entering the for loop, and since q is
incremented in each iteration of the for loop body, k < q always
holds. (This justifies the claim that
p
[q] < q as well, by line 9.) We
can pay for each execution of the while loop body on line 6 with the
corresponding decrease in the potential function, since
p
[k] < k.
Line 8 increases the potential function by at most one, so that the
amortized cost of the loop body on lines 5-9 is O(1). Since the
number of outer-loop iterations is
(m), and since the final potential
function is at least as great as the initial potential function, the total
actual worst-case running time of COMPUTE-PREFIX-FUNCTION
is
(m).
• A similar amortized analysis, using the value of q as the potential
function, shows that the matching time of KMP-MATCHER is
(n).