关于信息检索的基础知识

1、主要内容：    

信息检索系统中两个重要的数据结构：词项词典和全体倒排记录表，为了构建高效的IR系统，需要对这两个数据结构进行压缩。进行压缩有两个隐含的优点：①、能增加高速缓存（cache）技术的利用率：将频繁使用的查询此项t的倒排记录表采用压缩技术放到高速缓存中，当查询词项t的时候，不再需要进行磁盘操作，而只需要将其倒排记录表在内存中解压缩即可；②、压缩能够加快数据从磁盘到内存的传输速度：将压缩的数据块传输到内存并且解压缩用到的时间往往比将为压缩的数据块传输到内存用到的时间少，因为I/O操作的时间相对来说较长。     ①、在大规模文档集中待压缩对象（包括此项和倒排索引）的统计特性；     ②、采用”将词典视为长串“及按快存储的词典压缩技术；
    ③、两种倒排索引记录表的压缩方法：边长字节编码和γ编码。
有损压缩：大小写转换、词干还原、停用词剔除、向量空间模型和LSA的降维技术不可能完全恢复到原始的文档集。有一定的意义。 无损压缩：下面介绍的主要是无损压缩。 2、信息检索中词项的统计特性：     ①、Heaps定律：词项数目的估计：           词汇量的大小依赖于文档集本身以及对它进行处理的方法；             1、随着文档数目的增加，词汇量会持续增长而不会文档到一个最大值；（牛津英语词典的单词数目超过了600000，而对于大规模的文档集来说，其词汇量还远远不够：词典中没有包含大部分的人名、地名、产品名或包含基因各在内的大部分科学试题名称。）             2、大规模文档记得词汇量也会非常大。     ②、Zipf定律：对此项的分布建模：cfi ∝ (1/i)         词项在文档中的分布情况，能够为倒排记录表的压缩算法提供支持；         如果出现最多的词项的出现次数是cf1的话，出现第二多的词项的出现次数就是cf1的1/2，第三多的就是1/3。        其中： cfi 是文档频率(collection frequency): 某个词项在所有文档中出现的次数(不是出现该词项的文档数目df)。 3、词典压缩：

 对于未压缩的词典，存储空间为：M*(20+4+4)=400000*28=11.2M。

 ①、将词典看成单一字符串的压缩方法；
压缩之后存储空间未：400000*（4+4+3+8）=7.6M。

图5-4
    ②、按块存储；
使用块存储，存储空间：7.1M。

图5-5 当文档集规模很大而内存很小时，无法将词典存入内存中，这是就需要吧词典划分成不同页存储在磁盘上，则可以采用B树对煤业的第一个词项进行索引。在处理大多数查询时，搜索系统必须要到磁盘获取倒排记录表，而在分页方式下，还有首先从磁盘上取词项所在的词典页。

4、倒排记录表的压缩：     ①、可变字节码；      

对间隔编码: 存储docID间隔而不是docID本身 

可变字节(VB)码

变长的整数类型，它可能包含多个Byte，对于每个Byte的8位，其中后7位表示数值，最高1位表示是否还有另一个Byte，0表示没有，1表示有。 越前面的Byte表示数值的低位，越后面的Byte表示数值的高位。 例如130化为二进制为 1000, 0010，总共需要8位，一个Byte表示不了，因而需要两个Byte来表示，第一个Byte表示后7位，并且在最高位置1来表示后面还有一个Byte， 所以为(1) 0000010，第二个Byte表示第8位，并且最高位置0来表示后面没有其他的Byte了，所以为(0) 0000001。