128
CHAPTER 3. FINDING SIMILAR ITEMS
Case 2: p < q.
Here, the maximum size of the intersection is Ls −i + 1, as
when suﬃx length was not considered. However, the minimum size of the union
is now Ls + j −1 + q −p. If we again use the relationship Ls = i + p, we can
replace Ls −p by i and get the formula i + j −1 + q for the size of the union.
If the Jaccard similarity is at least J, then
Ls −i + 1
i + j −1 + q ≥J
whenever p < q.
Example 3.30 : Let us again consider the string s = acdefghijk, but to make
the example show some details, let us choose J = 0.8 instead of 0.9. We know
that Ls = 10. Since ⌊(1 −J)Ls⌋+ 1 = 3, we must consider preﬁx positions
i = 1, 2, and 3 in what follows. As before, let p be the suﬃx length of s and q
the suﬃx length of t.
First, consider the case p ≥q. The additional constraint we have on q and
j is (q + 1)/(9 + j) ≥0.8. We can enumerate the pairs of values of j and q for
each i between 1 and 3, as follows.
i = 1: Here, p = 9, so q ≤9. Let us consider the possible values of q:
q = 9: We must have 10/(9 + j) ≥0.8. Thus, we can have j = 1, j = 2,
or j = 3. Note that for j = 4, 10/13 > 0.8.
q = 8: We must have 9/(9 + j) ≥0.8. Thus, we can have j = 1 or j = 2.
For j = 3, 9/12 > 0.8.
q = 7: We must have 8/(9 + j) ≥0.8. Only j = 1 satisﬁes this inequality.
q = 6: There are no possible values of j, since 7/(9 + j) > 0.8 for every
positive integer j. The same holds for every smaller value of q.
i = 2: Here, p = 8, so we require q ≤8. Since the constraint (q+1)/(9+j) ≥0.8
does not depend on i,8 we can use the analysis from the above case, but
exclude the case q = 9. Thus, the only possible values of j and q when
i = 2 are
1. q = 8; j = 1.
2. q = 8; j = 2.
3. q = 7; j = 1.
i = 3: Now, p = 7 and the constraints are q ≤7 and (q + 1)/(9 + j) ≥0.8. The
only option is q = 7 and j = 1.
Next, we must consider the case p < q. The additional constraint is
11 −i
i + j + q −1 ≥0.8
Again, consider each possible value of i.
8Note that i does inﬂuence the value of p, and through p, puts a limit on q.
