3.9. METHODS FOR HIGH DEGREES OF SIMILARITY
129
i = 1: Then p = 9, so we require q ≥10 and 10/(q + j) ≥0.8. The possible
values of q and j are
1. q = 10; j = 1.
2. q = 10; j = 2.
3. q = 11; j = 1.
i = 2: Now, p = 8, so we require q ≥9 and 9/(q + j + 1) ≥0.8. Since j must
be a positive integer, the only solution is q = 9 and j = 1, a possibility
that we already knew about.
i = 3: Here, p = 7, so we require q ≥8 and 8/(q + j + 2) ≥0.8. There are no
solutions.
q
j = 1
j = 2
j = 3
7
x
8
x
x
i = 1
9
x
x
x
10
x
x
11
x
7
x
i = 2
8
x
x
9
x
i = 3
7
x
Figure 3.16: The buckets that must be examined to ﬁnd possible matches for
the string s = acdefghijk with J = 0.8 are marked with an x
When we accumulate the possible combinations of i, j, and q, we see that
the set of index buckets in which we must look forms a pyramid. Figure 3.16
shows the buckets in which we must search. That is, we must look in those
buckets (x, j, q) such that the ith symbol of the string s is x, j is the position
associated with the bucket and q the suﬃx length.
✷
3.9.7
Exercises for Section 3.9
Exercise 3.9.1: Suppose our universal set is the lower-case letters, and the
order of elements is taken to be the vowels, in alphabetic order, followed by the
consonants in reverse alphabetic order. Represent the following sets as strings.
a {q, w, e, r, t, y}.
(b) {a, s, d, f, g, h, j, u, i}.
