如何提供最佳搜索结果：深入了解全文搜索引擎

搜索栏是浏览网页不可或缺的一部分。无论我们是在购物、欣赏音乐还是计划度假，总有一个专门的搜索引擎在工作，以简化我们的生活。您有没有想过这些搜索引擎实际上是如何工作的？在本文中，我们将深入研究其中一个搜索引擎的内部运作：Meilisearch。

索引时间：从数据到文档

索引是一个基本过程，包括收集、解析和存储数据以供后续检索。它在使搜索引擎能够提供快速且相关的结果方面起着至关重要的作用。

高性能存储引擎

Meilisearch 以离散记录的形式存储数据，称为“文档”，这些文档被组合成称为“索引”的集合。在底层，Meilisearch 使用 LMDB (Lightning Memory-Mapped Database) 键值存储，该存储在数据库应用程序中已被证明具有稳定性和广泛的使用。顾名思义，键值存储是存储系统，它将数据组织为键值对的集合。

键值条目示例

键值存储提供灵活性、快速访问时间和高效性能，有助于用户获得快速响应的交互。通过一次只允许一个写入过程，LMDB 避免了与同步相关的问题。因此，它使无限数量的并发读取器能够快速访问最新的、一致的数据。

在将数据存储到其键值存储之前，Meilisearch 必须对其进行彻底的预处理。这就是分词化的用武之地。

从单词到词元

分词化涉及两个主要过程：分段和规范化。

分段包括将句子或短语拆分为更小的单元，称为词元。

Meilisearch 使用（并维护）名为 Charabia 的开源分词器。分词器负责从文档字段中检索所有单词（或词元）。

然后是规范化。单词根据每种语言的特殊性进行规范化。对于像法语这样的罗曼语，此过程包括将单词设置为小写字母并删除变音符号，例如重音符号。例如，像“Le café de Nicolas”这样的句子被转换为“le cafe de nicolas”。

分词化过程中分段和规范化阶段的示例

在分段和规范化单词后，引擎需要对它们进行分类。使用适当的数据结构来组织词元对于性能至关重要。这将稍后允许快速检索最相关的搜索结果。

存储词元

现代全文搜索引擎（如 Meilisearch）具有前缀搜索、错字容错和地理搜索等功能。每种数据结构都有其自身的优点和缺点。在设计搜索引擎时，我们的团队仔细选择了最适合启用这些功能的数据结构，而不会影响速度。

在本节中，我们将探讨哪些数据结构为 Meilisearch 提供支持。

倒排索引

首先，我们需要谈谈倒排索引。毫无疑问，它是因其重要性而脱颖而出的数据结构。Meilisearch 使用它来在搜索时快速返回文档。

倒排索引将文档中的每个单词映射到出现该术语的文档集，以及附加信息，例如它们在文档中的位置。

从给定文档生成的倒排索引的图示，展示了关键字到文档 ID 的映射

通过将单词存储一次并将其与出现它们的文档关联起来，倒排索引利用了术语在文档中的冗余。因此，Meilisearch 不需要浏览所有文档即可找到给定的单词，从而加快了搜索速度。

