文档分析及编码转换

1、判断文档的编码方式(ASCII,UTF-8等)，将字节序列转换成线性的字符序列
2、确定文档的索引单位(索引粒度问题indexing granularity)
*注：索引粒度太小，词项散布在多个细粒度文档中，错过重要段落，正确率高而召回率低。
索引粒度太大，不相关的匹配结果太多，导致正确率低召回率高。

词项集合的确定

1、词条化(tokenization)

词条化：将给定字符序列拆分成一系列子序列的过程，其中每个子序列称为一个词条。

词义辨析：
词条(token)：文档中出现的字符序列的一个实例
词条类(type)：相同词条构成的集合
词项(term)：词典中所包含的经过归一化处理的词条类

2、去除停用词

常用方法：将词项按照文档集频率从高到低排列，然后手工选择那些语义内容与文档主题关系不大的高频词作为停用词。
目的：减小系统所需要存储的倒排记录表的数目。

3、词项归一化

隐式地建立等价类：不需要事先计算出等价类的全部元素，如使用去掉连字符的映射规则

显示的建立等价(维持多个非归一化词条间的关联关系-可扩展成手工建立同义词词表)：

• 查询时扩展
  为某个查询项维护一张包含多个词的查询扩展词表，输入一个查询项时，根据扩展词表进行扩展并将扩展后得到的多个词所对应的倒排记录表合在一起。

• 构建索引时扩展
  如，对于包含automobile的文档，同时也用car来索引(同样，包含car的文档也用automobile来索引)

4、词干还原和词形归并

词干还原：粗略的去除单词两端词缀(如复数词缀等)的启发式过程

词形归并：利用词汇表和词形分析来去除曲折词缀，返回词的原形的过程，返回的结果称为词元。

基于跳表的倒排记录表快速合并算法

跳表(skip list):在构建索引的同时在倒排记录表上建立跳表，跳表指针能够提供捷径来跳过那些不可能出现在检索结果中的

• List item

记录项。

当跳表指针目标项仍然小 于另一个表的当前比较项时可以采用跳表指针直接跳转。

• 跳表指针的设置：在每个根号P处均匀放置跳表指针，P是倒排记录表长度

含位置信息的倒排记录表及短语查询

对于一些复杂的或技术性概念、机构名和产品名等多个词语的复合词或短语，希望在查询中将这类词语看成一个整体。以下将考虑两种支持短语查询的方式及它们的混合使用。

二元词索引

对文档中每个接续词(biword)对看成词项，这样就可以处理两个词构成的短语查询，更长的查询可分成多个短查询来处理。
例如，查询stanford university palo alto分成如下的布尔查询:

• 词性模式的扩展二元词索引
  对于名词短语，相关的名词被虚词分开，可采用如下方式：
  1、将文本进行词条化然后进行词性标注
  2、将每个词项归成名词(N),虚词(X)和其他词
  3、将形式为NX*N非词项序列看成一个扩展二元词。

位置信息索引

在位置信息索引(positional index)中，对于每个词项，以如下方式存储倒排记录：

根据这种方式，可构建如下的位置索引：

上图中，单词 to 的文档频率是 993427， 在文档 1 中出现 6 次，位置分别是 7、18、33等。

混合索引机制

混合策略：对某些高频常见的查询使用短语索引或二元词索引(基于位置索引的倒排记录表合并方式效率很低)，对于其他短语查询则采用位置索引。

后续词索引， 一种更复杂的混合索引机制：即对每个词项，有个后续词索引记录它在文档中的下一个词项。