倒排索引(Inverted Index),主要是用于存储某个词在文档中位置的映射,是文档检索中很常见的一种结构。
举个例子
使用乱数假文举个例子,我们有几个文档
0 - lorem ipsum dolor sit amet, consectetur adipiscing elit.
1 - Nulla sit amet est consequat, pretium risus ut, consectetur mi.
2 - Curabitur dui enim, mattis non blandit at, consectetur in turpis.
3 - Praesent sit amet metus nibh amet.
我们要寻找同时包含 amet 和 consectetur 这两词的文档,朴素的做法是根据关键词依次遍历所有文档来取得结果。
在句子的数量成指数级增长后,遍历的做法就不太可行了,复杂度太高。这个时候就需要找到一个可以提升检索速度的方法,那么就有一种看起来很暴力的做法了——打表。
打表也是有讲究的,如果以文档ID为键,文档里包含的字词列表为值,实际上就是朴素做法,因为实际上我们要检索的词的数目通常远小于文档数目,那么反过来对检索词建表,存储的是包含这个词的文档ID,这个做法就叫做倒排索引。
对于第一句假文,可以生成的索引部分如下
'Lorem': [0]
'ipsum': [0]
'sit': [0, 1, 3]
'amet': [1, 3]
'consectetur': [0, 1, 2]
...
假设检索条件同上,那么得出的结果就是 [0, 1, 2] and [1, 3] => [1],可以很方便的通过倒排索引去取出包含这个搜索结果的文档。当然,在搜索系统里,仅检索到文档的ID是远远不够的,我们往往要在结果里插入额外信息辅助相关性排序。
辅助信息
如果我们使用常规的 TF-IDF + 权重的方式对结果进行排序,那么我们可以在倒排索引里存储的格式如下
Term: [[文档编号,出现次数(&Term Frequency), 文档长度, [起始位置, ...]], ...]
term 是一个搜索(信息检索)领域的概念,是分词后的基本表述单位,不一定是文档中出现的词语,但可以用于描述文档。上面这种格式的数据经过在线处理我们可以得到一些 TF-IDF 和计算辅助权重需要的参数
- TF(Term Frequency),词频
- DF(Document Frequency) & IDF(Inverse Document Frequency),文档频率和逆文档频率
- 词距
不过这些都属于相关性的部分,此处就按下不表,以后再谈。
所以在中文搜索引擎里构建倒排索引的 term,主要有如下几部分
分词
回到最开始的例子,举的例子是英文文档,而中英文NLP最大的差异之一就在于分词。英文拥有天然的空格作为分隔符,可以很方便的切分出单词,中文则不然,虽说有的中文文档存在可以作为参考的标点(像是逗号书名号等),但是子句往往是由一串连续的汉字构成且不存在分隔符,所以切分出符合需要的 term 也是要花费一番功夫,往往会通过新词发现、维护自定义词典和领域词典等方式来优化分词结果。此外,为了提高召回率,有时候也会结合多粒度分词(比如 IKAnalyzer)等方法进行优化。
停用词过滤
停用词(Stop Words),即在处理文档的时候所不需要的字词,它们不能很好地用来区分文档。在中文语境下常见的助词(的/地/得/着/啊/吗…)、副词(很/十分/居然…)、介词(在/随/以…)和连词(那么/所以/但是…)等词性很多都属于停用词。
归一化
理想情况下用户输入的 query 经过分词后正好与文档的 term 能完全匹配上,但实际上用户的输入时很难预测的。归一化的目的就是将同义近义/拼写错误/拼音转写等表面不一致的多个 term 归一成一个等价的 term。
之后的步骤就是构建倒排记录表,这个和业务场景关系比较密切,本文也就不展开了。
本文属于历史文章,整理自笔者19年的私有云笔记。