数据挖掘以及搜索引擎经典pptchap6.ppt

文件索引建立,为什么需要索引,对海量数据，全文存储在检索上太耗时，无法再内存中进行操作。 索引可以快速的对包含关键词的文档进行定位，查询时间可以和文档长度无关，只和查询词长度有关。,和数据库索引的区别,数据库只索引某几项，而信息检索需要都索引。因为数据库的查询句是固定的，而信息检索是变化的。 索引是基于未来可能查询的“项”（terms）. 来自文本中的所有词。,Indexes: 实现方法,有代表性的方法 Bitmaps （位图） Signature files （签字文件） Inverted files （倒排文件） 索引要素 词 :Dictionary (lexicon) 元数据 document ids word positions,No positional data indexed,Indexes: Bitmaps,本质上是文档的向量表示，若文档包含某一特征词，则对应的位置上标记1，否则为0.,Signature Files,对每个项，给出长度为s的向量（hash函数值） 把一篇文档中的所有词的向量进行OR操作，得到的向量为文档的签名。 长文档肯定成为问题，解决的方法是分块签字。,Signature File Example,Signature File Example,Indexes: Signature Files,查询方法 若查询词可以在文档中找到签名对应的1,则认为文档中包含这个项。,Indexes: 倒排文档,目前最常用的索引方法 起源为书中术语检索的方法 Eg. Computer page 8, line 12,Inverted Files,Inverted Files,Word-Level Inverted File,倒排文档的搜索算法,Find query elements (terms) in the lexicon Retrieve postings for each lexicon entry Manipulate postings according to the retrieval model,Word-Level Inverted File,Query: 1.porridge & pot (BOOL) 2.“porridge pot” (BOOL) 3. porridge pot (VSM),Lexicon词汇表,Posting 记录表,Answer,倒排文件的建立,采用合适的数据结构，建立检索词汇表。对英文主要采用被称为trie的数据结构。 1) 前面给出的词汇和记录表在一起的形式。但可能词汇表本身很大 2) 词汇表和记录表分开，用指针给出对应关系。 3）词汇表和记录表分开，但没有直接连接指针，而是中间用一个数据结构把两者联系起来。,词汇表结构,基于 Heaps 的定理，可能词汇表的尺寸很大. 常采用两种方法存放 Hash table O(1) 查找时间和接近常数时间的处理冲突。 扩展比较麻烦 B-Tree 可以利用磁盘存储空间.查找时间快。 O(log n) 的查找时间，易于扩展。 Trie,In-memory Inversion Algorithm,Create an empty lexicon For each document d in the collection, Read document, parse into terms For each indexing term t, fd,t = frequency of t in d If t is not in lexicon, insert it Append to postings list for t Output each postings list into inverted file For each term, start new file entry Append each to the entry Compress entry Write entry out to file.,长文档的处理,分成若干块(chunk)处理 利用归并算法形成最后的索引,Idea 1: Partition the text,Invert a chunk of the text at a time Then, merge each sub-indexes into one complete index,Trie,In IR we need to record the position that a word appear in a document and the time it appears. We hope we can check if a word w in a document in O(|w|) time regardness how many words in the document.,trie,令S是取自的n个串的集合，d = | |,满足S中任意串不是另一串的前缀。S的一个标准trie是一有序树，满足： 除根外，每个定点的标记是中的字符 T中的内部顶点的排序按的顺序 T有n个叶子顶点，从根到叶子的路径的顶点标记对应S中的一个串。,n=8,The searching algorithm,Starting at the root, follow the path that matches the chars of the word in a trie. If a leaf node is reached, success else there is no the word in the trie,Record the position of a word in a trie,A compressed trie,s 下标 数组的起终下标,s,e,e,b,e,ar,ll,id,u,y,ll,hear,ll,to,ck,p,中文的trie怎么做,拼音 ？ 汉字组合 汉语词典 和中文的分词有关？,Summary,Common implementations of indexes Bitmap, signature file, inverted file Common index components Lexicon & postings Inverted Search Algorithm Inversion algorithm Inverted file access optimizations co