检索的改进技术.ppt

* * * * * * 批更新实时性差 * * * * * * * * * * * * * * * * Parsing:从文档中挑选出索引词的过程。 * * * * * * 需要针对每个term，计算 N(N-1)/2 个文档对的相似度 * * * * * * * * * * * * * * * * Karp-Rabin算法 (2) Hash函数将 m 个字符的比较降低为单个整数的比较, 但是需要一个快速的散列函数 Karp和Rabin建议使用函数h(x) = x mod q ，q 是一个适当大的质数 对 m 个字符的字符串 sksk+1…sk+m-1, 计算 xk = sk bm-1 + sk+1 bm-2 + … + sk+m-1 xk+1 = (xk - sk bm-1)b + sk+m ascii(e) 如果模式的hash值和文本的hash值每次都匹配，这是最坏的情况，时间复杂度为 O(mn) ，几乎不可能出现 期望的时间复杂度是： O(m+n) string = abcde ascii(a) = 97 m = 4 hash(“abcd”) = (97*23 + 98*22 + 99*21 + 100*20 ) % q = 1466 % q hash(“bcde”) = [ ( 1466 - 97*23) * 2 + 101 ] % q hash(“bcde”) = (98*23 + 99*22 + 100*21 + 101*20 ) % q = 1481 % q 本章小结 文本的表示方法 倒排文件，后缀数组和签名档的建立及检索 字符串匹配技术 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 顺序检索 顺序检索技术 前面介绍的文本有哪些信誉好的足球投注网站技术需要事先建立索引，然后执行快速的查询 但是，在某些应用中，这种建立索引的方法并不适用 在签名文件的候选块确认过程中，就需要在块中查找某一查询是否真正存在； 在文本过滤技术，一般文本仅需要查询一次，这就没有建立索引； 在有哪些信誉好的足球投注网站引擎中结果后处理中，需要对有哪些信誉好的足球投注网站结果中包含的查询关键词进行加亮显示，也需要用到文本有哪些信誉好的足球投注网站技术。 顺序检索技术，也具有很广阔的应用场合。快速的顺序检索是非常必要的 全文扫描(Full Text Scanning) 不维护索引表 直接在文本上进行有哪些信誉好的足球投注网站 需要模式匹配和逻辑组合来处理布尔条件 This is a long article on HIT Query: article AND HIT HIT article AND hit pattern matcher 全文扫描 优点: 不在索引方面花费时空开销 适用于文本频繁产生和更新的动态环境 在原始文本上完成有哪些信誉好的足球投注网站任务 理论上，文本中的任何信息都可以被找到 (例如, 不需要no 停用词和Stemming操作) h1HIT/h1p…/pp…computer…/p 查询: “computer” 出现在以“HIT” 为标题的某个章的第二段里 h1HIT/h1 p*computer*/p logic hit pattern matcher hit, doc#, loc, etc. 缺点: 有哪些信誉好的足球投注网站速度慢，但对于小文档集合来说是可以接受的。 (例如个人文档集合) 模式匹配算法 基本的文本扫描操作： 字符串有哪些信誉好的足球投注网站 给定一个单独的关键词p(有哪些信誉好的足球投注网站串)和一个输入串 s, 如果p 是s 的子串就回答yes，否则回答no 单模式的字符串匹配技术 Brute Force串匹配算法 快速串匹配算法 KMP算法 BM算法 模式匹配——BF算法 Brute Force算法(1) 有哪些信誉好的足球投注网站串 (模式): p1p2…pm 文本串: s1s2…sn (通常 n m) 将模式和m个字符的字串sksk+1…sk+m-1进行匹配，k从1到n - m +1. 模式要么和子串匹配，要么找到一个位置发现二者不匹配 p1 … pi … pm s1… sk … sj… sk+m-1 ... Brute Force算法(2) begin i := 1 j := 1 while i ? m and j ? n do if pi = sj then begin i := i +1; j := j +1 end else begin j := j - i + 2; i :=1 end if i m then return “yes else return “no” end 此循环可以更早地 终止: j ? n - m + 1 最多 n ? m 次 i=1 j=8 i=7 j=14 travel information informing i=1 j=9 travel informatio