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