Can someone answer this question:
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
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:
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.
