深入浅出 k-Shingle：海量文本去重的防篡改利器

在文本挖掘和信息检索领域，$k$-Shingle（通常也被称为 $k$-gram）是一种将连续的文本切分成固定长度碎片的技术。它是海量文本去重（如 MinHash + LSH 架构）中极其关键的数据预处理阶段。

简单来说，它的核心任务是：把一篇文章（一维的字符串）转化成一个集合（Set），并且在这个集合中锁死文本的局部语序。

---

一、 核心概念：滑动窗口（Sliding Window）

$k$-Shingle 的工作原理就像一把长度为 $k$ 的滑动尺子。尺子从文本的开头开始，每次框住 $k$ 个单位的内容作为一个 Shingle，然后向右平移一个单位，重复这个过程，直到文本结束。

根据具体需求，这里的“单位”可以是字符（Character），也可以是单词（Word）：

• 基于字符的 $k$-Shingle：通常用于拼写检查、DNA 序列分析或中文字符处理。
• 基于单词的 $k$-Shingle：通常用于英文等有天然空格分隔的文本去重与防抄袭。

直观案例演练

我们以短语 abcde 为例，来看看在不同的 $k$ 值下，基于字符切分出来的 $k$-Shingle 集合是什么样的：

• 当 $k = 1$ 时（尺子长度为 1）：每次只框一个字母。

• 集合结果：{ "a", "b", "c", "d", "e" }

• 当 $k = 2$ 时（尺子长度为 2）：第一次框 ab，向右滑一格框 bc，再滑一格框 cd……

• 集合结果：{ "ab", "bc", "cd", "de" }

• 当 $k = 3$ 时（尺子长度为 3）：

• 集合结果：{ "abc", "bcd", "cde" }

---

二、 核心痛点：为什么工业界去重一定要用 $k$-Shingle？

在做文本相似度计算时，如果我们只把文章简单地切成“单个词的集合”，会遇到严重的“洗牌式抄袭”漏洞。也就是说，作弊者只需要把原文章的段落顺序、句子顺序故意打乱调换，就能完美绕过传统的字词查重。

1. 经典漏洞：传统单字/单词去重

假设现在有两句话，句子 B 连人话都算不上，只是把句子 A 的单词顺序完全打乱了：

• 句子 A：I love eating apples
• 句子 B：apples eating love I

如果按照传统的“单字/单词”切分并转化为集合（Set），由于集合具有无序性和唯一性，它们切分后的结果是：

• 集合 A：{ "I", "love", "eating", "apples" } （共 4 个元素）
• 集合 B：{ "apples", "eating", "love", "I" } $\rightarrow$ 调整顺序后等同于 { "I", "love", "eating", "apples" }

此时我们计算两者的 Jaccard 相似度：

$J(A, B) = \frac{|A \cap B|}{|A \cup B|} = \frac{4}{4} = 100\%$

漏洞出现了：这两句话在人类看来语序完全反了，意思也彻底变了，但算法却极其自信地判定它们“100% 绝对完全相同”。

2. $k$-Shingle 的“破局”原理

如果我们使用 $k=2$ 的词级 Shingle（每次取连续的两个词组成的“词组”），让这把滑动尺锁死前后词的邻居关系：

对句子 A (I love eating apples) 进行滑动切分：

1. 第一组（前两个词）："I love"
2. 第二组（往后滑一个词）："love eating"
3. 第三组（再往后滑一个词）："eating apples"

• 集合 A (2-Shingle) = { "I love", "love eating", "eating apples" } （共 3 个元素）

对句子 B (apples eating love I) 进行滑动切分：

1. 第一组："apples eating"
2. 第二组："eating love"
3. 第三组："love I"

• 集合 B (2-Shingle) = { "apples eating", "eating love", "love I" } （共 3 个元素）

3. 防篡改效果对比

现在我们重新对 $k=2$ 之后的两个集合计算 Jaccard 相似度： 由于锁死了局部语序，这两句话切出来的词组没有一个能对得上！

• 交集 = { }（0 个）
• 并集 = { "I love", "love eating", "eating apples", "apples eating", "eating love", "love I" }（6 个）

$J(A, B) = \frac{0}{6} = 0\%$

💡 核心总结

• 只按单词切：只管“有没有这个词”，不管“词在哪里”，所以调换顺序无法识别（相似度 100%）。

• 按 $k$-Shingle 切：不仅管“有没有这个词”，还管“它的上下游是谁”。只要你敢打乱顺序，连续的词组就会断裂，相似度就会瞬间暴跌，从而精准揪出那些故意洗牌改写的抄袭手段。

---

三、 工业界如何选择 $k$ 的大小？

$k$ 的取值是一个精妙的平衡，通常取决于文本的平均长度以及字符集的大小。

$k$ 取值情况	优点	缺点	适用场景
$k$ 太小（如 1 或 2）	集合元素少，计算和存储开销极小。	区分度极低。像 "the", "and", "的", "是" 这种高频词/字符会大量重复，导致几乎所有文章的相似度都很高。	垃圾邮件分类的粗筛、极其简短的搜索关键词提示。
$k$ 太大（如 20 以上）	区分度极高，几乎具备唯一性。	容错率极低。哪怕抄袭者只改动了一个错别字，就会导致连续的 20 个 Shingle 全部碎掉（无法匹配），从而漏掉抄袭。	完全相同的文件/代码块硬匹配。

🎯 黄金经验法则（Engineering Rule of Thumb）

在实际工程中，选择 $k$ 的标准是：让任意一个随机 Shingle 出现的概率足够低。

• 短文本（如短信、推特、商品评论）：工业界一般选择 基于字符的 $k = 5 \sim 9$。
• 长文本（如新闻、论文、博客文章）：工业界一般选择 基于单词/词组的 $k = 5 \sim 8$。

---

四、 落地工程优化：Shingle 空间爆炸了怎么办？

如果一篇文章有 1 万个词，用 $k=9$ 变换后，就会产生约 1 万个长度为 9 的字符串（例如 "海量文本去重与相似度"）。直接存储这些大字符串，内存会直接挤爆，后续的 MinHash 矩阵也无法高效计算。

为了解决这个瓶颈，工业界采用了标准的 Tokens $\rightarrow$ $k$-Shingle $\rightarrow$ Hashing 流程：

在切出 $k$-Shingle 字符串后，立即用一个高效、均匀分布的哈希函数（如 MurmurHash3 或 64位 CRC）将其转化为一个 固定长度的整数（4字节或8字节）。

原始文本: "I love eating"
     ↓ (2-Shingle 切分)
字符串集合: { "I love", "love eating" }
     ↓ (MurmurHash3 数字化)
整数集合: { 284719384, 918273645 }

通过这一步降维，原本冗长的文本块就变成了一串紧凑、高密度的数字集合。接下来，系统就能完美对接 MinHash 签名算法，开启百亿级数据流的亚线性快速检索了。

参考资料

• k-shingling-python.py
• Gemini 3.5 Flash 的回答