信息检索(1): Sonic 中的技术

Sonic 是一个基于 rust 的语言的轻量极全文检索系统，类似项目还有 tantivy、MelliSearch 。因为学习需要，读了项目作者 Valerian Saliou （法）发布 Sonic 时的文章《Announcing Sonic: A Super-Light Alternative to Elasticsearch》，其中提到了这套系统实现的若干技术，于是结合自己看《信息检索导论》所学知识，在此记录一下。

什么是 Sonic？

用作者的话来说就是：

Sonic 是一个快速、轻量和无模式的搜索后端。它摄取搜索文本和标识符元组，然后可以针对微秒时间查询。

Sonic 可以用作重量级和全功能搜索后端的简单替代方案，如在某些用途中替代 Elasticsearch。

Sonic 使用标识符索引而不是文档索引。当需要查询时，它返回外部数据库中的、用于指向匹配的文档的 ID （而非文档本身）。

Sonic 使用 rust 语言编写，以确保性能和稳定性。您可以在您的服务器上托管它，并通过特定的协议 Sonic Channel 将应用程序通过网络相连。然后，您将能够发出搜索查询并用您的应用添加新的索引数据 - 无论您使用哪种编程语言。

Sonic 设计用于快速轻便地使用资源，期待它在没有毛刺的情况下在非常低的资源上运行。在 Crisp 项目中，我们将 Sonic 部署在每月 5 美元的 DigitalOcean SSD VPS 上，仅 300MB 内存和 15GB 磁盘空间就索引了五千万个对象。

实现技术

一个简单的、典型的搜索引擎中的技术并不复杂。Sonic 中包含了一部分这样的常见的技术。

词条化

一般的搜索引擎不会存储任何完整的句子，相反，它们只会存储单词。在新增文档时，我们为文档指定一个 ID，搜索引擎会对句子进行处理，分为若干单词，并将其词条化（tokenize），即，operating，operation 等单词均转换成 operate。这一做法还能减少单词量，且提升用户体验。

一些单词在检索中没有实际意义，应予去除，称为停用词（stopwords），如英文中的 the, he, like。Sonic 内置了一些常见的自然语言的停用词。

在分词中也存在分词粒度和歧义问题，如 “北京大学” 与 “北京”、“大学”，“南京市长江大桥”与 “南京市长”、“江大桥”。Sonic 使用 n元语法（ngram）来解决这个问题（参考资料5）。

倒排索引

分词结束后，可以建立“词项（term）” -> “文档（document）ID”的倒排索引。在 Sonic 中，这些关系使用 key-value 数据库存储，每一个 value 都是 key 所对应文档 ID 的集合。

在检索时，查询也会分成词语，每个词语单独在数据库中查询，对得到的若干文档ID的集合求交集，便是最终的搜索结果。

纠错

纠错算法使用莱文斯坦距离（Levenshtein distance）评估两个单词之间的差异，取距离最小的单词作为可能的单词。评估函数定义如下：

\qquad\operatorname{lev}_{a,b}(i,j) = \begin{cases} \max(i,j) & \text{ if } \min(i,j)=0, \\ \min \begin{cases} \operatorname{lev}_{a,b}(i-1,j) + 1 \\ \operatorname{lev}_{a,b}(i,j-1) + 1 \\ \operatorname{lev}_{a,b}(i-1,j-1) + 1_{(a_i \neq b_j)} \end{cases} & \text{ otherwise.} \end{cases}

$1_{(a_i \neq b_j)}$ 是一个指示函数，当 $a_i = b_j$ 时，其值为 0,其他时候它等于 1. $lev_{a,b}(i, j)$ 表示 $a$ 的前 $i$ 个字符与 $b$ 的前 $j$ 个字符之间的列文斯坦距离（ $i$ , $j$ 下标均从 1 开始）。

补全

如果遇到用户输入错误，搜索引擎程序需要进行纠正；当用户未输入完全时，搜索引擎也需要提供搜索建议（suggestion）。这两者往往结合起来使用。Sonic 中使用有限状态变换器（Finite-state transducer, FST）处理。

FST 也是一个有限状态机（FSM），具有这样的特性：

确定：意味着指定任何一个状态，只可能最多有一个转移可以遍历到。

无环：不可能重复遍历同一个状态

transducer：接收特定的序列，终止于 final 状态，同时会输出一个值。

FST 和 FSA 很像，给定一个 key 除了能回答匹配项是否存在，还能输出一个关联的值。

GPDR

原文中，作者是这样解释的：

A GDPR-ready search system: when text is pushed to the index, Sonic splits sentences in words and then hashes each word, before they get stored and linked to a result object. Hashes cannot be traced back to their source word, you can only know which hash form a sentence together, but you cannot re-constitute the sentence with readable words. Sonic still stores non-hashed legible words in a graph for result suggestions and typo corrections, but those words are not linked together to form sentences. It means that the original text that was pushed cannot be guessed by someone hacking into your server and dumping Sonic’s database. Sonic helps in designing “privacy first” apps.

实现了 GDPR 的搜索系统：当文本被推到索引时，Sonic 以单词拆分句子，然后在它们存储并链接到结果对象之前哈希划分。哈希值无法倒推来源单词，你只能知道哪个哈希组成了一个句子，但你不能用可读的单词重新构成句子。Sonic 仍然在图表中存储非哈希清晰的单词，以获得结果建议和拼写校正，但这些词并不连接在一起以形成句子。这意味着推动的原始文本不能被攻击到您的服务器并转储Sonic的数据库的人猜到。Sonic 帮助设计“隐私第一”应用程序。

后记

文中作者说：

A search engine is nothing more than a huge index of words.

不能更赞同！然而，正是这样一个小小的搜索引擎，要使用户体验良好，也要下很大的工夫呢。Sonic 是 Rust 中实现全文检索的、简单的一个搜索引擎，基于自己实现的 key-value 数据库，是一个不可多得的学习项目。