信息检索复习（2）——词项词典及倒排记录表

构建倒排索引步骤

概念：
- 词条化将给定的字符序列分成一系列子序列的过程
- 词条：每一个子序列是一个词条，是在文档中出现的字符序列的一个实例
- 一个词条类：相同词条构成的集合
- 一个词项：在信息检索系统词典中包含的某个可能经过归一化处理的词条类
  例：“to sleep perchance to dream”
  得到5个词条，4个词条类（重复的to），3个词项（去除停用词to）
词条化任务：确定哪些才是正确的词条
只要根据空格将字符串进行拆分去除标点符号？
英文“ ' ”：既可表达关系也可代表缩写
例：O'Neill -> neill/ oneill/ o'neill/ o' + neill/ o + neill?
简单做法：在既非字符也非数字的字符处进行拆分（o + neill），使用相同的词条化工具来实现
不同语言下的词条化处理并不相同
有效的语言种类识别：利用短字符子序列作为特征来进行分类
- 编程语言：“C++”，“C#”
- 飞行器名称：“B-25”
- 固定流行语
- 新的字符序列类型：邮件地址、IP地址、URL、包裹追踪号

概念
- 停用词（stop）：一些在文档和用户需求进行匹配时价值并不大，需要彻底从词汇表中去除的常见词。
- 文档集频率（collection frequency）：每个词项在文档集中出现的频率
常见生成停用词表的方法：将词项按照文档集频率从高到低排序，然后手工选择把那些语义内容与文档主题关系不大的高频词作为停用词。
好处：大大减小系统所需要存储的倒排记录表
问题：不对停用词建立索引很多时候对系统并没什么影响，但一些特殊情况如query全为停用词组成（to be or not to be）会有很大影响。
Web搜索引擎通常不使用停用词表。
- 压缩技术
- 如何利用语言的统计特性来更好处理常见词的问题
- 词项权重计算，将高频常见词对文档排序的影响降至极低
- 按照影响度大小排序，当权重变小，会及早停止对倒排记录表的继续扫描

相同：目的都是为了减少词的屈折变化形式，并且有时会将派生词转化为基本形式。
不同
词干还原：一个很粗略的去除单词两端词缀的启发式过程，并且希望大部分时间它都能达到这个正确目的，这个过程也常常包括去除派生词缀。（提高召回率降低正确率）
词形归并：利用词汇表和词形分析去除屈折词缀，从而返回词的原形或词典中词的过程，返回的结果成为词元。
词干还原算法：Porter算法（规则）
规则：示例
SSES -> SS caresses -> caress
IES ->I ponies -> poni
SS -> SS caress -> care
SS -> cat -> cat
词形归并例子： am,is,are => be

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

时间复杂度O（m+n）的基本合并算法的优化
指针个数和比较次数之间的折中问题：跳表指针越多意味着跳跃的步长越短，那么在合并过程中跳跃的可能性也更大，但同时这也意味着需要更多的指针比较次数和更多的存储空间。跳表指针越少意味着更少的指针比较次数，但同时也意味着更长的跳跃步长，也就是说意味着更少的跳跃机会。
简单的启发式策略：对于长度为P的倒排记录表，每√P处放一个跳表指针，即均匀放置，均匀放置方法忽略了查询词项的分布情况
如果索引相对固定的话，均匀方式方法是一种很简便的方法。但是如果倒排记录表由于经常更新而发生变化，那么跳表指针的建立就比较困难。恶意的删除策略可能会使跳表完全失效。
查询使用标准的倒排记录表与使用倒排记录表+跳表的方式所需比较次数问题(每次到达指针处需要比较下一跳的值决定能不能跳，太大则不进行跳比较下一节点值)

对于每一个词项存储方式：文档ID: <位置1，位置2，...>
例(保存词频)
to, 993427:
<1,6:<7,18,33,72,86,231>;
2,5:<1,17,74,222,255>;...>
单词to的文档频率为993427，在文档一出现了6次，位置分别是7,18,33,72,86,231。
短语查询：采用文档频率优先策略，不止简单判断两个词项是否出现在同一文档这两个，而且还需要检查他们出现的位置关系与查询当中是否保持一致。=》计算词之间的偏移距离
k词邻近搜索：/k 从左边或右边相距在k个词之内（employment /3 place）