• 1. 各种编码方式(一) 一元编码(Unary Code) 一个数n由n-1个1跟着一个0组成 以n=9为例,111111110 n占用的空间为 n bit γ(Gamma) Code 联合unary编码和二进制编码binary codes unary 编码 存储 用二进制编码表达n所用的位数,二进制编码 存储 用于恢复n的信息 unary 编码占用存储空间为 1 + |_log n_|,binary 占用存储空间为|_log n_|,存储的数为 n - 2 |_log n_| 以n=9为例,|_log 9_| = 3, so unary code is 1110,9-8=1, so binary code is 001,其编码为 1110 001 (7 bits) n占用的空间为 1 + 2 * |_log n_|1
  • 2. 各种编码方式(二)δ(delta) Code 用γ编码 编码 γ编码的长度部分 以n=9为例,其γ编码的长度为4,4的γ编码为 11000,故9的δCode为 11000 001 n占用的空间为 Golomb 编码 前 q+1 用 unary编码, q=|_(x-1)/b_| 余数 r=x-q*b-1 用二进制编码,需要 或 位,如果 r<2 |_logb_|-1,在二进制编码中需要 位,否则需要 位,其中第一个位为1。若b=3,则r=0 (0)、 r=1 (10)、 r=2 (11) b取3,以n=9为例,q=|_(9-1)/3_|=2,故其unary编码为 110, r=9-2*3-1=2,故其二进制编码为 11,故9的Golomb编码为11011 2
  • 3. 7. 索引和搜索Indexing and Searching倒排文件构建Inverted Files Construction 搜索Searching3
  • 4. 索引大小在第一讲我们初步研究了索引空间 同时也考虑了 stemming, case folding, stop words ... 提取词根等操作对于索引大小的影响如何?4
  • 5. 索引大小词根化和小写归一化处理能够降低 词的数量降低 ~40% 指针的数量降低10-20% 总空间大小降低 ~30% 停用词 Rule of 30:大约30个最常见的词占了书面文字中所有词的30% 从索引里消除150个最常见的词能够降低大约25%的索引空间5
  • 6. 包含位置信息的索引大小需要每个出现位置有一个条目, 不是一个文档一个条目 索引的大小取决于平均文档大小 Average web page has <1000 terms filings, books, even some epic poems … easily 100,000 terms 考虑一个出现频率为 0.1%的词(所需条目空间如下表所示)1001100,000 words111000 wordsPositional postings包含位置信息的记录Postings一般记录Document size6
  • 7. 经验性的规律包含位置信息的索引positional index大小大概是只包含出现情况的索引non-positional index的 2-4倍 包含位置信息的索引平positional index大小大概是原始文本的35-50% 一些商用软件也称此比率为膨胀率,并用它作为衡量搜索引擎效率的一个重要指标 以上这些数据主要是对英文类似的语言有效7
  • 8. 索引构建索引的空间 索引建立的时间 有限内存情况下采用怎样的策略建立和维护索引?8
  • 9. 对于比较大的语料库Number of docs = n = 40M Number of terms = m = 1M 用齐普夫率 Zipf 来估量记录条目的数量 n + n/2 + n/3 + …. + n/m ~ n ln m = 560M entries 在不包含位置信息的情况下, 每个条目10-12 bytes (term, doc, freq)9
  • 10. 关键步骤文档解析后倒排文件按关键词排序10
  • 11. 文档解析后各个词以及词出现的文档都被解析出来I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me.Doc 1So let it be with Caesar. The noble Brutus hath told you Caesar was ambitiousDoc 2回忆索引构建的过程11
  • 12. 倒排文档实例 (MIR Ch.8, Fig. 8.1)This is a text. A text has many words. Words are made from letters.词汇表1691117192428334046505560letters made many text words事件表60…… 50…… 28…… 11,19…… 33,40……词汇表占用的空间较少,为O(nβ),范围为0-1,一般为0.4-0.6 事件表占用的空间较大,为O(n),大约为文本大小的30%-40%左右12
  • 13. 倒排文档(块寻址)实例 (MIR Ch.8, Fig. 8.2)词汇表letters made many text words事件表4…… 4…… 2…… 1,2…… 3……通过块寻址技术,可减少指针的数量 可以将出现在一个块中的同一个单词的所有事件压缩为一个参照条目 采用这项技术生成的索引只占相当于文本大小5%的存储空间 若要知道事件的精确位置,需要执行遍历相应块的联机检索This is a text.A text has manywords. Words aremade from letters.块1块2块3块413
  • 14. 索引构建解析文档构建索引的时候一般不进行压缩 由于文档逐个解析,倒排文件每个词的记录条目postings entry只有在所有文档解析完后才能确定 (actually you can exploit compression, but this becomes a lot more complex) 10-12 bytes 每记录条目postings entry, 通常需要数gigabytes的存储空间14
  • 15. 系统参数设定磁盘寻道时间Disk seek ~ 10-3 second 磁盘数据块传递时间Block transfer from disk ~ 10-6 second per byte (following a seek) 其它操作 ~ 10-6 second 15
  • 16. Bottleneck逐个文档解析和建立每个检索词的记录条目 postings entries 将记录条目postings entries按关键词排序 (then by doc within each term) 如果采用随机存取磁盘寻道进行排序将非常缓慢在排序比较过程中如果每比较一次都进行一次磁盘寻道, 那么n个条目比较将进行nlog2n次比较, 共花费多少时间?16
  • 17. Sorting with fewer disk seeks12-byte (4+4+4) records (term, doc, freq) 解析文档时将会产生以上记录 现在需要将 560M 这样的记录加以排序 定义块大小 Block=10M 两个这样的块可以被放进内存中操作处理 先在块内进行排序,然后将块进行合并17
  • 18. 排序,Sorting 56 blocks of 10M records首先,读出一块并进行排序操作 快速排序花费步数为大约 2 x (10M ln 10M) steps Exercise: 估计从磁盘读出每个数据块(10M)并进行快速排序的总时间 56 倍以上估计的时间 – 56轮,每轮排序10M的数据块 整个过程在硬盘上数据有两份拷贝 18
  • 19. 归并,Merging 56 sorted blocks外部排序归并树Merge tree of log256 ~ 6 layers 在归并树的每一层,以10M为单位将数据从磁盘读出,归并排序,然后写回磁盘Disk13424213B1B2B1’B3B4B2’B3’19
  • 20. 归并时间估算 Merging 56 block time磁盘传输总时间的估计值 6 x 56 x (120M x 10-6) x 2 ~ 22 hoursdisk block transfer timeWork out how these transfers are staged, and the total time for merging.120M: 10M Unit, with 12 byte/Unit [(4+4+4) records (term, doc, freq)]. Also refer to MG ch 5, pp.233, figure 5.420
  • 21. Large memory indexing假设我们有足够大内存来进行上述排序(e.g., 16GB),需要的时间是多少? 事实上,web搜索引擎的索引和抓取是并行的 Web数据集要比刚才的例子大得多,内存仍然是索引构建的瓶颈 抓取器的瓶颈在于广域网上网页抓取的速度以及很多其它因素(后面我们在谈到web搜索时会详细讲解)21
  • 22. 动态索引文档不断读入到系统中 对词典中已有的词更新记录 把新词加入到词典中 最简单的处理方法 保持一个大的主索引 新的文档进入到小的从索引当中 搜索在两个索引进行,归并结果 周期性的将从索引归并到主索引中去22
  • 23. 更加复杂的方法全动态更新 所有时间只有一个索引 没有大小索引之分 动态管理空间库23
  • 24. 全动态更新插入一个记录 e.g., a typical postings entry 维护64KB 大小的chunk池 Chunk头维护关于chunk内记录的元数据信息,以及chunk的剩余空间RecordRecordRecordRecordHeaderFree space24
  • 25. 全局跟踪在内存维护一个全局记录地址表,记载各记录所在的chunk 定义一个当前chunk 插入操作 如果当前的chunk有足够的空闲空间 将记录记入并更新chunk头的元数据信息 否则查看其它的chunk是否有足够空间 如果没有空间了就打开新的chunk25
  • 26. 索引在硬盘上以及在内存中的比较大多数IR系统将词典放置在内存中,出现位置记录放在外存硬盘上 Web搜索引擎常常将两者都放进内存 需要大量内存 对于大型搜索服务可行,但对于一般的系统性价比较高 这些系统往往查询负担并不太重 用户可以对响应稍作等待26
  • 27. 分布式索引考虑有多台机器进行索引的情况 如何利用并行来提高性能 两种基本方法 建立索引时切分词典 切分文档集27
  • 28. 真实世界里的索引通常对于搜索引擎,是对从网上抓取下来的网页等其它地方的信息进行索引搜索 文档需要从网上抓取 文档散布于网上,连接的速度也各不一样 必须通过调度分布式的网络爬虫/索引器 可能是存在于以下位置安全的内容 数据库 内容管理应用 Email 应用 对于一些内容,本地API拷贝往往比通过Http获取更有效28
  • 29. 真实世界里的索引文档格式多种多样 word processing formats (e.g., MS Word) spreadsheets电子表格 presentations publishing formats (e.g., pdf) 可根据格式通过定制“过滤器”将不同的格式去除 convert format into text + meta-data 文档有各种不同语言 automatically detect language(s) in a document tokenization, stemming, are language-dependent29
  • 30. Other Indexing techniquesSuffix Trie/Tree 将文本看作是一个长的字符串,文本中的每个位置都被认为是文本的一个后缀 索引点,指出文本中需要建立标引的起始位置 Suffix arrays 是后缀树的一种有效的空间实现 Signature files 一种基于散列变换(哈希)的面向单词的索引结构 大多数应用中倒排文件表现出来的性能要比签名档要好,无论从索引大小还是从查询处理时间上。30
  • 31. 后缀Suffixes (MIR Ch.8, Fig. 8.5)This is a text. A text has many words. Words are made from letters.text. A text has many words. Words are made from letters.text has many words. Words are made from letters.many words. Words are made from letters.words. Words are made from letters.Words are made from letters.letters.后缀Suffixes169111719242833404650556031
  • 32. Suffix Trie (MIR Ch.8, Fig. 8.6)60This is a text. A text has many words. Words are made from letters.1691117192428334046505560‘l’‘m’‘a’5028‘d’‘t’‘n’‘e’‘x’‘t’1911‘ ’‘.’‘w’‘o’‘r’‘d’4033‘ ’‘.’‘s’后缀Trie:一棵树,存储不同后缀。不同后缀每个相同的前缀都对应一个节点。后缀字符串存储在特别的叶子节点上。32
  • 33. 后缀树Suffix Tree60‘l’35‘m’5028‘d’‘t’‘n’1911‘ ’‘.’‘w’4033‘ ’‘.’6This is a text. A text has many words. Words are made from letters.1691117192428334046505560后缀树中间的数字代表索引点的长度 33
  • 34. 后缀数组Suffix Arraysuffix tree 的最大问题是占用空间太多 Each node takes 12-24 bytes, a space of 120% - 240% over the text size is produced suffix array是一种按照词典顺序排列并存储文本后缀全部指针的数组34
  • 35. 后缀数组例子This is a text. A text has many words. Words are made from letters.1691117192428334046505560Suffix arrayText6050281911403335
  • 36. 后缀数组之上建二级索引占用空间大小与倒排索引接近 close to 40% overhead over the text size 允许折半查找,数组较大时效率较低 suffix array较大时可以在suffix array之上建立二级索引 最简单的二级索引机制是从b个数组条目中采样,每个采样前l个后缀字母保存在二级索引中(Simplest supra-index is sampling of one out of b suffix array entries, where for each example the first l suffix array are stored in the supra-index)36
  • 37. 具有二级索引的后缀数组例子This is a text. A text has many words. Words are made from letters.1691117192428334046505560Suffix arrayText60502819114033letttextwordSupra-Index 在后缀数组上构建了二级索引,每3个位置采样一次,保持前四个字母。指针实际上是没用的。37
  • 38. 搜索后缀数组如果需要查找后缀S满足P1
  • 39. 在内存中构建后缀数组1. First letter sort -> O(n) 2. First two letters sort -> O(n) … i. First 2i letters sort -> O(n) … log(n). First n letters sort -> O(n) 总共 O(n*log(n)) 平均 O(n*log log(n)) (不一定要比较 log(n)次)39
  • 40. 较长的文本构建后缀数组为第一个文本块建立suffix array 为第二个文本块建立suffix array 将两个suffix array归并在一起 为第三个文本块建立suffix array 将新建立的与之前的suffix array归并 …40
  • 41. Merge the small array into already build large arraySmall textSmall suffix arrayCountersLong textLong suffix arrayFinal suffix array存储大型文本中有多少后缀位于小型后缀数组的每组位置之间41
  • 42. 签名档 Signature file 签名档是基于散列变换(哈希)的面向单词的索引结构 对文本分块,每块有b个单词 对每个大小为b的文本块, 赋予一个大小为B位的掩码 掩码通过对文本块中全部单词的签名进行逐位OR操作获得 签名档的主要思想是:如果一个词出现在文本块中,那么这个词的签名中所有为1的位置必然出现在文本块的掩码中 好处: 对短语搜索有改进42
  • 43. 签名档Signature file举例This is a text.A text has manywords. Words aremade from letters.Block 1Block 2Block 3Block 4000101110101100100101101TextText signatureh(text)=000101 h(many)=110000 h(words)=100100 h(made)=001100 h(letters)=100001Signature function43
  • 44. 顺序检索Sequential Searching给定一个长度为m的短模式P,以及一个长度为n的长文本T,在文本T中找出出现模式P的所有位置 布鲁特-福斯算法Brute Force (BF算法) Trying all possible positions 克鲁什-莫里斯-普拉特算法 Knuth-Morris-Pratt(KMP算法) Use Next[] array to reduce comparison times 博叶-摩尔系列算法 Boyer-Moore Family (BM算法) The check inside the window can proceed backwards 移位-或算法 Shift-Or44
  • 45. Brute-Force 算法abracabracadabraa b r a c a da b r a c a d a b r a 只是简单的找到文本中所有可能模式的位置,并对该位置进行验证 无需任何形式的预处理 存在O(n)个文本位置,验证每个位置所需时间为O(m),所需最长时间为 O(mn),平均时间为O(n)aaa ba45
  • 46. Knuth-Morris-Pratt 算法Next=0 0 0 0 1 0 1 0 0 0 0 4abracadabraabracabracadabraa b r a c a da b r a c a d a b r a 第一次采用线性的方法来处理最坏的情况,需要一个在文本上滑动的窗口 不像BF算法那样滑过文本的所有位置,而是通过重新利用先前的匹配信息来减少滑动的次数 对每个搜索串,计算 next[ ] 数组 如果第i个位置失配,可跳转到 i - next[i] -1 的位置46
  • 47. Shift-Or 算法基于位并行处理,利用了在一个计算机字内部进行位运算的内部并行性 使用位并行处理模拟非确定自动机操作,来检索文本中的模式 Tj: 第j个新的文本字符 D’ = (D <<1) | B[Tj], refer to MIR fig. 8.17 B[c] has the i-th bit set to zero if and only if pi=c D=dm…d1: 搜索状态, D 刚开始的时候置成全147
  • 48. Shift-Or 算法a b r a c a d a b r a0 1 1 0 1 0 1 0 1 1 0B[a]1 0 1 1 1 1 1 1 0 1 1B[b]1 1 0 1 1 1 1 1 1 0 1B[r]1 1 1 1 0 1 1 1 1 1 1B[c]1 1 1 1 1 1 0 1 1 1 1B[d]1 1 1 1 1 1 1 1 1 1 1B[*]D’ = (D <<1) | B[Tj]D= dm…d1当dm=0时表示发现匹配匹配模式字符串p输入字符串48
  • 49. 容错检索:容错字符串匹配问题定义:给定一个长度为m的匹配模式字符串P,一个长度为n的长文本T,最多允许的错误数为k,找出最多有k个错误的模式在文本中的所有位置 Dynamic programming Automaton and Bit-Parallelism Filtering49
  • 50. 动态编程Dynamic Programming计算矩阵 C[0..m, 0..n]. C[i,j] 代表匹配(Pattern) P1..i 到suffix T1..j最少的错误个数 C[0,j]=0 C[i,0]=i C[i,j]= if (Pi=Tj) then C[i-1, j-1] else 1+min(C[i-1,j], C[i,j-1],C[i-1,j-1]) 如果C[m,j]<=k则在文本的第j个位置发生匹配50
  • 51. 动态编程例子surgery00000000s10111111u21012222r32101223v43211233e54322123y65433222Search ‘survey’ in the text ‘surgery’ with two errors51
  • 52. 自动机算法不确定有限状态自动机NFA 确定状态自动机的迁移函数映射输入信元和状态到下一个状态。不确定状态自动机迁移函数也可映射null信元(不需要输入信元)和状态到下一个状态52
  • 53. NFA Examplesurvey1 errorno error2 errorssurveysurveyεεεεεεεεεεεεMatching of the pattern ‘survey’ with two errors. MatchingInsertionReplacementDeletionε53
  • 54. 过滤Filtering动机:减少动态编程所占用的区域 主要想法 假设允许k个错误 把匹配串分成k+1 个, 任何少于或等于k个错误匹配的字符串一定能与这k+1个匹配子串中的某一个完全匹配,否则输入的字符串一定包含大于k个错误54