# Mining of massive datasets

It is from an exercise in the book: Mining of massive datasets:

Chapter 3: Finding Similar Itemsets

What is the largest number of k-shingles a document of n bytes can have?

Exercise 3.2.3 : What is the largest number of k-shingles a document of n bytes can have? You may assume that the size of the alphabet is large enough that the number of possible strings of length k is at least as n.

the answer is (N-k)


I wanted an explanation

• Hello and Welcome to Data Science SE! You probably need to include more context in your question to allow people to better answer. What have you tried so far? Where are you stuck? You can include links to any resources you have, explaining more about this problem. – n1k31t4 Jun 12 '18 at 10:59

I checked the exercise, there is an additional assumption that simplifies the question

Exercise 3.2.3 : What is the largest number of k-shingles a document of n bytes can have? You may assume that the size of the alphabet is large enough that the number of possible strings of length k is at least as n.

Shingling is a common technique of representing documents as sets. k-shingle is said to be all the possible consecutive substring of length k found within a document. For example if the document is "The sky is blue and the sun is bright" the k-shingles when k=3 is given below:

[1)"the sky is"    2)"sky is blue"     3)"is blue and"     4)"blue and the"
5)"and the sun"   6)"the sun is"      7)"sun is bright"]


Now we can say that for a document of 9 words, the number of 3-shingles is 7. if you try multiple sentences you conclude that:

The number of k-shingles = the number of words - k+1

The question now is what is the largest number of possible words in an n-bytes document?

This depends on the smallest possible size of a word. In UTF-8 encoding each letter occupies 1 byte(8 bits). for example a word of 4 letter "Mars" occupies 4 bytes.

The smallest possible size of a word is 1 byte, that's when it consists of only 1 letter. Hence the largest number of words in n bytes document is n . Now let's substitute it in the largest number of k-shingles

The number of k-shingles = n-k+1

At the end this answer is valid under the following assumptions:

• UTF-8 encoding
• Each word consists of 1 letter only
• The size of the alphabet is large enough (>n) so that all sets are different

MMDS defines k-shingle for this problem as

A document is a string of characters. Define 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.


So, the example in Ahmed’s answer is not quite correct. It will be “the”, “he “, "e s", " sk", "sky". Hence the number of words has nothing to do with the answer.

As an example, we can imagine a string "abcde" and take the same 3-shingle. The shingles will be: "abc", "bcd", "cde". k-shingle will be like a window on the text, so the answer is quite obvious N - k + 1

We also can image "abcabc" string with 3-shingles: "abc", "bca", "cab", "abc". Which gives us overall 4 3-shingles and 3 uniq k-shingles. But we were asked to find the largest possible number.