全文搜索之Tantivy

LLM之后，带火的一个东西就是RAG。在RAG的多路召回里面，其中一个就是BM25全文搜索。

什么是全文搜索

我们先抛开现成的解决方案，从要解决的问题出发：如果有海量的文档，如何查询里面相关的文档呢？我们可以用grep，或者regex去找，但是针对海量的文件这些工具都有点无力。

参考数据库的设计，我们的第一反应就是创建一个索引，然后查索引就好了。于是引出了倒排索引，即针对关键字进行索引。（为什么是关键字？无意义的字就直接忽略，因为找出来也没有意义）。比如，一篇介绍苹果手机的文章，关键字可能有“苹果手机”，在分词之后，就会出现“苹果”、“手机”、“苹果手机”，后面查询的时候，只需要根据关键词就可以找到文章了。

如何排序

通过倒排索引，我们可以快速找到包含关键词的文档。但通常会找到很多篇文档，接下来的问题是：哪些文档应该排在前面？

一个很自然的想法是统计关键词出现的次数。比如搜索“苹果手机”时，一篇文章出现了 10 次“苹果”，另一篇只出现了 1 次，那么前者大概率更加相关。这就是 TF（Term Frequency，词频） 的基本思想。

但是，只看词频还不够。“手机”可能出现在大量文章中，它区分文档的能力较弱；一个只在少数文章中出现的词，往往更有价值。因此还需要 IDF（Inverse Document Frequency，逆文档频率），关键词出现得越普遍，IDF 越小；关键词越稀有，IDF 越大。将 TF 和 IDF 相乘，就得到了经典的 TF-IDF：

如果查询中有多个关键词，就分别计算每个词的得分，再将它们相加。简单来说，TF-IDF 认为：一个词在当前文档中出现得多，同时在其他文档中出现得少，那么它对当前文档就越重要。

BM25

TF-IDF 有两个比较明显的问题。

第一，词频并不是越高越好。关键词从出现 1 次增加到 2 次，通常能明显提高相关性；但从 100 次增加到 101 次，意义就没有那么大了。第二，长文档天然包含更多词，如果只统计词频，长文档更容易得到高分。

可以把 BM25 的排序逻辑概括为：

查询词越稀有，得分越高；
查询词在文档中出现得越多，得分越高，但增长会逐渐变慢；
在词频相近时，较短且内容更集中的文档通常得分更高。

因此，BM25 不理解词语的语义，但非常擅长寻找“字面上匹配，并且关键词分布合理”的文档。它计算速度快、结果容易解释，所以至今仍是全文搜索和 RAG 关键词召回中非常常用的算法。Tantivy 默认使用的相关性评分算法就是 BM25。

PostgreSQL 使用 TF-IDF 还是 BM25？

PostgreSQL 原生全文检索使用的既不是标准 TF-IDF，也不是 BM25。它提供了两个主要的排序函数：

ts_rank：根据查询词在文档中的出现频率和词语权重计算得分；
ts_rank_cd：使用 Cover Density Ranking，在词频之外还考虑查询词之间的距离。多个查询词在文档中靠得越近，通常得分越高。

PostgreSQL 可以通过 setweight 给标题、摘要和正文设置不同权重，也可以通过 normalization 参数降低长文档的得分。例如：

SELECT
  title,
  ts_rank_cd(search_vector, query, 2) AS rank
FROM articles,
     websearch_to_tsquery('english', 'full text search') AS query
WHERE search_vector @@ query
ORDER BY rank DESC;

这里的 normalization = 2 表示用文档长度对得分进行归一化。

它与 TF-IDF、BM25 最关键的区别是：PostgreSQL 的内置排序函数不使用整个文档集合的全局统计信息。也就是说，它不知道一个词出现在多少篇文档中，因此没有 IDF，不能认为它实现了 TF-IDF 或 BM25。

简单对比如下：

算法	词频	IDF	长度归一化	词语邻近度
TF-IDF	是	是	视实现而定	否
BM25	是，带饱和	是	是	通常不考虑
PostgreSQL `ts_rank`	是	否	可选	否
PostgreSQL `ts_rank_cd`	是	否	可选	是

所以，如果数据已经存储在 PostgreSQL 中，并且搜索需求不复杂，ts_rank 或 ts_rank_cd 往往已经够用；如果更看重专业的相关性排序，尤其需要 BM25，则可以使用 Tantivy、Elasticsearch 等搜索引擎，或者为 PostgreSQL 安装提供 BM25 的扩展。

语义搜索

谈到RAG，就需要谈论另外一个分支，语义搜索。由于BM25是精确搜索，如果是语义搜索，可能效果就没有那么好了。所以就需要先embedding，然后根据向量进行搜索，这里就不展开了。

Page Rank

全文搜索主要根据页面内容判断它与查询词的相关性，但仅靠内容容易遇到一个问题：很多页面都包含相同的关键词，应该把哪一个排在前面？

PageRank 从页面之间的链接关系来衡量页面的重要性。可以简单理解为：一个页面被越多重要页面引用，它自身通常也越重要。普通页面的一次引用和权威页面的一次引用，所贡献的权重并不相同。

搜索引擎通常先通过倒排索引找出与查询匹配的候选页面，再综合多个信号进行排序：

BM25 等全文搜索算法判断页面与当前查询的相关性；
PageRank 判断页面在整个链接网络中的重要性或权威性；
最终排序将相关性、重要性以及时效性等信号组合起来。

需要注意，PageRank 本身通常不判断页面与查询是否相关，因为同一个页面的 PageRank 不会随着查询词变化。一个页面即使非常权威，如果内容与查询无关，也不应该出现在搜索结果前面。

例如，搜索“PostgreSQL 全文搜索”时，两篇文章的 BM25 得分可能接近；如果其中一篇被 PostgreSQL 官方文档以及大量技术文章引用，那么它可以借助 PageRank 得到更高的综合排名。

Tantivy

Tantivy是针对BM25的全文搜索，我搭了一个 https://github.com/zhongxiao37/tantivy-101，然后把阮一峰的周刊放进去，实现了毫秒级的查询效果。

Zhongxiao37