文本相似度：四类问题与五大类算法全解

先说清楚你指的是哪种相似度

四个不同的概念，在打开一个库之前先明确自己的需求是值得的：

表面相似度。 字符是否几乎相同？Jonathan Smith 对比 Jonathon Smtih。拼写错误、OCR 识别错误、音译。

集合相似度。 内容是否大部分相同？一篇改了标题的文章的两个副本。这是近重复检测。

主题相似度。 讨论的是同一件事吗？两篇关于利率政策的文档，词汇有重叠但并非副本。

语义等价性。 含义相同吗？how do I cancel 对比 ending your subscription，没有任何实词重叠。

没有任何单一指标能覆盖这四种。一个擅长检测前者的方法，在设计上对后者必然是盲的，反之亦然。

The methods, by what they detect

Complexity, and why all-pairs is out

这个算术规律支配着每一个实际系统：对 n 个文档的全量两两比对，比较次数为 n(n−1)/2。n = 1,000 时约 50 万次——微不足道。n = 100,000 时是 50 亿次。n = 1,000,000 时约 5000 亿次，即使以每次比较最优的 100 纳秒计算，最便宜的方法也需要约 14 小时 CPU 时间。如果用编辑距离，每次比较需要 10 微秒，那就超过 150 年了。

这就是为什么上表中的每种方法都分属两个家族，这也是本文最有用的区分方式。可索引的方法——哈希、MinHash、SimHash、稀疏向量、稠密向量——通过倒排索引或近似最近邻结构在亚线性时间内找到候选集，从不枚举全部 pair。而只能逐对计算的方法——编辑距离、Jaro-Winkler、cross-encoder——是对已有的一对文本生成分数。架构总是如此：先建索引获取候选，再对候选精确打分。试图用只能逐对计算的方法来做搜索，是把两小时能完成的任务变成不可能的任务的常见错误。

The cost column, derived

假设均可替换： 100 万文档，每篇 300 token，共 3 亿 token。一台 4 核 vCPU 机器，假设费用为每小时 $0.05。

MinHash 去重。 Shingling 和哈希的复杂度与字符数成线性关系。百万级文档在一台机器上需要几分钟到几小时，计算成本不到 $1，加上签名存储——每文档 128 个 32 位哈希值共 512 字节，总共约 512 MB。

TF-IDF 索引和余弦搜索。 一次遍历构建，之后查询从倒排索引提供。计算成本与上述方案相当。内存占用是稀疏矩阵，对于 3 亿 token 和剪枝后的词表，完全在普通服务器的容量范围内。

稠密向量嵌入。 3 亿 token，按每百万 token $0.02 的嵌入成本计算，一次约 $6——加上语料库或模型更新时需要重新嵌入的成本，这是人们常忽略的部分。768 维 float32 存储每文档 3 KB，约 3 GB，再加上 ANN 索引。了解向量存储的实际成本以及维度数为何是预算决策。

Cross-encoder 重排。 按 pair 计费而非按文档计费，所以成本由候选数量决定。对 100 万次查询各取前 50 名重排，就是 5000 万次模型调用，与上面所有方法不在同一个量级，这也是它只应该在短列表上运行的原因。

值得提取的核心规律：便宜的方法便宜几百倍，而不是几个百分点；昂贵的方法之所以还能承受，是因为先跑了某个便宜的方法。

Choose by the failure you cannot afford

准确性不是正确的衡量轴，因为每种方法都有特征性的失效方向。问自己：哪种错误最不能接受？

如果合并两个不同客户是不可接受的，就需要一种能看到字符的方法——嵌入模型会兴高采烈地把 Invoice 4471 和 Invoice 4417 给出 0.99 的余弦相似度。如果遗漏改写是不可接受的，就需要嵌入，因为再多的词项加权也无法建立 cancel 到 terminate 的联系。如果需要向监管者或客户解释决策，稀疏加权是唯一能把分数分解成可解释项的方法。如果语料库大到全量两两比对不可行——根据上面的算术，任何超过约十万文档的语料库都是如此——那么可索引性不是偏好，而是约束条件，它会让表格中一半的方法失效。

表格中只有一行有按 token 计的价格，值得去核实而不是假设：嵌入的计费方式和其他一样按每百万 token 计，通常只是聊天价格的一小部分，所以上面那个每百万文档 $6 的数字只需一次乘法就能得到你的真实成本。不过，如果任务是去重，实话是 MinHash 的成本只有其百分之一，检测的正是去重真正需要的东西，而且在模型版本更新时不需要重新运行。

TF-IDF Explained and Implemented

Spell Correction and Fuzzy Matching

Topic Modelling: LDA vs Embedding Clustering