相似性搜索：选择正确的匹配算法
相似性搜索是从一组项目中找出与给定查询最"相似"的项目的过程——基于模糊逻辑，而不是要求精确匹配。它是推荐引擎、语义搜索、记录去重、拼写检查器以及这里的智能体/工具路由的支柱。
梯形图转SCL | 博途AI辅助编程文档 | AI模型价格对比 | AI工具导航 | ONNX模型库 | Vibe Coding教程 | PLC在线仿真器 | Tripo 3D | Meshy AI | ElevenLabs | KlingAI | ArtSpace | Phot.AI | InVideo
想象一下，您正在构建一个智能体路由器。用户输入一个查询，您的工作是找出您注册的哪个智能体（每个都有一个简短的文本描述）最合适——而无需调用 LLM 来判断。这是一个相似性搜索问题，您选择的算法可以决定路由器是"正常工作"还是默默地将每个查询发送到错误的智能体。
我将使用一个示例，以便您可以看到每个算法在相同输入上的具体行为。
示例： 一个小型智能体注册表——一组智能体，每个都有一个简短的描述——以及一个传入的客户端查询。相似性算法的工作是根据每个智能体描述对查询进行评分，并返回得分最高的智能体（argmax）。
客户端查询："我想总结这个文档"
智能体注册表：
智能体 A → "总结文档"
智能体 B → "生成文档字符串"
智能体 C → "添加到任务板和事件"
对于人类读者来说，正确的智能体显然是智能体 A——下面演练的价值在于看到每个算法在多大程度上同意这一点，以及朴素算法可能在哪里出错。
1. 什么是相似性搜索？
相似性搜索是从一组项目中找出与给定查询最"相似"的项目的过程——基于模糊逻辑，而不是要求精确匹配。它是推荐引擎、语义搜索、记录去重、拼写检查器以及这里的智能体/工具路由的支柱。
广义上，每种相似性搜索技术都归结为两件事：
- 表示要比较的项目（将文本转换为标记、字符或向量）。
- 评分两个表示有多接近，使用距离度量（越低=越相似，例如编辑距离）或相似性分数（越高=越相似，例如余弦相似性、Dice系数）。
步骤2有两种主要的算法族：
本文主要关注词汇/模糊匹配族（因为这是当您明确不希望 LLM 或嵌入模型进行验证时使用的方法），但它也涵盖了嵌入的位置，以便您知道何时应该使用它们。
2. 步骤1：预处理（在任何相似性算法之前）
在比较任何两个字符串之前，您几乎总是希望标准化它们。比较原始的、未处理的文本往往会因为停用词、大小写或单词变形而在语义相似的短语上受到惩罚。
使用 spaCy (en_core_web_sm)，典型的预处理管道执行：
- 标记化 — 将文本分割成单个标记。
- 停用词移除 (token.is_stop) — 删除低信息词，如"is"、"the"、"a"。
- 标点符号移除 (token.is_punct) — 删除标点符号标记。
- 词形还原 (token.lemma_) — 将单词还原为词典/基本形式（例如"summarizes" → "summarize"，"reads" → "read"）。
- 小写化 — 标准化大小写，使"Document"和"document"不被视为不同的标记。
将其应用于我们的运行示例：
查询："我想总结这个文档"
→ 预处理后：['want', 'summarize', 'document']
智能体 A："总结文档"
→ 预处理后：['summarize', 'doc']
智能体 B："生成文档字符串"
→ 预处理后：['generate', 'doc', 'string']
智能体 C："添加到任务板和事件"
→ 预处理后：['add', 'taskboard', 'event']
注意：词形还原将"summarizes"标准化为"summarize"，但它不会将"doc"转换为"document"；这是两个真正不同的标记。这是真实智能体描述中经常出现的问题（缩写、简写），这正是为什么仅靠标记重叠方法并不总是足够的。
提示： 还要考虑词干提取与词形还原的权衡、移除重复标记，以及可选地按词性过滤（仅保留名词/动词）（如果描述嘈杂）。这种预处理使算法更准确。
3. 步骤2：相似性算法
3.1 基于标记/集合的算法
这些将文本视为标记袋（集合），而不是字符序列。它们快速、可解释，并且非常适合像智能体元数据这样的简短描述。
a) Sorensen-Dice系数（通常简称为"Dice系数"）
也通常被称为Sorensen-Dice系数（或Dice系数），是Jaccard相似性的近亲，但对重叠的加权方式不同。
它衡量两个集合之间的标记重叠，将交集加权两次：
Dice(A, B) = (2 × |A ∩ B|) / (|A| + |B|)
示例 — 对所有三个智能体评分查询：
查询标记 (Q)：{want, summarize, document}
智能体 A 标记：{summarize, doc}
交集 = {summarize} → |Q ∩ A| = 1
Dice = (2 × 1) / (3 + 2) = 2/5 = 0.400
智能体 B 标记：{generate, doc, string}
交集 = {} → |Q ∩ B| = 0
Dice = 0.000
智能体 C 标记：{add, taskboard, event}
交集 = {} → |Q ∩ C| = 0
Dice = 0.000
Argmax → 智能体 A (0.400)，而且差距不小——Dice已经将正确的智能体与其他两个清晰地分开，因为"summarize"是一个共享的精确标记。
- 优点： 简单、快速、可解释，在短文本（如智能体描述或标签）上效果良好。
- 缺点： 纯粹的标记重叠——"summarization"和"summarize"不被视为匹配，除非先进行词形还原（这就是为什么步骤1如此重要）。
b) Jaccard相似性
与Dice非常相似，但除以并集而不是总和：
Jaccard(A, B) = |A ∩ B| / |A ∪ B|
实际示例（相同注册表）：
智能体 A：|Q ∩ A| = 1，|Q ∪ A| = {want, summarize, document, doc} = 4 → Jaccard = 1/4 = 0.250
智能体 B：|Q ∩ B| = 0 → Jaccard = 0.000
智能体 C：|Q ∩ C| = 0 → Jaccard = 0.000
Argmax → 智能体 A (0.250) — 与Dice相同的获胜者，只是绝对分数较低，这是预期的（Jaccard对于相同的集合总是≤ Dice）。
- 优点： 与Dice相同——简单、快速，非常适合短标记集；也比较标签集、类别或标记化的n-gram非常常见。
- 缺点： 与Dice相同；Jaccard分数对于相同的集合总是≤ Dice分数，因此如果您设置相似性阈值，请记住两者在数值上不可互换。
Dice与Jaccard — 这重要吗？ 对于排名来说不重要：Dice是Jaccard的重新缩放。如果您只是选择最佳匹配，两者的工作方式相同。只有在设置固定相似性阈值时才会出现分歧：对于相同的重叠，Dice分数更高（它除以集合大小总和，而不是并集）。在实践中，Jaccard是更标准的"集合相似性"度量（在MinHash/LSH中使用）；Dice在NLP/IR文本匹配上下文中更常见。
3.2 基于字符的（编辑距离）算法
这些算法逐字符比较字符串，这使它们非常适合捕获拼写错误、拼写变体和标记重叠方法完全错过的形态相似性。
c) Jaro-Winkler相似性
Jaro-Winkler衡量字符级别的相似性，考虑匹配字符和转置（Jaro距离），然后如果两个字符串共享公共前缀（"Winkler"调整），则提升分数。它特别适合像名称这样的短字符串，或单字比较。
对于每个智能体，获取每个查询标记×描述标记对中的最佳（最大）分数。在我们的注册表上实际运行（jellyfish.jaro_winkler_similarity）：
智能体 A：最佳对 = ("summarize", "summarize") → 1.000 ← 精确标记匹配
智能体 B：最佳对 = ("document", "doc") → 0.854 ← 共享"doc"前缀
智能体 C：最佳对 = ("document", "event") → 0.658
Argmax → 智能体 A (1.000) — 仍然是正确的，但仔细看看智能体 B：0.854，对于错误的智能体来说这是一个高分。这是Jaro-Winkler的前缀加权对您不利的地方——"document"和"doc"共享完整的前缀，因此算法将它们评为非常相似，即使这里的"doc"更接近"docstring"的意思，而不是"文档"。仅Jaro-Winkler几乎可以将查询路由到错误的智能体，纯粹是因为它如何加权共享前缀。
这就是为什么建议将基于标记的方法与基于字符的方法集成——Dice/Jaccard会将智能体 B 标记为0.0，捕获了Jaro-Winkler单独错过的部分。
- 优点： 捕获标记重叠无法捕获的近似匹配——例如"summarize"与"summarizing"与"summarization"即使没有词形还原也能获得高分，因为它们共享长公共前缀。在短字符串上非常快。
- 缺点： 旨在比较单个单词/短字符串，而不是完整句子——直接使用Jaro-Winkler比较两个长句子效果不佳（这就是为什么在上面的示例中，您逐标记比较并取最大值/平均值，而不是将整个预处理短语塞入一个字符串中）。对前缀敏感，但对单词后面的字符不敏感。
d) Levenshtein距离（编辑距离）
Levenshtein距离是将一个字符串转换为另一个字符串所需的最少单字符编辑次数——插入、删除或替换。它是最著名的"编辑距离"度量，也是许多拼写检查器的基础。
Levenshtein("summarize", "summarization")
要将编辑距离转换为相似性分数（0到1，可与其他算法比较），请按较长字符串的长度进行标准化：
similarity = 1 — (edit_distance / max(len(s1), len(s2)))
在我们的注册表上运行此操作（每个智能体的最佳标记对匹配，通过rapidfuzz）：
智能体 A：最佳对 = ("summarize", "summarize") → 距离 0 → 相似性 1.000
智能体 B：最佳对 = ("document", "doc") → 距离 5 → 相似性 0.375
智能体 C：最佳对 = ("want", "event") → 距离 3 → 相似性 0.400
Argmax → 智能体 A (1.000)，请注意Levenshtein不会陷入与Jaro-Winkler相同的陷阱："document"与"doc"在这里只得到0.375，因为Levenshtein直接计算5个缺失字符，而不是像Jaro-Winkler的加权那样奖励共享前缀。这是一个有用的具体说明，说明为什么两种基于字符的算法不可互换——它们可能对相同的字符串对有不同的看法。
- 优点： 捕获拼写错误和轻微拼写变体的黄金标准（"summarize"与"sumarize"）；直观且易于理解；存在许多快速实现（python-Levenshtein、jellyfish、rapidfuzz）。
- 缺点： 与Jaro-Winkler一样，它用于单词/短字符串比较，而不是句子——逐标记应用它（取最佳匹配），而不是在整个描述上应用。它也是区分大小写和顺序敏感的："document summary"与"summary document"的评分会比您预期的要差，即使含义相同。
- 需要了解的变体： Damerau-Levenshtein扩展了Levenshtein，还将相邻字符转置（例如"the" ↔ "teh"）视为单次编辑而不是两次——如果您的查询来自人类输入，其中交换字母很常见，这很有用。
e) Bitap算法（Shift-Or / Baeza-Yates–Gonnet）
Bitap是一种快速的位运算实现，用于查找文本是否包含与模式"近似相等"的子字符串（它也依赖于底层的编辑距离）。它是Unix agrep背后的算法。当您需要在较长文本中搜索具有少量允许错误的短模式时，它表现出色。
- 与智能体匹配相关时： 对于整句描述匹配不太常见，如果您在长文档或日志中搜索已知关键字/短语（允许拼写错误），则更有用。
- 缺点： 在非常长的模式上性能会下降；您需要提前决定"错误预算"（最大允许编辑次数）。
3.3 基于序列/频率的算法
f) N-gram相似性
不是比较整个标记，而是将每个字符串分解为n个字符（或单词）的重叠序列，并比较这些n-gram的集合/频率。例如，"summarize"的三元组（n=3）：
sum, umm, mma, mar, ari, riz, ize
例如，
比较"summarize"和"summarization"之间的n-gram集合，即使没有任何词形还原步骤，也会显示共享前缀的三元组高度重叠。
- 优点： 对拼写错误和单词顺序洗牌具有鲁棒性（不像Levenshtein在字符级别对顺序敏感，但不像Dice/Jaccard对整个标记需要精确匹配）。当词形还原不可用时，作为后备方案效果良好。用于许多拼写检查器和搜索引擎。
- 缺点： 选择n很重要——太小（n=2）一切看起来都相似；太大（n=5+）它的行为就像精确匹配。设置起来比简单标记重叠更复杂。
3.4 基于向量/嵌入的算法（用于上下文——不是"LLM验证"，但仍然是基于ML的）
如果词汇/模糊方法不够准确（例如查询说"压缩此文件"，而描述说"总结文档"——零标记或字符重叠，但含义相同），下一层次是嵌入+距离度量。这不需要LLM来"判断"匹配——轻量级句子嵌入模型（例如sentence-transformers）将文本转换为向量，然后普通距离度量对它们进行排名：
对于大型智能体注册表（数百/数千个智能体），精确最近邻搜索变得很慢，因此使用**近似最近邻（ANN）**方法：
- HNSW（分层可导航小世界）— 基于图，高召回率，广泛用于向量数据库。
- LSH（局部敏感哈希）— 将相似向量哈希到同一个存储桶中。
- k-d树/球树 — 适合低维数据，不能很好地扩展到高维嵌入。
4. 手册：您应该使用哪种算法？
您可以将此用作快速决策清单。
您是在将短文本与短文本匹配吗（例如查询与智能体描述/标签）？ → 在预处理标记上从Dice/Sorensen或Jaccard开始。便宜、快速、可解释。
您的查询/描述可能包含拼写错误、缩写或拼写变体吗？ → 在标记级别添加Levenshtein或Jaro-Winkler（每个标记的最佳匹配），以捕获纯标记重叠会评为零的近似匹配。
您需要在较长文本块中检测已知短语，允许一些错误吗？ → 如果语料库较小，使用Bitap（在线，无需索引），如果较大，使用n-gram索引。
您的匹配对人类输入风格错误（相邻字母交换）敏感吗？ → 使用Damerau-Levenshtein而不是普通Levenshtein。
您期望查询和描述即使含义相同也会在措辞上有所不同吗（例如"summarize"与"condense"与"give me the gist"）？ → 词汇/模糊方法将失败——您需要嵌入+余弦相似性。
您需要单个稳健分数而不是选择一种算法吗？ → 集成它。 一种常见且有效的模式：计算Dice（标记重叠）+最佳配对Jaro-Winkler（字符相似性），然后将它们组合（例如加权平均或取最大值），这样您既可以捕获精确关键字重叠，也可以捕获近似拼写变体。
5. 综合应用：对整个注册表进行端到端评分
查询："我想总结这个文档"
四个算法中有三个给智能体A最高分，Jaro-Winkler单独也正确识别了智能体A，但安全裕度小得多（1.000对0.854）——这表明它是最不可靠的单一信号，无法单独用于这种短描述匹配的路由。
路由智能体的实用要点： 不要只取一种算法原始分数的argmax。计算至少一个基于标记的分数（Dice/Jaccard）和一个基于字符的分数（Levenshtein或Jaro-Winkler），将它们组合（例如平均值或加权和），并路由到组合分数获胜的智能体——并考虑标记低置信度案例（前两个智能体之间差距小）作为后备（例如要求用户澄清，或者仅在那时调用LLM）。
6. 结束语
- 推荐预处理（停用词移除+词形还原）
- 基于标记集的方法（Dice、Jaccard） 是像智能体描述这样的短文本最便宜的初步筛选。
- 基于字符的方法（Levenshtein、Jaro-Winkler、Damerau-Levenshtein） 捕获标记方法错过的拼写错误和近似拼写——逐标记应用它们，而不是在整个句子上。
- N-gram和Bitap 在您需要子字符串/拼写错误容忍搜索时很有用，特别是在大规模情况下。
- 嵌入+余弦相似性 是当含义比措辞更重要时的正确工具，只是数字向量比较。
- 如有疑问，集成两种不同族的算法（一种基于标记，一种基于字符），而不是依赖单一分数。
原文链接: Similarity Search: A Practical Checkbook for Choosing the Right Matching Algorithm
汇智网翻译整理，转载请标明出处
