信息检索索引和查找

《信息检索索引和查找》由会员分享，可在线阅读，更多相关《信息检索索引和查找（26页珍藏版）》请在装配图网上搜索。

1、信息检索索引和查找提纲n顺序查找n索引查找l签名文件l倒排文件lPAT树（Patricia tree）n关于压缩说明n索引和查找的关系l索引和查找其实是密不可分的l建索引时必须不断的执行查找操作n查找和查询的区别l查找（search）n如何在索引中定位关键词信息l查询（query）nQuery处理：如何根据用户输入确定关键词n检索模型：如何利用查找返回的信息计算相似度等n文本压缩和索引压缩的区别l注意文本压缩不能有效地减少索引文件的大小顺序查找n精确匹配算法lBrute ForcelKnuth-Morris-PrattlBoyer-MoorelShift-OrlSuffix Automaton

2、n容错匹配算法lDynamic ProgramminglNon-deterministic Finite AutomatonlBit-Parallelismn正则表达式和扩展模式索引n索引文件l为方便查找，描述原文件信息组织的文件l签名文件，倒排文档，后缀树都是索引文件签名文件nKarp-Rabin匹配思想l假设我们现在要判断字符串A和字符串B是否匹配l把A和B分别散列成数字hash(A)和hash(B)l如果hash(A)!=hash(B)则A!=Bl然而hash(A)=hash(B)不能说明 A B nKarp-Rabin匹配例子关键词 x0.5：A A C T C T Hash(x0.5

3、)=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签名文件n文档的签名l把文档中的关键词散列成F位的位串Signaturel顺序访问原文档的关键词，把散列所得的位串依次存入文件n重叠编码(superimposed coding)l我们不需要为每个关键词都保存一个Signaturel多个关键词共用一个Signature可以减少文件的长度n错误匹配（False drop）l由于重

4、叠编码和哈希冲突的原因，关键词和Signature不是一一对应的关系lSignature匹配并不能保证关键词一定出现，还需要检查Block 1Block2 Block3 Block4000101110101100100101101文本文本签名文件签名文件h(text)=000101h(many)=110000h(words)=100100h(made)=001100h(letters)=100001This is a text.A text has many words.Words are made from letters.签名文件签名文件n优点l文件组织简单，基本和原文档顺序一致l维护容易

5、，生成，插入，删除都很方便l所需空间小，特别是采用重叠编码之后n缺点l检索速度慢，需要顺序扫描l并且，当False Drop发生的时候需要比较原文档n总之l签名文件是倒排文档和全文扫描之间的折中倒排文件n倒排索引思想l每个文档都可以用一系列关键词来表示 l如果按关键词建立到文档的索引便可以根据关键词快速地检索到相关文档 n倒排文件组成l词汇表（Vocabulary）n根据Heaps定律，通常比较小O(n),:0.40.6n通常我们称存放词汇表的文件为索引文件索引文件（index file）l出现位置（Occurrence）n较大，O（n），通常在原文本的3040n通常我们称存放出现位置的文件为

6、置入文件置入文件（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 VocabularyOccurrencesTextaddressing granularity:(1)inverted list(2)word positions(3)character positions(2)inverted file(3)docu

7、ment倒排文件n块地址索引l有时候为了节省索引空间，可按块地址建索引l把原文划分为多个块，只记录关键词的块地址Block1 Block2 Block3 Block 4This is a text.A text has many words.Words are made from letters.letters4 made4 many2 text1,2 words3 VocabularyOccurrencesTextInverted index倒排文件n倒排文件的性能l时间代价时间代价主要取决于词汇表的组织方式n词表文件通常较小且比较固定n对于未登录词和数词可以按字建索引l空间代价空间代价主要

8、取决于对置入文件的压缩能力n置入文件的压缩能减少IO操作，也能提高部分时间性能n词汇表文件的组织方式l采用Hash散列表l按字母表顺序有序排列l采用Trie树，B树等查找树n置入文件的压缩l通常采用差值压缩（delta compression）倒排文件n词汇表的哈希存储l根据给定的关键字，散列成一个整数l用该整数作为词汇的访问地址l例如：如果我们按字索引，那么可以直接用字的编码 作为访问地址，对于2字节编码只需64K地址n优点l实现简单l速度极快n缺点l关键在于找到一个好的散列函数n随着现在散列空间的增大，问题相对简单l当冲突过多时效率会下降倒排文件n词汇表的顺序排列l把词汇按照字典顺序排列l

