倒排检索构建课件.ppt

倒排检索构建 主讲人：陈文亮 苏州大学计算机学院 提纲 倒排索引 布尔查询的处理 一个简单的例子(金庸小说) 金庸的哪本小说包含郭靖和黄蓉但不包含洪七公？ 布尔表达式为 郭靖 AND 黄蓉 AND NOT 洪七公 笨方法： 从头到尾扫描所有小说，对每本小说判断它是否包含郭靖和黄蓉但不包含洪七公 笨方法为什么不好? 速度超慢 (特别是大型文档集) 不太容易支持其他操作 (e.g., find the word Romans near countrymen) 不支持检索结果的排序 (即只返回较好的结果) 词项-文档(term-doc)的关联矩阵 若某小说包含某单词，则该位置上为1，否则为0 郭靖 AND 黄蓉 BUT NOT 洪七公 射雕英雄传 神雕侠侣 天龙八部 倚天屠龙记 鹿鼎记 郭靖 1 1 0 1 0 黄蓉 1 1 0 1 0 洪七公 1 1 0 0 0 张无忌 0 0 0 1 0 韦小宝 0 0 0 0 1 关联向量(incidence vectors) 关联矩阵的每一列都是 0/1向量，每个0/1都对应一个词项 给定查询郭靖 AND 黄蓉 BUT NOT 洪七公 取出三个列向量 ，并对 洪七公的列向量求补，最后按位进行与操作 11010 AND 11010 AND 00111 = 00010. 上述查询的结果文档 倚天屠龙记 IR中的基本假设 文档集Collection: 由固定数目的文档组成 目标: 返回与用户需求相关的文档并辅助用户来完成某项任务 相关性Relevance 主观的概念 反映对象的匹配程度 不同应用相关性不同 典型的有哪些信誉好的足球投注网站过程 文档集 任务 信息需求 查询 自然语言描述 结果 有哪些信誉好的足球投注网站 引擎 查询 重构 Get rid of mice in a politically correct way Info about removing mice without killing them How do I trap mice alive? mouse trap 是否转义? 是否转义? 是否转义? 检索效果的评价 正确率(Precision) : 返回结果文档中正确的比例。如返回80篇文档，其中20篇相关，正确率1/4 召回率(Recall) : 全部相关文档中被返回的比例，如返回80篇文档，其中20篇相关，但是总的应该相关的文档是100篇，召回率1/5 正确率和召回率反映检索效果的两个方面，缺一不可。 全部返回，正确率低，召回率100% 只返回一个非常可靠的结果，正确率100%，召回率低 大文档集 假定N = 1 百万篇文档(1M), 每篇有1000个词(1K) 假定每个词平均有6个字节(包括空格和标点符号) 那么所有文档将约占6GB 空间. 假定 词汇表的大小(即词项个数) M = 500K 词项-文档矩阵将非常大 矩阵大小为 500K x 1M=500G 但是该矩阵中最多有10亿(1G)个1 词项-文档矩阵高度稀疏(sparse). 稀疏矩阵 应该有更好的表示方式 求方法？ Why? 词项-文档矩阵将非常大 应该有更好的表示方式 比如我们仅仅记录所有1的位置 倒排索引(Inverted index) 对每个词项t, 记录所有包含t的文档列表. 每篇文档用一个唯一的 docID来表示，通常是正整数，如1,2,3… 能否采用定长数组的方式来存储docID列表 Brutus Calpurnia Caesar 1 2 4 5 6 16 57 132 1 2 4 11 31 45 173 2 31 文档14中加入单词Caesar时该如何处理? 174 54 101 倒排索引(续) 通常采用变长表方式 磁盘上，顺序存储方式比较好，便于快速读取 内存中，采用链表或者可变长数组方式 存储空间/易插入之间需要平衡 Dictionary Postings 按docID排序 (原因后面再讲) Posting Brutus Calpurnia Caesar 1 2 4 5 6 16 57 132 1 2 4 11 31 45 173 2 31 174 54 101 词典 倒排(记录)表 倒排记录 Tokenizer 词条流 Friends Romans Countrymen 倒排索引构建 Linguistic modules 修改后的词条 friend roman countryman Indexer 倒排索引 friend roman countryman 2 4 2 13 16 1 待索引文档 Friends, Romans, countrymen. 词条化工具 语言分析工具 索引构建过程: 词条序列 词条，docID二元组 I did enact Julius Caesar I was ki