Text Retrieval and Search Engines学习笔记(四)
这篇文章是接着上一篇Text Retrieval and Search Engines学习笔记(三) ，这一篇我们介如何绍下实现Vector Space Model所需要的一些步骤和流程。
System Implementation
前面我们介绍了Vector Space Model的一种实现-> BM25,虽然我们从数学上已经定义好了rank的函数，但是我们还得想办法进行高效的计算rank函数，因为有的时候我们会在我们的搜索引擎中存放千万甚至几十亿的数据,为了让用户在几百毫秒的时间内完成一次检索，我们必须非常高效的计算rank函数。
一个典型的信息检索系统的架构
当然刚开始的信息检索系统并不是这个样子，很久以前，信息检索系统并没有这么复杂，因为网上的数据还没有今天这么庞大，在那个软盘只有几十kb的年代，所谓的搜索引擎真的就是使用用户的关键字一篇一篇的找，可以是正则表达式也可以是普通的字符串查找，但是随着网页上的数据越来越多，这种一篇一篇查找的方式已经不能满足用户对检索的实时响应性，所以google的创始人搞出了Invert Index,为啥叫Invert Index,因为以前是以文档为主键，遍历文档进行关键字查找，而Invert Index是以关键词为主键，通过关键词找到对应的文档，其实这也是正常的用户场景，我们在google检索的时候，大部分情况下输入都是很短的。既然是对关键词，所以才会有Tokenization的概念.
分词
- 同义词处理，相同意思的词应该映射到同一个词上
- 词干提取(stemming)和词形还原(lemmatization)
- 关键字提取，英文可能比较简单，直接按照空格切分就行了，但是类似于中午我们需要对关键词进行一次切分
- …
索引
- 索引就是将原始的文档转换成可以支持快速检索的数据结构，说白了就是预计算
- 倒排索引就是为了支持计算算法所设计的一种索引方式
- 。。。
倒排索引
下面我们重点介绍下倒排索引，倒排索引是一种数据结构，通过这种数据结构我们可以快速进行排序算法的计算,下面是倒排索引的一个例子:
这里我们可以通过这个例子清楚的理解正排索引和倒排索引的区别
| -/- | 倒排索引 | 正排索引 |
|---|---|---|
| 特点 | 记录某个关键字在哪些文档中出现和出现的次数 | 记录某个文档中出现哪些关键词 |
| 使用方式 | 构建一次，多次使用 | 不需要构建，每次scan 就行了 |
并且倒排索引在搜索引擎中常见的term检索，bool检索的效率都远远高于正排索引，这是因为倒排索引采用了预计算的方式，对每个关键词出现的文档编号都做了记录，用的时候取出来就行了，即使对于稍微复杂的bool检索，也只需要对文档集合做对应的交、并、补等集合操作即可。那么倒排索引中到底有哪一些数据结构来保证我们能够快速获得计算rank函数的参数呢？
- 字典:正常来说字典的大小不会特别大，虽然中国汉字有非常多，常用的也就3500个，也就是说字典的大小由于人类使用自然语言的方式会是一可控的大小
- 我们需要对字典进行随机读取
- 一般来说为了高效率，字典我们都选择放在内存中
- 可以使用hash表 ，B-树,前缀树等方式实现
- Postings(倒排表): 一般来说这个很大，因为文章的关键词数量比较多，由于有位置信息，所以即使相同的关键词由于出现的位置不一样，在存储上这些空间是没法像字典一样节约下来的。
- 期望是通过顺序读写（太大了不能放到内存中）
- 可以放在磁盘上
- 一般会包含文档编号，词频，词的位置等信息
- 由于会很大所以需要进行数据的压缩
那么到底倒排索引是怎么生成的呢?
如何生成倒排索引
- 第一步: 针对每个文档生成三元组 (termID,docID,freq)
- 第二步: 按照termID 对三元组进行排序
- 第三步: 根据termID 进行docID,freq 合并
- 第四步: 输出倒排文件
如下图所示:
实际上生成倒排文件并不是那么困难，最难的是如何使用有限的内存生成倒排文件，因为往往我们真实场景中文档可能很多很大，就算是TB内存级别的机器可能也无法在内存中一次性生成倒排文件，但是我们可以生成很多倒排文件，然后对这些文件在内存中合并(因为文件的内容都是排好顺序的，所以我们不必将倒排文件全部读入到内存中进行合并))，这也是lucene生成索引的步骤，在lucene中可以生成很多很多的段(segment), lucene在后台使用单独的线程对这些段进行合并来避免段太多导致的查询性能低下的问题。
索引压缩
为了节约硬件成本,我们需要对索引进行压缩，这里举个例子来说明为什么我们需要对索引进行压缩，假设我们有1亿条文档需要进行压缩，这里文档编号我们使用int类型存储(占用4个字节),那么为了存储这一亿个文档编号我们需要1000000004/1024/1024=381.4MB的内存，但是如果我对这1亿个文档编号使用bitset来存储的话大约需要1000000004/32/1024/1024=11.9MB就够了，可以对文档编号压缩可以大大降低存储所消耗的资源。这里我们介绍几种常见的整型压缩算法。
- biset: bitset可以简单的理解为使用位信息来存储integer，例如正常情况下一个整型就占用了4个字节(32位),如果我们只是为了表示一个整型的集合(不管顺序),那么其实我们可以使用位信息来存储，每个位表示一个数，32位表示0～31这32个数字。同理表示0～63需要2个整型(整型数组)就行了
- 差值压缩: 想象下我们需要存储每个term的位置信息(起始和结束的位置)，那么当文档很长的时候表示位置的数字可能比较大，例如这篇文档有1万个字符，那么位置信息就可能是9000,但是因为位置信息都是连续的，所以前后位置信息的差值会很小，以中文为例子，前一个汉字和后一个汉字的差距永远都是1(即使文档的长度很长很长)，存储9000至少需要10个bit,但是存储1只需要1个bit就行了，当文档很长而且文档非常多的时候这样的压缩算法将会节约大量的存储空间。
倒排索引如何加速打分公式
我们在之前的文章中描述过BM25的打分公式:
f(q,d) = $\sum_{w \in q \cap d}$ [C(w,q) $\frac{(k+1)C(w,d)}{C(w,d)+k(1-b+b \frac {d}{avdl})}$log$\frac{M+1}{df(w)}$)]
- C(w,d) 表示w在文档d中出现的次数，从上面的倒排索引生成的过程中，我们知道词频信息已经在生成索引的时候被我们写入到倒排表中
- avdl 平均文档长度，我们在生成倒排表的时候会遍历所有的文档，我们可以存储每个文档的长度，在进行打分的时候通过每个文档的长度计算出平均文档长度
- df(w) 文档频率,表示有多少文档出现w，虽然我们但在生成倒排表的时候没有直接将这个数字写入到倒排文件中，但是我们记录了每个w出现的文档编号，统计文档编号的个数，我们可以直接得到df(w)
到这里也就说: 基本上BM25打分公式中用于计算最终文档的分数的算子，我们基本上已经在倒排索引中进行的直接或者间接的存储，那么当我们查询的结果有几十万或者几百万的文档时，我们依然可以在几百或者几十毫秒对命中到的文档进行排序输出。