9、词汇的查找采用二分查找n优点l实现简单 词汇表体积小（通常只有几兆）n缺点l索引构建的效率一般n对于插入的文档需要反复地调用排序排序和查找查找算法l排序的时间复杂度为N*log N（分配排序例外）n索引合并时还需要堆排序等方法合并多个有序的词汇表l如果合并最主要的时间开销在于IO操作的话，这点还是次要的l检索的效率一般n二分查找logN的复杂度已经具有较好的效率n能不能变成和词汇数量无关的常数复杂度倒排文件nLucene的词汇表即采用这种方式n假设现在词表中有16，000个词nindexInterval=16n则在词表中需要查找次数为16log(1000)=26次倒排文件n词汇表的查找树l把词

10、汇表中的关键词以树的形式组织l二叉树，B树，Trie 等n二叉查找树l考虑到平衡性，性能低于二分查找nB树l是多路查找树，效率高于二叉树，实现更麻烦nTrie 树树l查找时间只跟词的长度有关l而于词表中词的个数无关l词表较大时才能体现出速度优势nLog(词表长度)E(词长)E表示期望Trie树n什么是trie树ltrie树是一种用于快速检索的多叉树结构ltrie树把要查找的关键词看作一个字符序列。n根据这一序列构造用于检索的树结构。l在trie树上进行检索类似于查阅英语词典。n例如，电子英文词典，为了方便用户快速检索英语单词，可以建立一棵trie树。词典单词：a、b、c、aa、ab、ac、ba

11、、ca、aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caabaTrie树n优点l查找效率高，与词表长度无关nTrie树的查找效率只与关键词长度有关n目前我们分词词表最长的词为13个字l“大不列颠及北爱尔兰联合王国”n事实上索引词表中词过长会降低检索召回率l用户如果只输入“北爱尔兰”则无法返回该结果l索引的插入，合并速度快n注意，直接遍历Trie树需要搜索大量的无效节点n可以把数据存在一个数组中，Trie只保存指针n这样合并时，只需要对数组进行遍历即可n缺点l所需空间较大n如果是完全m叉树，节点数指数级增长n好在Trie不是，但所需空间仍然很大n不可

12、达上限：词数 字符序列长度 字符集大小 指针长度n例如：20000 6 256 4 120Ml实现较复杂差值压缩（Delta Compression）n置入文件l置入文件必须包含如下信息n当前词出现的文档号ID，以及在文档中的位置Posn差值压缩l记录当前ID和前一ID的差值l记录当前Pos和前一Pos的差值l这样做能有效减少表示ID，Pos所需的字长n例如：关键词A在文档13，124，346中出现 如果不压缩，由于346256,需要要两个字节 而346124222256，只需一个字节n应用实例lLucene对词汇表和置入文件都采用了这种压缩PAT树（Patricia tree）n什么是Pat

13、ricia树lPatricia树是Trie树的压缩表示压缩表示l所有只有一个子节点的节点都和父节点合并n后缀树（Suffix tree）l以文本所有后缀为关键词的Patricia树l后缀树的引入主要是针对字符串的高效查找n子串查找n最长重复子串n最长公共子串n回文子串n后缀数组（Suffix array）l按后缀树的先根遍历顺序，存储后缀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 Trie60502819114033lm

14、adntextwords605502819114033lmdntw163Suffix Treespace overhead:120%240%over the text sizeTextdifference between suffix array and inverted listnsuffix array:the occurrences of each word are sorted lexicographically by the text following the wordninverted list:the occurrences of each word are sorted by

15、 text position1 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 ArrayInverted listVocabularySupra-Index关于压缩n文本压缩l只对文本预处理时所采用的编码压缩技术n顺序查找l文本压缩能有效减少文本的存储空间l由于查找空间减少，能有效提高查找速度n索引查找l文本压缩能减少词汇表的存储空间l文本压缩对置入文件的存储空间没有影响l查找效率（不考虑文本预处理时间）n一方面增加了对查找关键词进行编码转换的时间n另一方面可以减少查找词表的时间l对于顺序词表，可以减少关键词比较时的时间l对于Trie 词表，可以使常用词用较短编码，减少E（词长）谢谢！