---
layout: single
title:  "深入浅出 k-Shingle：海量文本去重的防篡改利器"
date:   2026-06-06 20:00:00 +0800
categories: [人工智能, 大数据]
tags: [k-Shingle, 文本去重, 防篡改, Jaccard, MinHash, 大数据处理]
---

在文本挖掘和信息检索领域，**$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字节）**。

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

```

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


## 参考资料
- [k-shingling-python.py](https://gist.github.com/Renien/a738b614b224bafdfc783994536c44a9)
- [Gemini 3.5 Flash 的回答](https://gemini.google.com/app/dbfe686a52a1a75b)