近似重复和精确重复检测

从Common Crawl等来源抓取的海量数据集不可避免地包含冗余内容。某些重复可能反映自然语言模式，但过多的重复，无论是精确的还是近似的，都可能对大型语言模型（LLM）的训练产生负面影响。这会浪费计算资源多次处理相同信息，可能使模型对数据分布的理解产生偏差，并可能放大重复内容中存在的偏见。因此，移除重复项是数据预处理中一个标准且重要的步骤。

精确重复检测

识别字节级别完全相同的文件相对简单。最常见的方法是为每个文件的内容计算一个加密哈希值（如SHA-256或MD5）。具有相同哈希值的文件被认为是精确重复项。

import hashlib
import os

def get_document_hash(doc_content):
  """计算文件内容的SHA-256哈希值。"""
  # 确保内容是字节
  if isinstance(doc_content, str):
    doc_content = doc_content.encode('utf-8')
  return hashlib.sha256(doc_content).hexdigest()

# 文件使用示例（可适配内存数据）
hashes_seen = set()
duplicates_to_remove = []
data_directory = "/path/to/your/text/files" # 替换为实际路径

# 在实际管道中，您会处理分布式数据流
for filename in os.listdir(data_directory):
    filepath = os.path.join(data_directory, filename)
    if os.path.isfile(filepath):
        try:
            with open(filepath, 'rb') as f:
                content = f.read()
                doc_hash = get_document_hash(content)

                if doc_hash in hashes_seen:
                    duplicates_to_remove.append(filepath)
                    # print(f"找到重复项: {filepath}")
                else:
                    hashes_seen.add(doc_hash)
        except Exception as e:
            print(
                f"处理 {filepath} 时出错: "
                f"{e}"
            )

# 现在 duplicates_to_remove 包含重复文件的路径
# 在大型系统中，通常会记录哈希值并在后续处理
print(
    f"根据内容哈希，识别出 {len(duplicates_to_remove)} 个精确重复项。"
)

这种基于哈希的方法虽然对相同内容有效，但也有局限性。首先，为数十亿或数万亿个文件存储和比较哈希值需要大量的内存或分布式存储及查找基础设施。其次，更重要的是，它无法识别几乎相同的文件，这些文件可能仅在格式、时间戳、用户名、广告或措辞上略有不同。这些近似重复项仍然代表冗余信息。

近似重复检测

处理近似重复项需要从精确哈希转向测量内容相似性的方法。挑战在于如何高效地完成这项工作，而无需比较每个文件对，因为这在计算上是不可行的（对于 $n$ 个文件，复杂度为 $O(n^2)$ ）。MinHash结合局部敏感哈希（LSH）等技术提供了一种概率性的、可扩展的解决方案。

分片：将文件表示为集合

第一步是将每个文件转换为适合相似性比较的表示形式。一种常用技术是分片（shingling），它将文件分解为一组重叠的标记 (token)或字符序列，称为片（shingles）或k-grams。

例如，考虑句子“the quick brown fox”。使用字符3-gram（长度为 $k=3$ 的片）： {"the", "he ", "e q", " qu", "qui", "uic", "ick", "ck ", "k b", " br", "bro", "row", "own", "wn ", "n f", " fo", "fox"}

选择片的类型（字符 vs. 单词）和长度（ $k$ ）会影响粒度。字符片对细微的单词变化更具弹性，而单词片则捕获更多语义结构。字符片的典型 $k$ 值可能是5到10。

def get_character_shingles(text, k=5):
  """为字符串生成一组字符k-gram（片）。"""
  text = text.lower() # 统一大小写
  shingles = set()
  if len(text) < k:
      return shingles # 处理短文本
  for i in range(len(text) - k + 1):
    shingles.add(text[i:i+k])
  return shingles

doc1 = "The quick brown fox jumps over the lazy dog."
doc2 = "The quick brown fox jumped over the lazy dogs." # 略有改动
doc3 = "A completely different sentence."

shingles1 = get_character_shingles(doc1, k=5)
shingles2 = get_character_shingles(doc2, k=5)
shingles3 = get_character_shingles(doc3, k=5)

print(f"文件1的片（示例）：{list(shingles1)[:5]}")
print(f"文件2的片（示例）：{list(shingles2)[:5]}")

Jaccard相似度

