产品

如何在 Elasticsearch 中使用模糊搜索

By
Andrew Cholakian

更新：本文中提到的托管 Elasticsearch 产品名称为 Found，现已更名为 Elastic Cloud。

Elasticsearch 的模糊查询是一种功能强大的工具，适用于多种场景。用户名搜索、拼写错误以及其他一些棘手的问题，通常都可以用这种非常规查询方式来解决。本文将阐明模糊搜索中一些容易让人困惑的选项，并深入探讨 Lucene 中 FuzzyQuery 的内部实现机制。

介绍

自然语言搜索本质上是不精确的。由于计算机无法理解自然语言，因此存在着大量不同的搜索方法，每种方法都有其各自的优缺点。Elasticsearch 所依赖的技术 Lucene 就像一把瑞士军刀，集成了多种文本处理工具。其中每个工具都是一种启发式方法，即用算法上的捷径来代替真正的语言理解。有些工具（例如 Snowball 词干提取器和 Metaphone 语音分析器）相当复杂。这些工具分别模拟了语言理解中的语法和语音特征。而其他工具则非常基础，例如前缀查询类型，它仅仅匹配单词的首字母。模糊查询的复杂程度介于两者之间；它们查找最多只需进行一定次数的字符修改（称为“编辑”）即可匹配查询的单词。例如，对“ax”进行模糊搜索会匹配到单词“axe”，因为只需要删除一个字母“e”，两者就能一致。

简单的模糊匹配

