全文搜索算法杂谈

奇葩的灵梦2022/2/9大约 5 分钟

最近更新： 2025/5/13

全文搜索指的是像搜索引擎一样，在大量文档中，找出和查询语句相关联的文档。

我们先讨论搜索一个字符串的情况，为什么顺序扫描检索的速度非常慢？

对于一个无固定格式的数据（例如一个文件），我们所知道的是文件里包含了哪些字符串，换句话说就是文件→字符串的映射。而我们搜索的时候，是已知字符串，欲求哪些文件包含了这个字符串，换句话说这是字符串→文件的映射。可以看出，这两者是恰恰相反的。

也就是说，如果我们能提前建立字符串→文件的映射，就可以大大加快检索速度。

创建索引

创建索引的方法很简单，遍历所有文件，按照每个词进行划分，建立一个反向映射表即可。下面用简单的代码来说明一下：

// 假设我们已读取了多个文件，并将文件名和文件内容组成了一个映射：
// Map<String, String> files;
var wordsToFiles = new HashMap<String, List<String>>();
for (var entry : files.entrySet()) {
    String fileName = entry.getKey();
    String content = entry.getValue();
    for (String word : content.split("[ .,!]")) { // 按照空格和标点符号分割，如果是中文，可能需要一些特殊的分词算法
        if (!wordsToFiles.containsKey(word)) {
            wordsToFiles.put(word, new LinkedList<>());
        }
        wordsToFiles.get[word].add(fileName);
    }
}

其中词汇是key，包含指定词汇的文件名组成一个链表，作为这个词汇对应的value。

除此之外，我们还需要对文件进行进一步的一些操作。例如，对于英语，我们应该把单词统一变成小写，把复数形式、过去式等统一变成原词的词根形式。例如在中文中，我们也需要去掉一些例如“了”“呢”等无意义的词汇。

分词

英文是以单词为单位的，单词与单词之间以空格或者逗号句号隔开，所以将一篇文档分成一个一个单词是非常容易的。而中文的语义比较特殊，很难像英文那样，一个汉字一个汉字来划分。

好在现在有非常多很成熟的开源中文分词算法库，我们可以直接使用。

搜索和排序

经过以上的这些步骤，我们便可以建立起一个key是单词、value是文件名链表的映射关系，也就是我们说的倒排索引。这个索引我们在后续查找的过程中就可以重复利用了。

到了这一步，似乎我们已经可以根据单词找到我们想要的文档了。然而事情并没有结束，“找到文档”仅仅是全文检索的一个方面。如果仅仅只有一个或十个文档包含我们查询的字符串，我们的确找到了。但如果结果有成千上万个文档，哪个才是我们最希望找到的呢？

例如，我们打开一个搜索引擎，想要查找某个内容，结果会发现总共查找到几百万甚至几千万个结果。在如此多的结果中，如何将最关键的放在最前面呢？

这就引入了“打分”的机制。我们知道，一个文档由很多词（Term）组成，但是，不同的词的重要性不同。就比方说，例如两篇文档都包含search、fulltext，说明这两篇文档的相关性高。而如果两篇文档都包含this、is、a，这些词并不能影响两篇文档的相关性。

换句话说，不同的词应该有不同的权重（Weight）。那么我们应该怎么计算不同的词的权重呢？下面就来介绍具体方法：

影响一个词(Term)在一篇文档中的重要性主要有两个因素：

词频率（Term Frequency，简称tf）：即此Term在此文档中出现了多少次，越大说明越重要。
文档频率(Document Frequency，简称df)：即有多少文档包含此Term，越大说明越不重要。

那么公式就是： $W = tf \times log(n/df)$

当然了，这仅仅是一种最简单最经典的公式，实现全文检索系统的算法一般都会有自己的实现。

通过上述方法，我们就能知道一个词对于一个文档的重要性。接下来，我们把查询语句看作一片短小的文档，我们的问题就转化为如何比较查询语句和需要搜索的文档之间的相关性了，即两篇文档的相关性。

首先，一个文档中有多个单词，我们把每个单词的权重排列在一起，可以得到一个向量。

\vec{V_1} = (W_{11}, W_{12}, W_{13}, \cdots, W_{1n})

然后，我们把查询语句也看作一个向量，就可以类似地得到：

\vec{V_2} = (W_{21}, W_{22}, W_{23}, \cdots, W_{2n})

注意，这里一定要每个单词的位置要一致。也就是说， $W_{11}$ 和 $W_{21}$ 是同一个单词的权重， $W_{12}$ 和 $W_{22}$ 是同一个单词的权重。如果缺少这个单词，就把位置空出来，这个位置填上0。这样，这两个向量就会有相同的维度。

那么如何判断两个向量之间的相似度呢？我们可以用他们的夹角 $\theta$ 来表示。夹角越小，说明两个向量越相似。

我们又知道，夹角 $\theta$ 越小，余弦值 $\cos{\theta}$ 越大。而根据向量的点积公式，我们可以得到：

\begin{aligned} \cos{\theta} & = \frac{\vec{V_1} \cdot \vec{V_2}}{|\vec{V_1}| \cdot |\vec{V_2}|}\\ & = \frac{W_{11}W_{21} + W_{12}W_{22} + \cdots + W_{1n}W_{2n}}{\sqrt{W_{11}^2+W_{12}^2+\cdots+W_{1n}^2} \times \sqrt{W_{21}^2+W_{22}^2+\cdots+W_{2n}^2}} \end{aligned}

这样一来，这个 $\cos{\theta}$ 的值越大，就说明夹角 $\theta$ 越小，两个向量越相似，即查询语句和文档的相关性越大。