2 篇文章带有标签 “文本去重”

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

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

$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=2k = 2k=2 时（尺子长度为 2）：第一次框 ab

在互联网大数据场景中，如何从海量数据（如百亿网页、千万级商品描述、巨大的开源代码仓库）中快速找出重复或高度相似的内容？这是一个极其经典的工业界痛点。

最朴素的想法是：对文章进行分词，转成集合后两两比对。若有 $N$ 篇文档，需要比较 $\frac{N(N-1)}{2}$ 次。当 $N = 10^7$（一千万）时，比较次数约为 50 万亿次。即便单次比较仅需 1 微秒，也需要 1.6 年 才能跑完。这种 $O(N^2)$ 复杂度的算法会导致服务器直接卡死崩溃。

本文将结合数学原理、算法推导与工程实战，深入拆解 Jaccard 相似度 的直觉陷阱，以及 MinHash（最小哈希） 算法如何对高维稀疏数据完成降维打击，最终给出可直接落地的工业级实现方案。

Jaccard 相似度（Jaccard Similarity） 是衡量两个集合重合度的标准数学方法。其核心思想非常直观：看两个集合的交集（共同拥有的元素）占它们并集（总共拥有的元素）的比例。

数学公式定义为：

假设我们要对比两篇简短文本的词汇相似度： 文本 A 词集：{ 苹果, 香蕉, 梨, 桃子 }（4个元素） 文本 B 词集：{ 香蕉, 梨