模糊查询最简便的实现方式是通过向匹配查询类型添加额外参数，如下段示例所示。在该示例中，最后一个请求是搜索“vaacuum”（多了一个字母 A），但仍应能查找到“Vacuum”产品。模糊度参数指定了结果匹配之间的最大编辑距离为 2。需要注意的是，模糊度值仅建议使用 1 或 2，这意味着查询与文档中的某个词条之间最多允许 2 次编辑。更大的差异计算成本更高，且效率低下，Lucene 不会处理。官方文档仍然提到将模糊度设置为浮点值（例如 0.5），但实际上这些值已被弃用，并且难以理解。

 # 创建索引
 PUT /fuzzy_products 
 # 创建产品映射
 PUT /fuzzy_products/product/_mapping 
 { 
 "product": { 
 "properties": { 
 "name": {
        "type": "string",
        "analyzer": "simple"
      } 
 } 
 
 } 
 # 上传一些文档
 PUT /fuzzy_products/product/1 
 {"name": "Vacuum Cleaner"} 
 PUT /fuzzy_products/product/2 
 {"name": "Turkey Baster"} 
 # 执行模糊搜索！ 
 POST /fuzzy_products/product/_search 
 { 
 "query": { 
 "match": { 
 "name": {
        "query": "Vacuummm",
        "fuzziness": 2,
        "prefix_length": 1
      } 
 } 
 } 
 }

确定编辑距离

模糊查询用于确定匹配项的度量标准是 Damerau-Levenshtein 距离公式。简而言之，两个文本之间的 Damerau-Levenshtein 距离是指使一个字符串与另一个字符串匹配所需的插入、删除、替换和交换操作次数。例如，“ax”和“axe”这两个词之间的 Levenshtein 距离为 1，因为只需要一次删除操作。

Damerau-Levenshtein 距离公式是对经典 Levenshtein 距离公式的改进，通过将交换操作也视为有效操作来扩展了原公式。两种公式均受支持，默认使用 Damerau-Levenshtein 公式，也可以通过在查询中将交换设置为 false 来选择经典 Levenshtein 公式。交换操作的实用性在比较字符串“aex”和“axe”时尤为明显。使用经典的 Levenshtein 距离公式时，“aex”与“axe”之间需要两次编辑；必须先删除“e”，然后在正确的位置插入一个新的“e”。而使用 Damerau-Levenshtein 距离公式时，只需一次操作，交换“e”和“x”的位置即可。由此推断，如果使用经典的 Levenshtein 距离公式，那么“aex”与“axe”之间的距离就与“faxes”与“aex”之间的距离相同；这说明为什么在大多数情况下，Damerau-Levenshtein 距离公式更符合直觉。

特别是在处理模糊搜索时，必须理解 Elasticsearch 中文本在可供搜索之前会先经过分析器处理。当数据被索引后，会被处理成所谓的“词条”，即数据库中实际可搜索的基本单元。搜索的对象是这些经过分析后的词条（有关词条的具体内容，请参阅《从底层开始了解 Elasticsearch》），而不是实际存储的文档。这意味着，执行模糊查询时，查询文本可能会与分析结果中未预料到的词条值进行比较，从而导致有时令人困惑的结果。这也意味着，如果某个字段启用了同义词，即使某个词根本没有出现在源文本中，它也可能被匹配。例如，如果对一个经过 n-gram 分析的字段执行模糊查询，结果可能会很奇怪，因为 n-gram 会将单词拆分成许多小的字母组合，其中许多组合之间仅相差一两次编辑距离，但实际涉及的单词却截然不同。这也意味着，如果使用 Snowball 分析器之类的工具对“running”进行模糊搜索时，会将其词干化为“run”，但不会匹配拼写错误的单词“runninga”（“runninga”的词干仍为“runninga”），因为“run”与“runninga”的词干相差超过两次编辑。这可能会造成相当大的混淆，因此，通常建议仅在打算用于模糊查询的文本上使用简单的分析器，并可能禁用同义词。为了更清楚地说明这一点，下图展示了针对 Snowball 分析文档运行模糊查询的过程。

A fuzzy query using a snowball analyzer

使用雪球分析器的模糊查询

不同类型的模糊搜索

Elasticsearch 支持多种模糊搜索类型，它们之间的区别可能会令人困惑。以下列表旨在澄清这些不同类型之间的差异。

  • 匹配查询+模糊度选项：在匹配查询中添加模糊度参数，可将普通匹配查询转换为模糊匹配查询。它会在执行搜索之前分析查询文本。
  • 模糊查询：通常应避免使用 Elasticsearch 的模糊查询类型。其行为与词条查询非常相似，不会首先对查询文本进行分析。
  • fuzzy_like_this / fuzzy_like_this_field ：一种more_like_this查询，但支持模糊匹配，并采用经过优化的评分算法，能更好地处理模糊匹配结果的特性。*
  • 建议器：建议器并非真正的查询类型，而是一种独立的操作类型（在内部基于模糊查询构建），可以与查询同时运行，也可以独立运行。建议器非常适合“您是不是要找”之类的功能。

带有模糊度参数集的匹配查询可能是所有模糊查询中最灵活的查询方式。模糊查询类型支持完全相同的行为，但不允许对查询文本进行任何分析。此外，模糊查询类型只是匹配查询功能的子集，这使其带来更多困惑而非实用价值。

fuzzy_like_this（简称 FLT）查询适用于基于包含拼写错误或其他不准确信息的大型源文本进行推荐，这些错误可通过编辑距离来区分。此类查询包含两种不同类型：fuzzy_like_this 和 fuzzy_like_this_field，两者功能相同，后者在仅使用单个字段时简化了语法。这类查询接受一个名为 like_text 的参数，即一段较大的文本（例如文章正文），并尝试查找与该文本“相似”的文档。系统会检查文章中的文本，并根据查询词在 like_text 中的出现频率对其进行加权，同时进行一些特殊调整（例如禁用坐标因子、基于源文本的 IDF），以便将源文本中的各种词条组合起来。FLT 查询最适用于语料库包含大量拼写错误的情况，否则，标准的 more_like_this 查询性能更佳。有关更多详细信息，请参阅 Fuzzy More Like This 的官方文档。

如果用户本想搜索“New York”，却输入了“New Yrok”，那么搜索建议功能就非常有用。应用程序可以利用搜索建议在用户界面中显示“您是不是要找”的提示框，提供可能的更正建议。但需要注意的是，对于自动补全搜索这种对延迟非常敏感的搜索方式，自动补全 API 的性能更佳。有关搜索建议的更多信息，请访问搜索建议页面。

性能考量

尽管 Lucene 的 Levenshtein 距离实现是目前最先进的，速度也相当快，但它仍然比普通的匹配查询慢得多。查询的运行时间会随着索引中唯一词条数量的增加而增长。也就是说，执行模糊搜索时，主要影响因素并非返回的文档数量，而是被搜索字段在整个集群中的唯一词条总数。例如，如果有 100 个文档，每个文档包含 10,000 个唯一词条，那么搜索该索引的速度将比搜索 10,000 个文档（每个文档中被搜索字段仅有 100 个唯一词条）要慢得多。

造成这种性能差异的主要原因是：标准的匹配查询可以快速检查 Lucene 内部使用的词条索引数据结构，并通过二分查找迅速定位文档。即使在大型词典中，这一过程依然高效，因为二分查找具有良好的可扩展性。另一方面，模糊查询则使用了一种更复杂的算法，涉及 DFA，必须处理大量词条。模糊搜索所需的词条数量远超二分查找，因此处理速度总是比简单的二分查找慢。例如，在英语维基百科数据集上，对词条“history”进行模糊搜索，最小相似度设为 2 时，大约需要 320 毫秒，而对同一词条进行普通匹配搜索仅需 35 毫秒，两者相差一个数量级。若将最小相似度设为 1，则搜索时间仅为 150 毫秒。需要注意的是，这些测试并未采用严格的统计方法，实际运行时间可能受到特定应用环境因素的显著影响。尤其是维基百科数据集，其词条数量远远超过大量常见用例。

通过要求匹配项的前缀与查询词完全匹配，可以显著提升性能。这大幅缩小了搜索范围，但代价是会遗漏一些拼写错误的词。前缀长度越长，性能提升越明显。例如，将“prefix_length”设置为 1，可以将上述 320 毫秒的查询时间缩短至仅 104 毫秒。增加此值还可以进一步提升速度。通常，对于包含大量词条的数据集，建议强制要求使用前缀，否则性能会很差，延迟通常会达到数百毫秒。

max_expansions 参数用于定义模糊查询在停止搜索前最多匹配的词条数量，它也会对模糊查询的性能产生显著影响。然而，减少查询词条数量可能会带来负面影响，即由于查询过早终止，导致一些有效结果无法被找到。需要注意的是，max_expansions 的限制作用于分片级别，这意味着即使将其设为 1，仍可能有多个词条被匹配，这些词条来自不同的分片。这种行为可能会让人误以为 max_expansions 并未生效，因此请注意，统计返回的唯一词条数量并不能有效判断 max_expansions 是否生效。

模糊匹配的替代方案

模糊匹配并非总是最佳选择，很多时候，通过其他技术也能找到不精确的匹配项。语音分析插件包含许多用于近似匹配的实用工具，例如元音分析器，它可以找到发音相似的词。例如，如果需要确保“run”和“ran”这样的词被视为等效词，则使用 Snowball 分析器等智能分析器更为合适。而针对拼写错误的检查，如本简短教程中所述，N-gram 分析在查询时可能运行得更快，具体速度取决于数据集。然而，N-gram 分析的缺点是会占用更多存储空间/内存，索引时处理时间略长，并且在匹配成功后可能会出现大量误报。

更多阅读

  • 想要更深入地了解 Elasticsearch 中模糊查询的性能，Lucene 核心贡献者 Mike McCandless 撰写了一篇精彩的博客文章。此外，Dawid Weiss 还制作了一段名为《Lucene 和 Solr 中的有限状态自动机》的视频，讲解了 Lucene 中的 Levenshtein 自动机和其他自动机。
  • 如果您想了解有关 Levenshtein 自动机的更多信息，Nick Johnson 有一篇很棒的文章：《超酷的算法：Levenshtein 自动机》。