快速近重复匹配 —

快速近重复匹配是一种通过利用 Rabin-Karp 算法 来快速找到文档中近重复片段的方法。该算法可用于在预训练语料库中统计查询的近重复，以促进对大型语言模型 (LLM) 中记忆的分析。

该存储库包含快速近重复匹配算法的实现以及该算法的基准测试，核心功能以 neardup crate 的形式提供。

方法

快速近重复匹配

• 输入：后缀 $s$，文档 $d$ 和 $n$-gram 的 $n$
• 输出：$d$ 是否与 $s$ 有近重复片段

Python 伪代码

def fast_near_duplicate_matching(s: list[int], d: list[int], n: int, threshold: float) -> bool:
    l_s = len(s)
    l_d = len(d)
    H = set(ngram(s, n))
    for i in range(max(l_d - l_s, 0)):
        if d[i:i+n] in H:
            for j in range(max(i - l_s + n, 0), i):
                t = d[j:j+l_s]
                if Jaccard_W(s, t) >= threshold:
                    return True
    return False

您可以使用快速哈希函数，如 fxhash 或 滚动哈希。

当 $n$-gram 的大小较小时，fxhash 比滚动哈希更快。然而，当 $n$ 的大小较大时，滚动哈希比 fxhash 更快，因为滚动哈希可以在 $O(1)$ 时间内计算出下一个 $n$-gram 的哈希值。

如何运行

您可以通过运行以下命令来计数文档中查询的近重复（示例查询（2 个查询）和文档（100 个文档）位于 sample_data 文件夹中）

$ cargo run --release -- --search-dir ./sample_data --query-path ./sample_data/query.jsonl --threshold 0.6 --n 10
[2024-08-07T10:59:40Z INFO  neardup] query_list_all: 2
[2024-08-07T10:59:40Z INFO  neardup] search_path_list len: 1
[2024-08-07T10:59:40Z INFO  neardup] path: "./sample_data/pythia-00000-00999.jsonl.gz" start loading token_ids_list
[2024-08-07T10:59:40Z INFO  neardup] loaded token_ids_list
[2024-08-07T10:59:40Z INFO  neardup] query: 0 count: 1
[2024-08-07T10:59:40Z INFO  neardup] query: 1 count: 1
[2024-08-07T10:59:40Z INFO  neardup] path idx: 0 finished
[2024-08-07T10:59:40Z INFO  neardup] count: [1, 1]

Pythia 数据集中的近重复计数

您可以从 这里 下载 Pythia 数据集。下载数据集后，您可以通过运行以下命令将其转换为程序可以读取的格式

$ python scripts/prepare_pythia.py --output_dir path/to/output/folder --pythia_data_path path/to/merged/folder/document

然后，您可以通过运行以下命令来计数 Pythia 数据集中查询的近重复

$ cargo run --release -- --search-dir path/to/output/folder --query-path path/to/output/folder/query.jsonl --threshold 0.6 --n 10

基准测试

您可以运行三种方法的基准测试

• 使用 fxhash 的快速近重复匹配
• 使用 滚动哈希 的快速近重复匹配
• 朴素 近重复匹配

$ cargo bench

参考文献

• Rabin-Karp 算法
• fxhash
• Pythia