78
CHAPTER 3. FINDING SIMILAR ITEMS
3.1.4
Exercises for Section 3.1
Exercise 3.1.1: Compute the Jaccard similarities of each pair of the following
three sets: {1, 2, 3, 4}, {2, 3, 5, 7}, and {2, 4, 6}.
Exercise 3.1.2: Compute the Jaccard bag similarity of each pair of the fol-
lowing three bags: {1, 1, 1, 2}, {1, 1, 2, 2, 3}, and {1, 2, 3, 4}.
!! Exercise 3.1.3: Suppose we have a universal set U of n elements, and we
choose two subsets S and T at random, each with m of the n elements. What
is the expected value of the Jaccard similarity of S and T ?
3.2
Shingling of Documents
The most eﬀective way to represent documents as sets, for the purpose of iden-
tifying lexically similar documents is to construct from the document the set
of short strings that appear within it. If we do so, then documents that share
pieces as short as sentences or even phrases will have many common elements
in their sets, even if those sentences appear in diﬀerent orders in the two docu-
ments. In this section, we introduce the simplest and most common approach,
shingling, as well as an interesting variation.
3.2.1
k-Shingles
A document is a string of characters. Deﬁne a k-shingle for a document to be
any substring of length k found within the document. Then, we may associate
with each document the set of k-shingles that appear one or more times within
that document.
Example 3.3 : Suppose our document D is the string abcdabd, and we pick
k = 2. Then the set of 2-shingles for D is {ab, bc, cd, da, bd}.
Note that the substring ab appears twice within D, but appears only once
as a shingle. A variation of shingling produces a bag, rather than a set, so each
shingle would appear in the result as many times as it appears in the document.
However, we shall not use bags of shingles here.
✷
There are several options regarding how white space (blank, tab, newline,
etc.) is treated. It probably makes sense to replace any sequence of one or more
white-space characters by a single blank. That way, we distinguish shingles that
cover two or more words from those that do not.
Example 3.4 : If we use k = 9, but eliminate whitespace altogether, then we
would see some lexical similarity in the sentences “The plane was ready for
touch down”. and “The quarterback scored a touchdown”. However, if we
retain the blanks, then the ﬁrst has shingles touch dow and ouch down, while
the second has touchdown. If we eliminated the blanks, then both would have
touchdown.
✷
