80
CHAPTER 3. FINDING SIMILAR ITEMS
ﬁnd in typical documents. Thus, the eﬀective number of diﬀerent shingles is
much less than 232 −1. If, as in Section 3.2.2, we assume only 20 characters are
frequent in English text, then the number of diﬀerent 4-shingles that are likely
to occur is only (20)4 = 160,000. However, if we use 9-shingles, there are many
more than 232 likely shingles. When we hash them down to four bytes, we can
expect almost any sequence of four bytes to be possible, as was discussed in
Section 1.3.2.
3.2.4
Shingles Built from Words
An alternative form of shingle has proved eﬀective for the problem of identifying
similar news articles, mentioned in Section 3.1.2. The exploitable distinction for
this problem is that the news articles are written in a rather diﬀerent style than
are other elements that typically appear on the page with the article. News
articles, and most prose, have a lot of stop words (see Section 1.3.1), the most
common words such as “and,” “you,” “to,” and so on. In many applications,
we want to ignore stop words, since they don’t tell us anything useful about
the article, such as its topic.
However, for the problem of ﬁnding similar news articles, it was found that
deﬁning a shingle to be a stop word followed by the next two words, regardless
of whether or not they were stop words, formed a useful set of shingles. The
advantage of this approach is that the news article would then contribute more
shingles to the set representing the Web page than would the surrounding ele-
ments. Recall that the goal of the exercise is to ﬁnd pages that had the same
articles, regardless of the surrounding elements. By biasing the set of shingles
in favor of the article, pages with the same article and diﬀerent surrounding
material have higher Jaccard similarity than pages with the same surrounding
material but with a diﬀerent article.
Example 3.5 : An ad might have the simple text “Buy Sudzo.” However, a
news article with the same idea might read something like “A spokesperson
for the Sudzo Corporation revealed today that studies have shown it is
good for people to buy Sudzo products.” Here, we have italicized all the
likely stop words, although there is no set number of the most frequent words
that should be considered stop words. The ﬁrst three shingles made from a
stop word and the next two following are:
A spokesperson for
for the Sudzo
the Sudzo Corporation
There are nine shingles from the sentence, but none from the “ad.”
✷
3.2.5
Exercises for Section 3.2
Exercise 3.2.1: What are the ﬁrst ten 3-shingles in the ﬁrst sentence of Sec-
tion 3.2?
