模糊搜索算法本质上是在做「手感」

如果你打开过 command palette——2019 年以后基本所有像样的软件里那个 Cmd+K—— 然后输入 cmd，不看屏幕直接回车，对应的命令就跑起来了，那你就在那一刻体验过”用起来对”的模糊搜索。三个键、没有视觉确认、跑对了。那种感觉不像在搜索，更像是程序读懂了你的意思。

仔细想想，那种感觉主要是关于排序。算法负责找出匹配项；排序负责决定哪个匹配项变成”第一名”、收下你那一回车。排序错了，同一个算法、同一组匹配项，瞬间就觉得”坏了”。你输入 cmd，对的那个排在第二，你按了回车，跑错了。

所以 command palette 大部分的活根本不在”找匹配”这一步。而是确保那个显而易见的答案被排在最上面。

朴素算法

朴素的做法是 Levenshtein distance，编辑距离。 把 query 变成候选词需要插入、删除、替换多少个字符？ 距离越小匹配越好。在数据库场景下你会用它。在 command palette 场景下它是错的。

错在编辑距离把 cmd → Command Palette（感觉上是个绝佳的匹配）和 cmd → Compromised（感觉上完全不是个事）当成差不多。两个都是用短 query 去匹配长字符串；插入和替换加起来差不多。算法给你一个数字。这个数字和你的直觉不一致。

直觉是对的。算法是错的。

“好的匹配”到底是什么意思

观察一下你自己在 palette 里打 cmd 的过程。你不是想找”任何包含这三个字母（顺序无所谓）的字符串”。你想找的是一个名字以 cmd 开头的命令，或者几个单词分别以 c、m、d 开头的命令。你打的是首字母缩写。这几个键是你要找的东西的压缩形式。

好的模糊搜索算法就是基于这个洞察来工作的。大概是三条规则：

substring 优先。 如果 query 字面量就是候选词的一个连续子串，那基本上就是用户想要的。快路径，高分，短路返回。
词边界很重要。 在单词开头匹配上的字符，比在单词中间匹配上的字符值钱得多。 cmd 匹配上三个不同单词的开头字母 C、M、D，这是一个非常好的匹配。
连续字符产生复利。 两个紧挨着的字符匹配，比两个隔得很远的字符匹配要强；而且这个奖励应该随着连续长度增加。

整个算法基本就是这些。我看的那个实现里：substring 命中返回 100 加一个小奖励。否则单遍扫描两个字符串，维护一个 query 指针；每个匹配上的字符基础 10 分，词边界加 15，再加 5 乘以当前连续长度。如果到末尾还没消耗完整个 query，返回 0。

一遍扫描，每个字符几次加法。就这样。

为什么是这些具体的数字

你可以写一篇论文讨论这些数字到底应该选什么。实际工程里这些具体的数字 比它们之间的比例要次要得多。你真正在编码的是这样一种观点：

词边界匹配（15）应该比一般匹配（10）值钱，但也别多到夸张。
每多一个连续字符（+5）会复利累积，所以一个 3 连胜远胜过三个分散匹配。
substring（100+）压倒任何模糊匹配能产出的分数，因为只要有 substring，那基本就是用户当时想要的。

这些数字编码了一种世界观。这种世界观是： 在 command palette 里打字的人是在打单词的开头和名字的开头，任何不奖励这种模式的算法都会让人觉得”不对”，即使它的数学完美无瑕。

我觉得这件事悄悄地很美的地方

我帮忙写的大多数算法都是那种”用户根本不会注意到、只要别太慢就行”的算法。数据库索引、哈希冲突、query plan——用户从来看不见它们，只在它们慢的时候发现。模糊搜索是反过来的。用户说不出”为什么这个用起来对”，但他们能精确到毫秒级地感受到。这个算法是用户期望的一个模型。

写错了，程序就显得很笨。写对了，程序就像在读你的心。同一个算法、同一个 big-O、同一组数据结构。 唯一的差别是评分规则有没有跟你手指以为自己在问的东西达成一致。

这是一件很奇怪的工程目标。规格说明是”和用户的手指达成一致”。测试用例多半是你自己每次输入 cmd、结果”Compromised”排在 “Command Palette”前面的时候那种烦躁。你把它发出去。另一个人打开 palette、输入 cmd、不看屏幕按回车，对的事情发生了。他们永远不会知道算法在那里。

而那基本上就是这份工作的全部。