写在前面的话
本文是《信息检索导论》第二部分的内容，本文主要讨论了如下内容
文档的处理
- 如何将文档变为可识别的字符序列
- 如何对文档的粒度进行划分
词条处理
- 基于跳表的合并优化
- 短语查询
- 二元词索引
- 位置信息索引
词项词典及倒排记录表
文档分析及编码转换
字符序列的生成
字节序列转化成为线性的字符序列
- 机器学习分类问题确定编码
- 手工确定编码
二进制文档中得到字符序列
- 确定文档格式，再确定编码
这里假设文档只由一系列文本字符构成
文档单位的选择
并非每篇文档就是固定的索引单位，可能存在合并或者文件划分
信息检索需要对文档集，用户及其可能的需求和使用模式都有一个深入的理解，才能确定好索引粒度。
- 索引粒度大：找到不相关的结果，正确率低而召回率高。
- 索引粒度小：错过重要片段，正确率高而召回率低
词项集合的确定
词条化
将给定的字符序列拆分成一系列子序列的过程，其中每一个子序列被称为词条
词条
文档中出现的字符序列的一个实例
词条类
相同词条构成的集合
词项
信息检索词典中包含的某个可能经过归一化处理的词条类
词条化的主要任务是确定哪些才是真正的词条
词条化的处理往往和语言相关，不同语言下的词条化处理并不相同。
去除停用词
停用词
一些常见词在文档和用户需求匹配时价值不大，需要彻底从词汇表中去除
然而对于短语查询来说，停用词影响会更大
1 | To be or not to be. |
现代IR系统中通常不用停用词表
词项归一化
将看起来不完全一致的多个词条归纳为一个等价类，以便他们之间进行匹配的过程
做法一：
隐式的建立等价类，例如将anti-discriminatory和antidiscriminatory映射为词项antidiscriminatory
做法二：
维护非归一化词条的关联关系，可以扩充为同义词的手工扩建，例如car和automobile为同义词。
词项关系的实现方式:
- 采用非归一化的词条进行索引，并未某个查询项维护一张由多个词组成的查询扩展词表。查询时用扩展词表扩展后的结果合并在一起。
- 在索引构建时为词进行扩展，例如包含car的文档，同时用automobile来索引。
不同语言会有不同的归一化方法。
词干还原和词形归并
词干还原
一个粗略的去除单词两端词缀的启发式过程
词形归并
利用词汇表和词形分析来去除屈折词缀，从而返回词的原形或词典中词的过程，返回的结果称为词元
英文处理中最常见的词干还原算法是Porter算法
基于跳表的倒排记录表快速合并算法
构建跳表的问题：
- 在什么位置设置跳表指针
- 如何利用跳表指针进行倒排记录表的合并
快速合并
算法如下：
- 首先找到p1 == p2的位置，并且p1++, p2++
- 如果p1 < p2，那么就判断skip(p1)与p2的大小，如果仍然小于，则p1 = skip(p1)
- 反之亦然
设置跳表指针
- 更多的指针：更短的步长，更多的存储空间，更多的跳转机会
- 更少的指针：更多的步长，更少的存储空间，更少的跳转机会
启发式的策略：每个sqrt(p)处均匀放置跳表指针，p是倒排记录表的长度
含位置信息的倒排记录表及短语查询
要支持短语查询，只列出词项所在文档的倒排索引记录是不够的
二元词索引
一个简单办法，将文档中每个续接词看做一个索引，例如
文本friend Romans countryment会产生如下的二元词对
- friend Romans
- Romans countryment
在实际处理中，可能有大量的虚词来分开名词，因此可以用如下的方式
NX*N
- N为名词
- X为虚词
例如 renegotiation of the constitution，既是NXXN
然而，穷尽所有二元词会大大增加词汇表的大小，需要有一种方法来处理。
位置信息索引
位置索引，按照如下方式存储倒排记录
1 | 文档ID：(位置1，位置2，...) |
在这种方式下，查询时需要注意：
- 判断两个词项出现在同一文档中
- 检查它们出现的位置关系和查询短语的一致性
一个k词近邻搜索算法
整体算法就是在之前的文档匹配算法中增加了临近位置的判断，整体思路为一个指针放在p1位置上，一个放在p2位置上，如果两个位置之差的绝对值小于k，那么放入集中，再移动p2，p1。
位置索引大概是非位置索引的2~4倍
混合索引机制
将某些高频词查询放入二元词索引中，可以大大提高查询效率