一旦文件被表示为片集（ $S_1$ , $S_2$ ），它们的相似性就可以使用Jaccard相似系数来量化 (quantization)：

J(S_1, S_2) = \frac{|S_1 \cap S_2|}{|S_1 \cup S_2|}

这衡量了集合交集的大小除以它们并集的大小。值为1表示集合完全相同，而0表示它们没有共同元素。直接计算这仍然需要比较片集，而片集可能非常大。

# 直接计算Jaccard相似度
intersection_size = len(shingles1.intersection(shingles2))
union_size = len(shingles1.union(shingles2))
jaccard_1_2 = intersection_size / union_size if union_size > 0 else 0

intersection_size_1_3 = len(shingles1.intersection(shingles3))
union_size_1_3 = len(shingles1.union(shingles3))
jaccard_1_3 = intersection_size_1_3 / union_size_1_3 if union_size_1_3 > 0 else 0


print(f"Jaccard(文件1, 文件2): {jaccard_1_2:.4f}") # 应该很高
print(f"Jaccard(文件1, 文件3): {jaccard_1_3:.4f}") # 应该很低

MinHash：估算Jaccard相似度

MinHash是一种巧妙的技术，它允许我们估算Jaccard相似度，而无需明确计算潜在巨大片集的交集和并集。它依赖于对片进行哈希处理并观察最小哈希值。

其核心思想是：如果我们对集合 $S_1$ 和 $S_2$ 中的所有片应用一个随机哈希函数 $h$ ，那么从 $S_1$ 获得的最小哈希值与从 $S_2$ 获得的最小哈希值相同的概率等于它们的Jaccard相似度。

P(\min(h(S_1)) = \min(h(S_2))) = J(S_1, S_2)

为什么会这样？考虑组合集 $S_1 \cup S_2$ 。如果我们从这个并集中随机选择一个元素 $x$ ，那么 $x$ 也属于交集 $S_1 \cap S_2$ 的概率正好是 $J(S_1, S_2)$ 。应用随机哈希函数并选择最小哈希值，就像根据哈希排序随机采样一个元素。对于并集 $S_1 \cup S_2$ 生成最小哈希值的片必须属于 $S_1$ 或 $S_2$ （或两者）。只有当那个特定的、哈希值最小的片存在于它们的交集中时，它才会为两个集合产生相同的最小值。

为了得到可靠的估计，我们不只使用一个哈希函数。相反，我们使用 $m$ 个不同的哈希函数（ $h_1, h_2, ..., h_m$ ）。对于每个文件，我们计算其片通过这 $m$ 个函数获得的最小哈希值。这为每个文件生成一个由 $m$ 个最小哈希值组成的“签名”向量 (vector)。

\text{Signature}(S) = [\min(h_1(S)), \min(h_2(S)), ..., \min(h_m(S))]

两个文件 $S_1$ 和 $S_2$ 之间的Jaccard相似度估计值，就是它们签名向量中最小哈希值匹配位置的比例。

像 datasketch 这样的库提供了高效的实现。

# 使用datasketch进行MinHash（示例）
# pip install datasketch
from datasketch import MinHash, MinHashLSH

# 参数（示例值）
num_perm = 128 # 哈希函数数量 (m)

# 为每个文件创建MinHash对象
m1 = MinHash(num_perm=num_perm)
for shingle in shingles1:
  m1.update(shingle.encode('utf8'))

m2 = MinHash(num_perm=num_perm)
for shingle in shingles2:
  m2.update(shingle.encode('utf8'))

m3 = MinHash(num_perm=num_perm)
for shingle in shingles3:
  m3.update(shingle.encode('utf8'))

# 使用MinHash签名估计Jaccard相似度
print(f"估计的 Jaccard(文件1, 文件2): {m1.jaccard(m2):.4f}")
print(f"估计的 Jaccard(文件1, 文件3): {m1.jaccard(m3):.4f}")

局部敏感哈希（LSH）：高效查找相似签名

即使有了MinHash签名，比较所有签名对（ $O(n^2)$ 次比较）对于数十亿个文件来说也太慢了。局部敏感哈希（LSH）是一种用于高效查找可能相似的候选文件对的技术，它显著减少了所需的明确比较次数。

LSH的工作原理是对MinHash签名本身进行哈希处理，使得相似的签名更有可能哈希到同一个桶中。该策略涉及将MinHash签名（长度为 $m$ ）分成 $b$ 个带（band），每个带包含 $r$ 行（因此 $m = b \times r$ ）。

