超快语义模糊搜索，万亿级文本秒级响应
SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora
- 基于后缀数组与向量表示，实现高效灵活的模糊匹配
- 在1.4万亿词元数据集上搜索延迟低于0.3秒
- 适合需要快速检索和抗污染检测的NLP应用
我们提出SoftMatcha 2，一种超快速且灵活的搜索算法，可在不到0.3秒内对万亿级自然语言语料库进行搜索，并支持替换、插入、删除等语义变体。该方法基于后缀数组的字符串匹配，将词语表示为向量以实现语义灵活性。为缓解语义松弛带来的组合爆炸问题，采用两个关键算法设计：动态语料感知剪枝和基于磁盘感知设计的快速精确查找。理论上分析表明，该方法可抑制搜索空间的指数增长。实验上，在FineWeb-Edu（1.4T tokens）数据集上，其搜索延迟显著低于infini-gram、infini-gram mini和SoftMatcha。实际应用中，可发现现有方法遗漏的训练语料基准污染问题，并提升信息检索与改写检测效果。我们还提供了跨七种语言的在线演示。
原文摘要 · Abstract (English)
We present SoftMatcha 2, an ultra-fast and flexible search algorithm that enables search over trillion-scale natural language corpora in under 0.3 seconds while allowing semantic variations in the form of substitution, insertion, and deletion. Our approach employs string matching based on suffix arrays that scales well with corpus size, and represents words as vectors, which underpin its semantic flexibility. To mitigate the combinatorial explosion induced by the semantic relaxation of queries, our method is built on two key algorithmic ideas: dynamic corpus-aware pruning and fast exact lookup enabled by a disk-aware design. We theoretically analyze the efficiency of the proposed method, indicating that it can mitigate exponential growth in the search space. Empirically, on FineWeb-Edu (Lozhkov et al., 2024) (1.4T tokens), it attains substantially lower search latency than existing methods: infini-gram (Liu et al., 2024), infini-gram mini (Xu et al., 2025), and SoftMatcha (Deguchi et al., 2025). As a practical application, our method uncovers benchmark contamination in training corpora that existing approaches miss, and it also benefits information retrieval and paraphrase detection. We also provide an online demo of fast, soft search across corpora in seven languages.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。