我检查了练习，有一个额外的假设可以简化问题

练习 3.2.3：一个 n 字节的文档最多可以有多少个 k-shingles？您可以假设字母表的大小足够大，以至于长度为 k 的可能字符串的数量至少为 n。

Shingling 是一种将文档表示为集合的常用技术。k-shingle 被认为是在文档中找到的所有可能的长度为 k 的连续子串。例如，如果文档是“天空是蓝色的，太阳是明亮的”，当 k=3 时的 k-shingles 如下所示：

[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"]

现在我们可以说，对于 9 个单词的文档，3-shingles 的数量是 7。如果您尝试多个句子，您会得出以下结论：

k-shingles的数量=单词的数量-k+1

现在的问题是，在一个 n 字节的文档中，最大可能的单词数是多少？

这取决于单词的最小可能大小。在 UTF-8 编码中，每个字母占用 1 个字节（8 位）。例如，一个 4 个字母的单词“Mars”占用 4 个字节。

一个单词的最小可能大小是 1 个字节，即它仅包含 1 个字母。因此， n 字节文档中的最大单词数是 n。现在让我们用最大数量的 k-shingles 代替它

k-shingles 的数量 = n-k+1

最后，这个答案在以下假设下是有效的：

• UTF-8 编码
• 每个单词仅包含 1 个字母
• 字母表的大小足够大 (>n)，因此所有集合都不同

MMDS 将此问题的 k-shingle 定义为

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.

因此，艾哈迈德答案中的示例并不完全正确。它将是“the”、“he”、“es”、“sk”、“sky”。因此，单词的数量与答案无关。

例如，我们可以想象一个字符串“abcde”并采用相同的 3-shingle。带状疱疹将是：“abc”、“bcd”、“cde”。k-shingle 会像文字上的一个窗口，所以答案是相当明显的N - k + 1

我们还可以用 3 个带状疱疹对“abcabc”字符串进行映像：“abc”、“bca”、“cab”、“abc”。这给了我们总共 4 个 3-shingles 和 3 个 uniq k-shingles。但我们被要求找到最大可能的数字。