模糊搜索基础：字符串相似度度量

做模糊搜索，说白了就是让机器能像人一样，在拼写不精确、表述有差异的情况下，照样找到你要的东西。我最早接触这个需求，是被一个搜索人名的工作逼出来的。用户输了个“张雪峰”，结果库里存的是“张学峰”，没了。这种问题，你靠精确匹配永远搞不定。

核心是什么？是算两个字符串有多「像」。这个「像」的程度，我们就叫它相似度。下面聊三种最常见、也最实用的度量方式。

2.1 编辑距离 (Levenshtein Distance)

编辑距离，逻辑很直观。它算的是一个字符串变成另一个字符串，最少需要做几次操作。操作只有三种：插入、删除、替换。

举个例子。“猫”变成“狗”，替换一下，一次操作就够了。编辑距离就是 1。

再看个长的。“kitten”到“sitting”：

1. k → s （替换）
2. e → i （替换）
3. 当前是 kitten -> sitten -> sitt…… 嗯，然后加个g
4. 结尾再加个 （插入）——其实要走完整过程

你算下来，总共需要 3 步。这就是编辑距离。

步骤	操作	字符串变化
1	替换 k → s	kitten → sitten
2	替换 e → i	sitten → sittin
3	替换 n → g	sittin → sitting

我记得有一次，一个同事搞了个用户输入的纠错模块。他觉得直接替换就能搞定，结果“acc”和“accommodate”差得老远，代码崩了。我告诉他，编辑距离不关心单词长度，只在意操作次数。对于短串，这个值很敏感。后来我们加了个归一化，让距离除以字符串长度，才解决了误判问题。

2.2 Jaccard 相似度

这个算法的思路跟编辑距离完全不一样。编辑距离看操作次数，Jaccard只看集合。它把字符串拆成元素，然后看两个集合的交集在并集里占多大比例。

举个例子。有两句话：

• “我喜欢吃苹果”
• “我喜欢吃香蕉”

我们把每个词当集合元素。它们都有“我”、“喜欢”、“吃”，交集是3个词。并集是“我、喜欢、吃、苹果、香蕉”，共5个。Jaccard系数 = 3/5 = 0.6。

说白了，它只看「有没有出现过」，不看「出现几次」和「在哪出现」。

字符串 A	字符串 B	交集大小	并集大小	Jaccard 系数
apple banana	apple orange	1	3	0.333
cat dog fish	cat bird	1	4	0.250

我习惯在做垃圾文本过滤的时候用 Jaccard。为什么？因为垃圾信息里经常重复出现某些关键词，顺序不重要，出现了就算。Jaccard对顺序不敏感，反而成了优势。

2.3 余弦相似度

余弦相似度在文本搜索里很常用。它是看两个向量之间夹角的余弦值。夹角越小，代表方向越接近，相似度越高。

怎么把字符串变成向量？最常见的是词袋模型。你要给每个词一个维度，出现就给分，不出现就给0。

比如“我 喜欢 打球”和“我 喜欢 跑步”。词表是：“我”、“喜欢”、“打球”、“跑步”。

• A 向量：[1, 1, 1, 0]
• B 向量：[1, 1, 0, 1]

然后算余弦公式：

cos(A, B) = (A·B) / (|A| * |B|)

点积 = 1*1 + 1*1 + 1*0 + 0*1 = 2

|A| = sqrt(1+1+1) ≈ 1.732

|B| = sqrt(1+1+1) ≈ 1.732

结果 = 2 / (1.732 * 1.732) ≈ 0.667

余弦相似度是0到1之间的值。0代表无关，1代表完完全全一样。

跟 Jaccard 的区别：Jaccard只看有没有，余弦相似度会考虑频率。如果一句话“喜欢”出现10次，另一句只有1次，余弦相似度会降低，但Jaccard完全不在乎。

我建议在做短文本匹配时，优先试用编辑距离；如果文本是整段整段的，余弦相似度效果更好。Jaccard则适合做近似去重。

2.4 三种方法对比一览

度量方法	核心思想	对顺序敏感吗？	适合场景
编辑距离	操作次数	是	拼写纠错、基因序列
Jaccard	集合交集占比	否	文本去重、近似匹配
余弦相似度	向量夹角	否（但可引入词序）	文档相似度、推荐系统

你看，没有哪种方法是万能的。我遇到过一个项目，用的余弦相似度，结果因为句子太短，几乎全是1。后来切成字符级，再用Jaccard，效果才出来。说白了，选对工具才是真本事。

下面这张图帮你理清怎么根据输入特征选方法。你可以想想看，你手头的任务更接近哪种情况。