对于每个带，我们对其包含的签名部分进行哈希处理。如果两个文件在至少一个带中哈希到同一个桶，它们就被认为是候选对。

如果两个文件具有高的Jaccard相似度，它们的MinHash签名很可能在许多位置匹配。极有可能至少有一个完整的带会完全匹配，从而使它们在该带中哈希到同一个桶并成为候选对。
如果两个文件具有低的Jaccard相似度，它们的MinHash签名很可能在许多位置不同。任何单个带内的所有 $r$ 个值都不太可能完全匹配，这使得它们在任何带中哈希到同一个桶的可能性很小。

通过调整参数 (parameter) $b$ 和 $r$ ，我们可以平衡找到真正近似重复项的概率（召回率）与被标记为候选的非相似对的数量（精确率）。增加 $b$ （更多带，每个带的行数 $r$ 更少）会使LSH标准更严格，减少误报，但可能遗漏一些真阳性。减少 $b$ （更少带，每个带的行数 $r$ 更多）会使文件更容易成为候选，提高召回率，但也会增加需要验证的候选对数量。

# 使用datasketch进行LSH（示例）

# LSH参数
threshold = 0.8 # 示例Jaccard相似度阈值

# 创建LSH索引 - b和r由datasketch内部计算
# 基于阈值
lsh = MinHashLSH(threshold=threshold, num_perm=num_perm)

# 索引MinHash签名（假设唯一ID为'doc1', 'doc2', 'doc3'）
lsh.insert("doc1", m1)
lsh.insert("doc2", m2)
lsh.insert("doc3", m3)
# ... 索引数百万/数十亿更多

# 查询文件1的潜在近似重复项
result_doc1 = lsh.query(m1)
print(f"文件1的近似候选项: {result_doc1}")

# 查询文件3的潜在近似重复项
result_doc3 = lsh.query(m3)
print(f"文件3的近似候选项: {result_doc3}")

# 通过LSH找到候选项后，通常会
# 检索完整文件（或详细哈希值）进行最终验证
# 并决定移除哪些重复项（例如，保留第一次遇到的）。

实现和扩展

在大型语言模型预训练 (pre-training)数据集所需的规模下实现近似重复检测涉及多个考量：

参数 (parameter)调整： 片长度（ $k$ ）、哈希函数数量（ $m$ ）以及LSH带/行（ $b, r$ ）的选择取决于数据集的特点和所需的相似度阈值。这些通常需要在数据样本上进行经验调整。常用值包括字符的 $k=5..9$ ， $m=128..512$ ，以及选择 $b, r$ 以达到特定的Jaccard阈值（例如0.8或0.85）。
分布式处理： 处理TB或PB级数据需要Apache Spark或Dask等分布式框架。工作流程通常包括：
- 并行读取分区中的文件。
- 在分区内为每个文件生成片和MinHash签名。
- 在分区内应用LSH分带和哈希，或使用分布式哈希表/连接。
- 收集候选对。
- （如果需要）对候选对执行最终的Jaccard相似度检查。
- 根据选定的策略（例如，保留最旧的、保留最短的、随机选择）筛选出已识别的重复项。
内存管理： MinHash签名紧凑，但LSH索引仍可能变得很大。可能需要高效的数据结构以及基于磁盘的LSH实现。

有效移除精确和近似重复项可以确保最终训练数据集更加多样化，减少冗余，并可能减轻重复内容中存在的偏见的放大。这会带来更高效的训练，并且通常会使模型具有更好的泛化能力。

这部分内容有帮助吗？

参考文献

Mining of Massive Datasets, Jure Leskovec, Anand Rajaraman, Jeff Ullman, 2020 (Cambridge University Press) - 这本广受认可的教材对切片（shingling）、Jaccard相似度、MinHash和局部敏感哈希（LSH）进行了全面阐述，这些是大型数据集中检测近重复项的核心方法。
Detecting Near-Duplicates for Web Crawling, Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, Geoffrey Zweig, 2000 Proceedings of the 5th International Conference on World Wide Web (ACM) DOI: 10.1145/336796.337050 - 这篇开创性论文介绍了MinHash及其在高效识别近重复文档中的应用，这是管理大型网络抓取语料库中冗余的关键一步，与LLM数据流水线高度相关。