第讲词汇表和倒排记录表Thetermvocabularyandpostings.pptVIP

第二种解决方法: 带位置信息索引(Positional indexes) 在倒排记录表中，对每个term在每篇文档中的每个位置(偏移或者单词序号)进行存储: term, 出现term的文档篇数； doc1: 位置1, 位置2 … ; doc2: 位置1, 位置2 … ; 等等 位置索引的例子 对于输入的短语查询，需要在文档的层次上进行迭代(不同位置上)合并 不仅仅简单合并，还要考虑位置匹配 be: 993427; 1: 7, 18, 33, 72, 86, 231; 2: 3, 149; 4: 17, 191, 291, 430, 434; 5: 363, 367, … 1,2,4,5这几篇文章 中哪篇包含 “to be or not to be”? 短语查询的处理 短语查询：“to be or not to be” 对每个词项，抽出其对应的倒排记录表: to, be, or, not. 合并docID:位置 表，考虑 “to be or not to be”. to: 2:1,17,74,222,551; 4:8,16,190,429,433; 7:13,23,191; ... be: 1:17,19; 4:17,191,291,430,434; 5:14,19,101; ... 邻近有哪些信誉好的足球投注网站中的有哪些信誉好的足球投注网站策略与此类似，不同的是此时考虑前后位置之间的距离不大于某个值 邻近式查询(Proximity query) LIMIT! /3 STATUTE /3 FEDERAL /2 TORT /k 表示 “在 k 个词之内” 很明显，位置索引可以处理邻近式查询，而双词索引却不能 位置索引的大小 位置索引增加了位置信息，因此空间较大，但是可以采用索引压缩技术进行处理(参见第五讲) 当然，相对于没有位置信息的索引，位置索引的存储空间明显大于无位置信息的索引 另外，位置索引目前是实际检索系统的标配，这是因为实际中需要处理短语(显式和隐式)和邻近式查询 位置索引的大小 词项在每篇文档中的每次出现都需要一个存储单元 因此索引的大小依赖于文档的平均长度 平均Web页面的长度 1000 个词项 美国证监会文件(SEC filings), 书籍, 甚至一些史诗 … 和容易就超过 100,000 个词项 假定某个词项的出现频率是0.1% Why? 100 1 100,000 1 1 1000 位置索引存储单元 倒排记录表的数目 文档大小 一些经验规律 位置索引的大小大概是无位置信息索引的2-4倍 位置索引大概是原始文本容量的35-50% 提醒：上述经验规律适用于英语及类英语的语言 混合索引 上述两种索引方式可以混合使用 对某些特定的短语 (如“Michael Jackson”, “Britney Spears”) ，如果采用位置索引的方式那么效率不高 还有“The Who”（英国一著名摇滚乐队），采用位置索引，效率更低 Williams et al. (2004)对一种混合的索引机制进行了评估 采用混合机制，那么对于典型的Web查询(比例)来说，相对于只使用位置索引而言，仅需要其? 的时间 相对于只使用位置索引，空间开销只增加了26% 本讲小结 索引构建过程(特别是预处理） 如何对索引文档进行处理来得到词典 理解文档(document)的概念 词条化(Tokenization)，理解词条(token)的概念 词项生成，理解词项(term)的概念 倒排记录表 更快的合并算法: 跳表法(skip list) 短语查询的处理及带位置信息的倒排索引 参考资料 《信息检索导论》第 2章 MG 3.6, 4.3; MIR 7.2 Porter’s stemmer: /~martin/PorterStemmer/ 跳表理论: Pugh (1990) Multilevel skip lists give same O(log n) efficiency as trees H.E. Williams, J. Zobel, and D. Bahle. 2004. “Fast Phrase Querying with Combined Indexes”, ACM Transactions on Information Systems. .au/research/research.php?author=4 D. Bahle, H. Williams, and J. Zobel. Efficient phrase querying with an auxiliary index. SIGIR 2002, pp. 215-221. 课后练习 习题2-1 习题2-6 习题2-9 * * * * * Nontrivial issues. Requires some