3.9. METHODS FOR HIGH DEGREES OF SIMILARITY
127
or 2. Suppose i = 1. Then j ≤(10 × 0.1 −1 + 1 + 0.9)/0.9. That is, we only
have to compare the symbol a with strings in the bucket for (a, j) if j ≤2.11.
Thus, j can be 1 or 2, but nothing higher.
Now suppose i = 2. Then we require j ≤(10 × 0.1 −2 + 1 + 0.9)/0.9, Or
j ≤1. We conclude that we must look in the buckets for (a, 1), (a, 2), and (c, 1),
but in no other bucket. In comparison, using the buckets of Section 3.9.4, we
would look into the buckets for a and c, which is equivalent to looking to all
buckets (a, j) and (c, j) for any j.
✷
3.9.6
Using Position and Length in Indexes
When we considered the upper limit on j in the previous section, we assumed
that what follows positions i and j were as in Fig. 3.15, where what followed
these positions in strings s and t matched exactly. We do not want to build an
index that involves every symbol in the strings, because that makes the total
work excessive. However, we can add to our index a summary of what follows
the positions being indexed. Doing so expands the number of buckets, but not
beyond reasonable bounds, and yet enables us to eliminate many candidate
matches without comparing entire strings. The idea is to use index buckets
corresponding to a symbol, a position, and the suﬃx length, that is, the number
of symbols following the position in question.
Example 3.29 : The string s = acdefghijk, with J = 0.9, would be indexed
in the buckets for (a, 1, 9) and (c, 2, 8). That is, the ﬁrst position of s has symbol
a, and its suﬃx is of length 9. The second position has symbol c and its suﬃx
is of length 8.
✷
Figure 3.15 assumes that the suﬃxes for position i of s and position j of t
have the same length. If not, then we can either get a smaller upper bound on
the size of the intersection of s and t (if t is shorter) or a larger lower bound
on the size of the union (if t is longer). Suppose s has suﬃx length p and t has
suﬃx length q.
Case 1: p ≥q.
Here, the maximum size of the intersection is
Ls −i + 1 −(p −q)
Since Ls = i + p, we can write the above expression for the intersection size as
q + 1. The minimum size of the union is Ls + j −1, as it was when we did not
take suﬃx length into account. Thus, we require
q + 1
Ls + j −1 ≥J
whenever p ≥q.
