胡晓光信息检索实验室.ppt
胡晓光信息检索实验室,索引和查找,提纲,顺序查找索引查找签名文件倒排文件PAT树（Patricia tree）关于压缩,说明,索引和查找的关系索引和查找其实是密不可分的建索引时必须不断的执行查找操作查找和查询的区别查找（search）如何在索引中定位关键词信息查询（query）Query处理：如何根据用户输入确定关键词检索模型：如何利用查找返回的信息计算相似度等文本压缩和索引压缩的区别注意文本压缩不能有效地减少索引文件的大小,顺序查找,精确匹配算法Brute ForceKnuth-Morris-PrattBoyer-MooreShift-OrSuffix Automaton容错匹配算法Dynamic ProgrammingNon-deterministic Finite AutomatonBit-Parallelism正则表达式和扩展模式,索引,索引文件为方便查找，描述原文件信息组织的文件签名文件，倒排文档，后缀树都是索引文件,签名文件,Karp-Rabin匹配思想假设我们现在要判断字符串A和字符串B是否匹配把A和B分别散列成数字hash(A)和hash(B)如果hash(A)!=hash(B)则A!=B然而hash(A)=hash(B)不能说明 A B,Karp-Rabin匹配例子关键词 x0.5：A A C T C T Hash(x0.5)=17579文本y0.9：G C A A C T C T C A Hash(y0.5)=17819文本y0.9：G C A A C T C T C A Hash(y1.6)=17533文本y0.9：G C A A C T C T C A Hash(y2.7)=17579,签名文件,文档的签名把文档中的关键词散列成F位的位串Signature顺序访问原文档的关键词，把散列所得的位串依次存入文件重叠编码(superimposed coding)我们不需要为每个关键词都保存一个Signature多个关键词共用一个Signature可以减少文件的长度错误匹配（False drop）由于重叠编码和哈希冲突的原因，关键词和Signature不是一一对应的关系Signature匹配并不能保证关键词一定出现，还需要检查,Block 1Block2 Block3 Block4,000101110101100100101101,文本,签名文件,h(text)=000101h(many)=110000h(words)=100100h(made)=001100h(letters)=100001,This is a text.A text has many words.Words are made from letters.,签名文件,签名文件,优点文件组织简单，基本和原文档顺序一致维护容易，生成，插入，删除都很方便所需空间小，特别是采用重叠编码之后缺点检索速度慢，需要顺序扫描并且，当False Drop发生的时候需要比较原文档总之签名文件是倒排文档和全文扫描之间的折中,倒排文件,倒排索引思想每个文档都可以用一系列关键词来表示 如果按关键词建立到文档的索引便可以根据关键词快速地检索到相关文档 倒排文件组成词汇表（Vocabulary）根据Heaps定律，通常比较小O(n),:0.40.6通常我们称存放词汇表的文件为索引文件（index file）出现位置（Occurrence）较大，O（n），通常在原文本的3040通常我们称存放出现位置的文件为置入文件（posting file）,倒排文件,1 6 9 11 17 19 24 28 33 40 46 50 55 60This is a text.A text has many words.Words are made from letters.,letters60 made50 many28 text11,19 words30,40,VocabularyOccurrences,Text,addressing granularity:inverted list word positionscharacter positionsinverted file document,倒排文件,块地址索引有时候为了节省索引空间，可按块地址建索引把原文划分为多个块，只记录关键词的块地址,Block1 Block2 Block3 Block 4This is a text.A text has many words.Words are made from letters.,letters4 made4 many2 text1,2 words3,VocabularyOccurrences,Text,Inverted index,倒排文件,倒排文件的性能时间代价主要取决于词汇表的组织方式词表文件通常较小且比较固定对于未登录词和数词可以按字建索引空间代价主要取决于对置入文件的压缩能力置入文件的压缩能减少IO操作，也能提高部分时间性能词汇表文件的组织方式采用Hash散列表按字母表顺序有序排列采用Trie树，B树等查找树置入文件的压缩通常采用差值压缩（delta compression）,倒排文件,词汇表的哈希存储根据给定的关键字，散列成一个整数用该整数作为词汇的访问地址例如：如果我们按字索引，那么可以直接用字的编码 作为访问地址，对于2字节编码只需64K地址优点实现简单速度极快缺点关键在于找到一个好的散列函数随着现在散列空间的增大，问题相对简单当冲突过多时效率会下降,倒排文件,词汇表的顺序排列把词汇按照字典顺序排列词汇的查找采用二分查找优点实现简单 词汇表体积小（通常只有几兆）缺点索引构建的效率一般对于插入的文档需要反复地调用排序和查找算法排序的时间复杂度为N*log N（分配排序例外）索引合并时还需要堆排序等方法合并多个有序的词汇表如果合并最主要的时间开销在于IO操作的话，这点还是次要的检索的效率一般二分查找logN的复杂度已经具有较好的效率能不能变成和词汇数量无关的常数复杂度,倒排文件,Lucene的词汇表即采用这种方式假设现在词表中有16，000个词indexInterval=16则在词表中需要查找次数为16log(1000)=26次,倒排文件,词汇表的查找树把词汇表中的关键词以树的形式组织二叉树，B树，Trie 等二叉查找树考虑到平衡性，性能低于二分查找B树是多路查找树，效率高于二叉树，实现更麻烦Trie 树查找时间只跟词的长度有关而于词表中词的个数无关词表较大时才能体现出速度优势Log(词表长度)E(词长)E表示期望,Trie树,什么是trie树trie树是一种用于快速检索的多叉树结构trie树把要查找的关键词看作一个字符序列。根据这一序列构造用于检索的树结构。在trie树上进行检索类似于查阅英语词典。例如，电子英文词典，为了方便用户快速检索英语单词，可以建立一棵trie树。,词典单词：a、b、c、aa、ab、ac、ba、ca、aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caaba,Trie树,优点查找效率高，与词表长度无关Trie树的查找效率只与关键词长度有关目前我们分词词表最长的词为13个字“大不列颠及北爱尔兰联合王国”事实上索引词表中词过长会降低检索召回率用户如果只输入“北爱尔兰”则无法返回该结果索引的插入，合并速度快注意，直接遍历Trie树需要搜索大量的无效节点可以把数据存在一个数组中，Trie只保存指针这样合并时，只需要对数组进行遍历即可缺点所需空间较大如果是完全m叉树，节点数指数级增长好在Trie不是，但所需空间仍然很大不可达上限：词数 字符序列长度 字符集大小 指针长度例如：20000 6 256 4 120M实现较复杂,差值压缩（Delta Compression）,置入文件置入文件必须包含如下信息当前词出现的文档号ID，以及在文档中的位置Pos差值压缩记录当前ID和前一ID的差值记录当前Pos和前一Pos的差值这样做能有效减少表示ID，Pos所需的字长例如：关键词A在文档13，124，346中出现 如果不压缩，由于346256,需要要两个字节 而346124222256，只需一个字节应用实例Lucene对词汇表和置入文件都采用了这种压缩,PAT树（Patricia tree）,什么是Patricia树Patricia树是Trie树的压缩表示所有只有一个子节点的节点都和父节点合并后缀树（Suffix tree）以文本所有后缀为关键词的Patricia树后缀树的引入主要是针对字符串的高效查找子串查找最长重复子串最长公共子串回文子串后缀数组（Suffix array）按后缀树的先根遍历顺序，存储后缀,1 6 9 11 17 19 24 28 33 40 46 50 55 60This is a text.A text has many words.Words are made from letters.,Suffix Trie,60,50,28,19,11,40,33,l,m,a,d,n,t,e,x,t,w,o,r,d,s,60,5,50,28,19,11,40,33,l,m,d,n,t,w,1,6,3,Suffix Tree,space overhead:120%240%over the text size,Text,difference between suffix array and inverted list,suffix array:the occurrences of each word are sorted lexicographically by the text following the wordinverted list:the occurrences of each word are sorted by text position,1 6 9 11 17 19 24 28 33 40 46 50 55 60This is a text.A text has many words.Words are made from letters.,Suffix Array,Inverted list,VocabularySupra-Index,关于压缩,文本压缩只对文本预处理时所采用的编码压缩技术顺序查找文本压缩能有效减少文本的存储空间由于查找空间减少，能有效提高查找速度索引查找文本压缩能减少词汇表的存储空间文本压缩对置入文件的存储空间没有影响查找效率（不考虑文本预处理时间）一方面增加了对查找关键词进行编码转换的时间另一方面可以减少查找词表的时间对于顺序词表，可以减少关键词比较时的时间对于Trie 词表，可以使常用词用较短编码，减少E（词长）,谢谢！,
