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

搜索栏是浏览网页不可或缺的一部分。无论是购买衣服、欣赏音乐还是计划度假，总有一个专门的搜索引擎在工作以简化我们的生活。您是否曾经想过这些搜索引擎实际上是如何工作的？在本文中，我们将深入研究其中一个搜索引擎的内部运作：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：一个用于存储数据集的所有单词，另一个用于存储最常见的前缀。

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

FST（有限状态转换器）以其紧凑的设计，相比倒排索引，具有数据结构更小的优点。正如我们稍后将看到的，这有助于更快、更高效的读取操作。您可以在这篇关于有限状态转换器的综合文章中了解更多相关信息。

R树

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

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

搜索时间：查询处理

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

为了容忍拼写错误，Meilisearch 将有限状态转换器与 莱文斯坦算法 结合使用。此算法计算莱文斯坦距离，可以将其视为将一个字符串转换为另一个字符串的成本。换句话说，它量化了一个单词转换为另一个单词所需的转换次数。

在莱文斯坦算法的上下文中，可能的转换是

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

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

很明显，在处理搜索请求时需要考虑很多因素。用户是否已完成输入？查询中是否存在拼写错误？哪些文档应该在搜索结果中首先出现？

让我们讨论一下 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。随后，它会生成与每个属性值（如 comedy 或 horror）关联的文档 ID 列表。首先，当应用过滤器时，Meilisearch 会将潜在结果缩小到满足过滤器条件的文档 ID。

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

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

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

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

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

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

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

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

相关性

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

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

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

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

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

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

结论

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

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

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

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