信息检索札记-词项及倒排记录表
建立倒排表的几个主要步骤：搜集文档；对文档中的文本进行词条化；对词条进行语言学处理，得到词项；根据词项建立倒排索引。
通过词条化和语言学处理我们才能确定系统的所用词项词典。词条化将原始的字符流转换成一个个词条的过程，而语言学处理主要是建立词条的等价类。
文档分析及编码生成
文档一般由文件或者web中的网页组成，那么第一步我们要确定其编码方式，有时我们需要确定文档的格式（比如XML），然后采用合适的编码方式还原出字符序列。
第二步，确定索引粒度。简单的说就是我们将整本书看成是一个文档，还是书中的一篇文章看成一篇文档，或者每篇文章的每一段看成一篇文档。这里面有个trade-off，索引粒度太小，我们很可能错过重要的段落，即召回率低。索引粒度大，我们很可能将整本书作为返回结果，召回率是高了，但是准确率低了。
词项集合的确定
编码方式和索引粒度都确定之后，接下来就是词条化：
my,name,is,lsj==>my name is lsj
将上面的标点符号去掉（当然还有其他处理）变成一个个词条，词条的重要任务是确定哪些才是正确的词条。在文章中可能出现类似email地址、IP地址特殊语句，我们都要考虑到。词条化处理往往与语言本身有关，不同语言下的词条化处理并不相同。例如：
对于一些短语的词条分词：基于机器学习；k-gram方法。
去掉停用词：将一些介词或者助词去掉。这种办法容易将一些短语或者专有名词拆错，现代web搜索不用，而是更关注如何利用语言的统计特性来更好解决这个问题。
词条归一化：（1）看起来不完全一致的多个词条归成一个等价类，最常规的方法就是建立等价类。例如，anti-discrimination和antidiscrimination都转化为antidiscrimination去查询。（2）同时还有一些意思相等的词也可以将其转化为等价类。例如，car和automobile转化car去查询。（3）大小写转化，Car和car都转化为car。（4）词干还原（porter算法）。
非严格的情况下，词条往往和词项或词通用。词项指的是在信息检索系统词典中所包含的某个可能经过归一化处理的词条（可能将词条经过等价处理）。
基于跳表快速合并算法
对两个排序的倒排表求公共的节点需要o(m+n)的时间复杂度，为了加快合并的时间，可以建立跳表。关于跳表请看：http://blog.csdn.net/lsjseu/article/details/12185753。这样我们在合并的时候，可以先比较跳表指针，再比较一般的指针。
跳表只能加速and操作，对or操作没力。
含位置信息的倒排记录表及短语查询
（1） 短语索引
要处理这种查询，需要将每个接续词看出词项，这样就能处理短语查询。
standford university palo alto==》 ” standford university“ and “university palo” and “palo alto”（这个不错）
the abolition of salvery===》 ”the abolition“ and “abolition of" and "of salvery" （短语被介词搞乱了，完全不对）
（2）位置索引
这种方式需要按下面这种方式设计倒排表。这里我们要接受一个事实，倒排记录表的空间将会扩得很大，看你怎么去trade-off。
为了处理短语查询，仍然需要访问各个词条的倒排记录表。但是不是简单判断两个词汇是否在同一篇文章中，还有一层递近关系，出现在文档中且两个单词的距离小于k。这种方法被称作k次近邻搜索。
具体的方法：我们首先扫描倒排表，发现两个词出现在同一篇文章中，然后定住一个词的位置，去搜索另一个词的位置，搜索到小于k距离的位置加入到结果当中。
（3）混合索引
有些词采用短语查询（这个根据用户的访问日志得到），有些词采用位置索引。
用户的输出不可能完全正确吧，有关查询矫正请看：http://blog.csdn.net/lsjseu/article/details/12234769