Meilisearch 每个文档索引大约创建 20 个倒排索引，使其成为实例数量最多的数据结构之一。实际上，为了提供即时搜索体验，引擎需要在索引时预先计算大量内容：单词前缀、包含可筛选属性的文档等等。为了更好地理解倒排索引的工作原理，请阅读有关[索引最佳实践](/blog/best-practices-for-faster-indexing/

Roaring 位图

Roaring 位图是压缩数据结构，旨在高效地表示和操作整数集。

Meilisearch 在其倒排索引中广泛使用 roaring 位图来表示文档 ID。Roaring 位图提供了一种节省空间的方式来存储大型整数集并执行集合运算，例如 并集、交集和差集。这些操作在通过允许根据文档与其他文档的关系来包含或排除特定文档来优化搜索结果方面起着至关重要的作用。

有限状态转换器

有限状态转换器 (FST) 是一种结构化数据表示形式，非常适合执行字符串匹配操作。它表示一系列按从小到大顺序排列的状态，单词按字典顺序排列。

有限状态转换器也称为单词字典，因为它包含索引中存在的所有单词。Meilisearch 依赖于两个 FST 的使用：一个用于存储数据集的所有单词，一个用于存储最常见的 prefixes。

FST 非常有用，因为它们支持压缩和延迟解压缩技术，从而优化内存使用和存储。此外，通过使用自动机（例如正则表达式），它们可以检索与特定规则或模式匹配的单词子集。此外，这使得能够检索以特定前缀开头的所有单词，从而实现快速、全面的搜索功能。

FST 以其紧凑的设计，比倒排索引具有更小的数据结构的额外优势。正如我们稍后将看到的那样，这有助于更快、更高效的读取操作。您可以在这篇关于 有限状态 reducer 的全面文章中了解有关该主题的更多信息。

R 树

R 树是一种 树，用于索引多维或空间信息。Meilisearch 利用 R 树来支持其地理搜索功能。

R 树将地理坐标与它所属的文档的标识符相关联。通过以这种方式组织坐标，它使 Meilisearch 能够以卓越的效率执行空间查询。这些查询允许用户查找附近的点、特定区域内的点或与其他空间对象相交的点。

搜索时间：查询处理

现代搜索体验仅需您开始输入即可获得结果。为了实现这种即时搜索体验，Meilisearch 预先计算最常见前缀的列表。

为了容忍错别字，Meilisearch 将有限状态转换器与 Levenshtein 算法结合使用。此算法计算 Levenshtein 距离，该距离可以被认为是将一个字符串转换为另一个字符串的成本。换句话说，它量化了将一个单词转换为另一个单词所需的转换次数。

在 Levenshtein 算法的上下文中，可能的转换是

• 插入，例如 hat -> chat
• 删除，例如 tiger -> tier
• 替换，例如 cat -> hat
• 换位或交换，例如 scared -> sacred

FST 生成指定编辑距离内单词的所有可能变体，使引擎能够计算 Levenshtein 距离，并通过将用户输入与有效单词字典进行比较来准确检测错别字。

显而易见的是，在处理搜索请求时需要考虑许多因素。用户是否已完成输入？查询中是否存在错别字？哪些文档应首先出现在搜索结果中？

让我们讨论 Meilisearch 如何处理搜索查询，以及它如何优化和排序搜索结果。

查询图

每次收到搜索查询时，Meilisearch 都会创建一个查询图，表示查询及其可能的变体。

为了计算这些变体，Meilisearch 将 连接 和 拆分 算法应用于查询词。考虑的变体还包括潜在的错别字和同义词（如果用户设置了它们）。例如，让我们检查查询：the sun flower。Meilisearch 也会搜索以下查询

• the sunflower：连接
• the sun flowe**d**：替换
• the sun flower**s**：添加

现在考虑更复杂的查询：the sun flower is facing the su，查询图应如下所示

使用我们的内部调试工具生成的视觉效果，由 D2 提供支持，展示了搜索请求的执行过程

如上图所示，该图表示搜索查询的不同解释。引擎预先计算每个查询词的单词变体（及其成本）。此外，它还会检测最后一个查询词是否是前缀（后面没有空格），从而发出需要查阅前缀数据库的信号。

那么引擎如何利用查询图呢？

正如我们之前看到的，在索引过程中，Meilisearch 识别所有具有可筛选属性的文档，例如 genre。随后，它生成与每个属性值关联的文档 ID 列表，例如 comedy 或 horror。首先，当应用过滤器时，Meilisearch 将潜在结果缩小到满足过滤器条件的文档 ID。

接下来，它使用查询词和查询图中生成的变体，并在有限状态转换器（即我们的单词字典）中搜索匹配的单词。如果该单词被认为是前缀，它也会在前缀 FST 中查找它。

当在 FST 中遇到单词时，它会在倒排索引（其中包含单词到文档 ID 的映射）中搜索它们，以检索相应的文档 ID。

最后，引擎执行交集以识别包含查询图中单词并满足过滤器条件的文档。

让我们举一个例子来更好地理解查询处理：假设您有一个歌曲数据集。搜索查询是 John Lennon。用户只想检索 1957 年至 1975 年之间发行的歌曲。

首先，Meilisearch 检索该时间范围内歌曲的文档 ID。然后，在 FST 中检查查询图中的单词是否存在后，Meilisearch 检索包含 John、Lennon 或两者的文档的 ID。它还会检索可能的变体，但为了简单起见，我们在此示例中不包括它们。

图表说明了根据用户查询检索文档所涉及的操作。

最后，取两个文档 ID 集的交集（图表中的紫色区域）。这意味着只保留两个集中都出现的文档 ID。换句话说，Meilisearch 保留了 1957 年至 1975 年之间发行的歌曲的文档 ID，这些歌曲包含 John、Lennon 或两者。

当多个文档与搜索查询匹配时会发生什么，引擎如何决定先返回哪个文档？哪个更相关？让我们探讨允许 Meilisearch 确定如何对结果进行排名的规则。

相关性

正如我们之前讨论的那样，查询图包括单词的可能变体。因此，Meilisearch 也会返回搜索结果中包含艺术家（例如 John Lebon）的文档。

幸运的是，查询图不仅考虑了单词变体，还为它们分配了 Levenshtein 成本，除其他因素外，这有助于 Meilisearch 确定搜索结果的相关性。

Meilisearch 使用 桶排序对搜索结果中的文档进行排序。此算法允许根据一组连续规则对文档进行排名。默认情况下，Meilisearch 按以下顺序优先考虑规则

1. 单词：根据匹配的查询词的数量对文档进行排序，包含所有查询词的文档排名第一
2. 错别字：根据错别字的数量对文档进行排序，匹配查询词且错别字较少的文档排名第一
3. 邻近度：根据匹配的查询词之间的距离对文档进行排序。查询词彼此靠近且与查询字符串顺序相同的文档排名第一
4. 属性：根据属性的排名顺序对文档进行排序。在更重要的属性中包含查询词的文档排名第一。属性开头包含查询词的文档被认为比属性末尾包含查询词的文档更相关
5. 排序：如果处于活动状态，则根据在查询时设置的用户定义的参数对文档进行排序
6. 精确度：根据匹配的单词与查询单词的相似性对文档进行排序

Meilisearch 顺序应用这些规则，逐步对结果进行排序。如果两个文档在一个规则后并列，它将使用下一个规则来打破平局。

默认情况下，Meilisearch 每次搜索最多返回 1000 个文档，优先提供最相关的结果，而不是所有匹配的结果。换句话说，Meilisearch 优先考虑效率和相关性，而不是详尽的结果，以确保优化的搜索体验。

结论

搜索引擎是复杂的系统，包含多个相互关联的组件，所有组件协同工作以提供无缝的搜索体验。虽然不同搜索引擎的内部运作可能有所不同，但我们已经探索了为现代搜索引擎提供支持的底层机制。

Meilisearch 目前正在探索广阔的 语义搜索 领域。AI 驱动的搜索正在重塑我们理解查询和文档的方式，开辟了新的可能性和用例。如果您渴望亲身体验，我们邀请您试用我们的 向量搜索原型——您的反馈将非常有价值！

Meilisearch 是一款开源搜索引擎，不仅为最终用户提供最先进的体验，还提供简单直观的开发者体验。您想亲眼看看 Meilisearch 的实际应用吗？试试我们的 演示。您还可以在本地运行它，或在 Meilisearch Cloud 上创建一个帐户。

有关更多 Meilisearch 的信息，您可以加入 Discord 上的社区或订阅 新闻通讯。您可以通过查看 路线图 并参与 产品讨论来了解有关该产品的更多信息。