第五章文本索引和搜索

1、第五章,:,文本索引和搜索,任飞亮,东北大学自然语言处理实验室,2010,大纲,?,?,?,?,?,索引和搜索的概念,倒排文件索引,后缀数组索引,签名文件索引,文本搜索技术,大纲,?,?,?,?,?,索引和搜索的概念,倒排文件索引,后缀数组索引,签名文件索引,文本搜索技术,应用索引的例子,?,?,?,检索的目的是为了在一大堆的信息中发,现自己感兴趣的信息,;,但是,当有了一大堆资料之后,并不能立即,开始搜索,.,为什么,?,图书馆实例,在检索前必须建立索引,!,索引的定义,?,?,?,所谓建立索引,是指将待搜索的信息进行一,定的,分析,并将分析的结果按照,一定的组织,方式存储,起来,通常是存储

2、在文件中,.,存储了分析结果的文件的集合就是所谓的,索引,.,准确定义,:,索引,（,Index,）,是一种,数据结构,，,其将关键词与包含该关键词的文档（或关,键词在文档中的位置）建立了一种映射关,系，以加快检索的速度。,文本搜索的概念,?,?,不使用任何索引技术，而快速的在给定,文本或文本集合中查找是否出现某一关,键词，这种技术通常被称为,单模式匹配,应用领域,?,信息过滤、检索结果后处理等,BF,KMP,BM,?,常用算法,?,?,?,大纲,?,?,?,?,?,索引和搜索的概念,倒排文件索引,后缀数组索引,签名文件索引,文本搜索技术,倒排索引主要内容,?,?,?,?,?,?,?,倒排索引

3、简介,倒排文件的使用,倒排文件的建立,倒排文件的维护,倒排文件的压缩,倒排文件的性能分析,词汇表的存取,倒排索引主要内容,?,?,?,?,?,?,?,倒排索引简介,倒排文件的使用,倒排文件的建立,倒排文件的维护,倒排文件的压缩,倒排文件的性能分析,词汇表的存取,倒排文件简介,?,倒排文件,(Inverted File),?,?,?,也称倒排索引，索引对象是文档或文档集合中,的,单词,等，用来存储这些单词在一个文档或者,一组文档中的,存储位置,，是对文档或文档集合,的一种最常用的索引机制,倒如,:,有些书往往在最后提供的索引,(,单词,页,码列表表,),就可以看成是一种倒排索引,.,即通过,一些

4、关键词,在全书中检索出与之相关的部分,;,这种思想也被应用于数据库技术中,即对数据,库中需要经常进行检索的域建立索引结构,从,而实现快速查询,.,在关系数据库上建索引,姓名,地址,哈尔滨工业大学,姓名索引,张三,张三,查询式,:,姓名,=,“,张三,”,?,如上图所示,对”姓名”字段使用便于查找的数,据结构,(,如排序数组、,B,树或散列等,),建立索引，,当查询某个名字时，就不需要从头至尾遍历整,个字段，而可以快速找到该姓名，从而查找出,与其对应的信息。,倒排文件组成,?,?,词汇表,(vocabulary)+,记录表,(posting list),词汇表,?,?,文档或文档集合中所包含的所

5、有,不同单词,的集合,占用的空间,V,=,cn,，,c,是常数，,n,是文档集合的大小，,是一个,0,到,1,之间的常数，一般在,0.4,到,0.6,之间,对于词汇表中的每一个单词在文档中出现的,位置,或者其出现的,文,档编号,构成的列表,占用的空间,P,=,cn,，其中,c,是常数，随着记录表中存储的信息丰富,程度而变化,记录表既可以存储文本中单词的编号位置，也可以指向单词首字,母的字符位置，还可以是其所在的文档编号，即可以根据不同的,应用需求，使用不同的寻址粒度,(addressing granularity),?,记录表,?,?,?,对单文档的倒排文件,对文档集合的倒排文件,倒排索引主要

6、内容,?,?,?,?,?,?,?,倒排索引简介,倒排文件的使用,倒排文件的建立,倒排文件的维护,倒排文件的压缩,倒排文件的性能分析,词汇表的存取,倒排文件的使用,?,三个步骤,?,词汇表检索,?,将出现在查询（,Query,）中的单词分离出来，并在词,汇表中进行检索。,?,记录表检索,?,检索出所有找到的单词对应的记录表。,对检索出的记录表进行后处理，以实现短语查询、相,邻查询或者布尔查询。,?,记录表操作,?,词汇表检索,?,?,规模相对较小的独立文件，全部调入内存,常用数据结构,?,树状结构，如：,B,树和,Trie,树,?,前缀查询和范围查询,检索速度快，但是不支持前缀查询和范围查询等,

7、?,散列,?,?,需要根据实际需求情况，决定采用什么样,的数据结构。,记录表操作,?,?,如果查询中仅包含一个单词，则在词汇,表中找到该单词，并取出其对应的记录,表即完成了检索操作,如果查询中包含多个单词，则需将各个,单词检索出的记录表进行合并,?,同步遍历记录表，实现合并过程,倒排索引主要内容,?,?,?,?,?,?,?,倒排索引简介,倒排文件的使用,倒排文件的建立,倒排文件的维护,倒排文件的压缩,倒排文件的性能分析,词汇表的存取,倒排文件的建立,?,?,建立倒排文件的,最关键问题,是由于需要,索引的文档数量过大，有可能导致不能,在内存中存储整个倒排文件。,根据索引文档的大小，介绍三种倒排文

8、,件的建立方法。,?,?,?,基于内存的方法,基于排序的方法,基于归并的方法,倒排文件的建立,?,?,建立倒排文件的,最关键问题,是由于需要,索引的文档数量过大，有可能导致不能,在内存中存储整个倒排文件。,根据索引文档的大小，介绍三种倒排文,件的建立方法。,?,?,?,基于内存的方法,基于排序的方法,基于归并的方法,基于内存的方法,输入：,文档集合,输出：,基于文档集合的倒排文件,算法：,(1),初始遍历文档集合。对于每一个单词,w,，统计包含该,单词的文档数,f,w,；,(2),在内存中建立长度为,w,词表,f,w,的数组，并且对于,每一个单词,w,，生成指向其记录表块首的指针,p,w,。,

9、(3),第二次遍历文档集合，对每个文档,d,中的每一个单词,w,，在,p,w,中追加文档,d,的序号，,p,w,后移。,基于内存的方法,?,核心思想是经过两次遍历,?,?,第一次遍历首先获得每个单词出现的文档的个数，,从而获得所需内存的大小；,第二次遍历充分利用内存的随机访问功能，快速更,新每个单词的记录表；,只要内存比最终生成的倒排文件（包括词汇表和记,录表）大一些，该算法是可行的；,可以很方便地扩展该方法，在记录表中增加更多的,信息，如单词的位置等；,?,优点：,?,?,倒排文件的建立,?,?,建立倒排文件的最关键问题是由于需要,索引的文档数量过大，有可能导致不能,在内存中存储整个倒排文件

10、。,根据索引文档的大小，介绍三种倒排文,件的建立方法。,?,?,?,基于内存的方法,基于排序的方法,基于归并的方法,基于排序的方法,?,基于内存方法的不足,?,从磁盘读取和分析文档的操作需要花费较多时间，,如果反复调用，必将成为倒排文件建立的一个瓶颈,方法一：存储分析好的文本。,?,?,解决方法,?,潜在的代价是将会带来大量的磁盘开销，有时甚至要花费,比第二步更多的时间。,该方法将用,单词，文档编号,二元组构成数组或文件，,从由原来的按照文档编号排序，变为由单词排序，然后产,生最终的倒排文件。,?,方法二：基于排序的方法；,?,基于排序的方法,?,通过使用多路归并算法，排序过程可以在硬盘上完成

11、,?,另外一个好处是不必在内存中存储整个词表，从而大大增加了在单台机器上索,引的数据量,倒排文件的建立,?,?,建立倒排文件的最关键问题是由于需要,索引的文档数量过大，有可能导致不能,在内存中存储整个倒排文件。,根据索引文档的大小，介绍三种倒排文,件的建立方法。,?,?,?,基于内存的方法,基于排序的方法,基于归并的方法,基于归并的方法,?,提出背景,?,?,?,随着文档集合的增加，将所有词汇表置于内,存中的花费也越来越大,必须一部分一部分地生成索引，其中每一部,分索引都可使用上面的方法生成；,最后，将各个子索引进行归并，形成最终的,索引。,基于归并的方法,输入：,文档集合,输出：,基于文档集

12、合的倒排文件,算法：,(1),初始生成一个基于内存的临时索引结构，其中词汇表和,记录表均使用动态数据结构存储，如动态数组，链表等。,(2),读取一个文档，并在其中出现的单词的记录表中，加入,文档编号。直到占用的内存大小超过一定的阈值。,(3),将生成的包括词汇表和其记录表的临时索引结构转存到,磁盘，并清空内存。,(4),如果所有文档处理完毕，则转到,(5),，否则转到,(1),。,(5),归并以上生成的子索引，生成单一索引。,基于归并的方法,?,优点：,?,?,适用于各种大小的文档集合，即使对于内存,不大的机器也同样有效和实用；,该方法仅需一次扫描和分析文档，效率较高。,倒排索引主要内容,?,

13、?,?,?,?,?,?,倒排索引简介,倒排文件的使用,倒排文件的建立,倒排文件的维护,倒排文件的压缩,倒排文件的性能分析,词汇表的存取,倒排文件的维护,?,维护倒排文件通常需要三种维护操作,?,?,插入、删除和更新文档或文档集合,通常的更新操作需要较高的代价,?,?,例如，要在存储了单词位置信息的倒排文件中进,行一篇文档的更新，即使该文档仅仅改动很小的,部分，文档中出现的大部分单词的记录表都需要,做出改动。,原因：单词的位置很可能发生变化，这就需要频,繁地读取和修改记录表，这种代价是相当高的。,?,因此，在维护倒排文件时，一般不进行更新,操作，而是使用删除,+,插入操作代替,插入操作的维护,?

14、,?,?,?,在已有的倒排文件中插入一篇文档相当于在该文档包含的单词所对,应的记录表后面插入此文档的编号或者每个单词的位置信息,对于一般的文当，这种插入需要调用获取记录表并在其末尾添加该,文档或者单词位置信息的操作多次，以目前的硬件水平，这种操作,需要较长的时间。,如果使用批量插入，效率将大大的提高,?,类似归并操作,首先为待插入的多个文档建立临时内存索引结构,然后一次性地将此索引结构插入到原索引中,;,?,在生成批的时候新插入的文档不能马上被检索，会造成索引内容,滞后的问题，可以通过对临时内存索引进行检索解决,除使用批量插入方法外,还可以在新文档中包含单词被用户检索的时,候进行该单词词表的更

15、新,或者使用后台进程在机器空闲的时候进行,插入操作,;,?,效率都不如批量插入效率高,删除操作,?,?,?,文档的删除操作与插入操作类似,其瓶颈也是记,录表从磁盘读取和写回的过程,;,也可使用批量删除的方法,为了保持删除的及时性,需要维护一张删除文件,列表,?,在检索时如果结果包含列表中的文件，则将其从结,果中删除,?,总之,在维护倒排文件的时候,无率是插入操作,还是删除操作,为了提高效率,必须想办法减少,读写磁盘的操作,即提高磁盘,I/O,的效率,倒排索引主要内容,?,?,?,?,?,?,?,倒排索引简介,倒排文件的使用,倒排文件的建立,倒排文件的维护,倒排文件的压缩,倒排文件的性能分析,词

16、汇表的存取,倒排文件的压缩,?,优点,?,?,减少内存和磁盘的空间占用,提高磁盘的吞吐量，提高索引维护和查找的效率,有损压缩,?,?,?,压缩分类,?,去停用词、词干提取等技术,使用这些技术会损失一些原文中的信息；,在压缩倒排文件的同时，其原始信息完全被保留，不会缺损。,分,词汇表,的压缩和,记录表,的压缩,?,无损压缩,?,?,词汇表的压缩,?,?,在检索的时候，需要经常查询词汇表，,在理想情况下，应将词汇表始终置于内,存之中。,实际情况：,?,?,?,随着文档数的增多，词汇表也将逐渐增大；,存在一些对内存使用有限制的应用,必须对词汇表进行压缩；,?,压缩常用方法：,?,?,使用一个长字符串

17、连续存储词汇表,见下页图,词汇表的压缩,?,使用长字符串连续存储单词表,?,?,这样的存储方式紧凑，且不会出现溢出问题；,通过该种简单的压缩方式，可以很容易地将词汇表压缩,为原来大小的,50%,左右,记录表的压缩,?,文档和单词的位置使用,16,位或,32,位整数表示,?,16,位太小，,32,位太大，浪费空间,?,解决方法：仅记录相邻文档编号或词位置之间,的差异,Word positions,database,D,345, 25, 34, 98, 120,D,348, 37, 71, 85,345, 25, 9, 64, 22,3, 37, 34, 14,database,?,用比较少的字节

18、表示编号的相对变化,记录表的压缩,(2),?,整数的定长表示不是特别的节省空间,?,?,对于常用词相对变化不多，使用,16,位编码，,浪费空间,对于非常用词，有可能仅存在于少数的文档,之中，,16,位表示会溢出,基本原理,?,?,?,解决方案：变长整数表示,?,使用较少位数表示较小，出现次数较多的整数,使用较多位数表示较大，出现次数较少的整数,倒排表压缩总结,?,优点：,?,?,?,?,1,、降代了索引在内存和磁盘中占用的空间，,经过适当的压缩，索引的大小可以降为原始文,档的,25%,左右；,2,、由于索引被压缩，提高了磁盘的传输效率，,使得查询的速度加快；,3,、由于磁盘传输效率的提高，使得

19、索引的构,造和维护的效率也得到提高；,4,、另外一个隐含的好处是，这样提高了倒排,文件的缓存能力；进而提高了检索的速度,倒排表压缩总结,?,负面影响：,?,?,1,、在搜索时必须花时间对压缩的数据进行解码,;,2,、在维护时,特别是进行删除操作时,由于某些文,档被删除,不得不对剩余的文档编号进行重新编,码,;,?,总体上：利大于弊,倒排索引主要内容,?,?,?,?,?,?,?,倒排索引简介,倒排文件的使用,倒排文件的建立,倒排文件的维护,倒排文件的压缩,倒排文件的性能分析,词汇表的存取,倒排文件性能分析,?,可以证明,使用倒排文件,检索查询的开销与文,档集合大小成,次线性关系,其时间复杂性,?

20、,O(n,a,),，其中,0 ,a, 1,，与查询有关,一般在,0.40.8,之间,?,?,?,在实际应用中,倒排文件的时间和空间复杂性接,近,O(n,0.85,),在使用压缩技术之后，在时间复杂性损失不多,的条件下，空间的复杂性会进一步降低到原来,的,25%,左右,-,其它索引方法很难实现,倒排索引主要内容,?,?,?,?,?,?,?,倒排索引简介,倒排文件的使用,倒排文件的建立,倒排文件的维护,倒排文件的压缩,倒排文件的性能分析,词汇表的存取,词汇表的存取,?,?,?,词汇表的存取是实现倒排文件查询的第一个步,骤,需要非常高的存取效率,高效的词汇表存取方法也被应用于信息检索的,其他步骤或者

21、其他信息技术应用领域,要实现高效的词汇表搜索,往往需要设计特殊的,数据结构,?,?,排序数组,树状结构,?,都是基于字符串比较的方法,需,要事先将待查找的字符串排序,B,树，,Trie,树,?,散列,1,、不需要预先排序、检索速度快,2,、很难处理前缀查找,(,如查找以“沈阳“开始的,词,),、区域查找,(,如查找所有“技术”到“检索”之,间的单词,),排序数组,?,?,?,?,?,最简单的词汇表搜索方法,是由一系列元素组成的数组，其中的元素一般,包括三个域：关键词、记录表的大小以及指向,其记录表的指针,数组中的元素根据关键词排序,可以采用二分查找的方法，在,O,(log(,n,),的时,间复

22、杂性内，查找给定的关键词,缺点,?,?,维护代价较高，无论插入还是删除，都需要移动较,多的元素,可能造成内存不足,引入树状结构,!,B,树,?,B,树的定义：,B,树是一种平衡的多叉树，一,棵,m,阶的,B,树满足下列条件：,树中每个节点至多有,m,个孩子；,除根节点和叶子节点外，其它每个节点至少,有,m,/2,个孩子；,若根节点不是叶子节点，则至少有,2,个孩子；,所有叶子节点都出现在同一层，叶子节点不,包含任何关键字信息；,有,k,个孩子的非终端节点恰好包含有,k,-1,个关,键词。,在,B,树中，每个节点中的关键词从小到大排列，并且当该结点的孩子是非叶,子节点时，该,k-1,个关键词正好

23、是,k,个孩子包含的关键字的值域的划分。,B,树示例,?,?,B,树中的一个包含,n,个关键词、,n+1,个指针的节点的一般,形式为,(P,0,K,1,P,1, K,2,P,2,K,n,P,n,),其中，,K,i,为关键词，,K,1,K,2,K,n,P,i,是指向包括,K,i,到,K,i+1,之间的关键词的子树的指针,B,树操作,?,查找,?,?,在每个节点进行沿着指针查找节点和在节点内的关键,词中查找交叉的过程,从根结点开始，在节点包含的关键词中查找给定的关,键词，找到则查找成功，否则确定给定关键词可能在,哪个子树，重复上面的操作，直到查找成功或者指针,为空为止,如何查找,20,？,如何查找

24、,21,？,如何查找,22,？,B,树操作,?,插入,?,在恰当的叶子节点中添加关键词，如果该节点中关键词超过,m,-1,个，要把这个节点分裂为两个，并把中间的一个关键词拿出来,插到节点的父节点里去。如果父节点也是满的，就需要再分裂，,再往上插，以此类推，直到根节点,如何插入,22,？,如何插入,38,？,B,树操作,?,删除,?,删除操作与插入操作类似，但要稍微复杂些。从一个,节点中删除关键词时，需要重新安排一些节点，防止,因删除操作而导致树的结构违反,B,树的性质,B,树的扩展：,B+,、,B*,树等,Trie,树,?,?,?,?,?,又称作前缀树，其名字来源于英文词,reTrieval(

25、,检索,),当关键词的长度变化较大时，,Trie,树是一种特别有效的查找数据结构；,另外，,Trie,树还适合用于查找单词前缀，如果找所有以”,comput,”,开头的词，,如”,computing,”,、”,computer,”,等,Trie,树的每一层分支不是靠整个单词的值来确定，而是由单词中的一个字符,来确定,例如存储：,information,、,retrieval,、,system,、,introduction,的,Trie,树,Trie,树包括两种类型的节点：元素节点,和分支节点。,元素节点包含整个单词，在图中用表,示，分支节点用表示。,如要查找单词”,information,”,

26、，则顺次查,找字母”,i,”,、”,n,”,和”,f,”,，进入元素节,点”,information,”,，它与查询单,词”,information,”,相同，故查找成功；,如要查找”,inference,”,，也会进入元素,节点”,information,”,，但在比较两个单词,的时候会发现它们不同，故查找失败。,?,?,?,?,Patricia,树,?,?,Trie,树在最坏的情况下搜索的时间代价为,O(l),其中,l,是,Trie,树的层数,;,Trie,树的改进,?,?,压缩一元节点,(,即只有一个子节点的节点,),，提高空间利用率,?,Patricia(Practical Algor

27、ithm To Retrieve Information Coded in,Alphanumeric),树,Patricia,树,?,除了不含有一元节点外，,Patricia,树与,Trie,树的不同之,处还在于其分支节点内包含待比较的字节编号。,?,?,如要查询单,词”,information,”,Patri,cia,树只需查找第一个,字母”,i,”,，然后查找第,3,个字母”,r,”,即可进入,元素节,点”,information,”,.,与,Trie,树查找相比,减少,了一次对字母,n,的判断,一般情况下，,Patricia,树的性能要优于,Trie,树,大纲,?,?,?,?,?,索引和

28、搜索的概念,倒排文件索引,后缀数组索引,签名文件索引,文本搜索技术,后缀数组,?,在倒排文档中，文本被看作是由单词组成的序列,?,限,制了倒排文件的应用,?,?,情况,1,：词组查询在使用倒排文件查询时就比较困难，因为不,但需要记录每个单词在文档中的位置，还要在合并时判断其,是否相邻并构成词组；,情况,2,：在某些应用中，如基因数据库，不存在词的概念。,?,?,?,?,解决方案：使用,后缀数组,在,后缀数组,中，可以将文本看作是一个长的字符串，,文本中的每个位置都被认为是文本的一个后缀，即一,个从当前文本位置到文本末尾的字符串。,索引的位置可以是每个字符的位置、单词的位置或者,汉字的位置等。,

29、后缀数组,(suffix array),就是对文本中的所有后缀按照,词典序存放每个后缀对应的起始位置的一个列表,后缀数组的构造,0,这,2,是,4,一,6,本,8,关,10,于,12,信,1,4,息,16,检,18,索,20,的,22,教,24,材,26,。,28,介,30,绍,32,了,34,检,36,索,38,的,40,基,42,本,44,技,46,术,48,。,原始文本，按字的顺序位置索引,首先截取每个后缀的前,n,个字节，作为类似倒排文件中的“词汇表”,(,此处,n=4),0,2,12,16,22,34,44,这是,是一,信息,检索,教材,检索,技术,文本中的部分后缀，按位置索引,44

30、,16,34,22,2,12,0,技术,检索,检索,教材,是一,信息,这是,相同的部分后缀，按字典序索引,后缀数组的使用,?,在使用后缀数组进行检索的时候，将每个查询同样截,取前,n,个字节，并于索引中进行查找,?,?,如果没有找到，则表明不包含所需查询,如果查找成功，则需要在相应的文本位置上，进行进一步的,字符串比较，以确定文本中是否包含查询,查找“信息检索”，首先截取,4,个字节“信息”，并于后缀数,组中查找到了位置,12,，接着在原文中的,12,号位置，找到“信,息检索”字符串，则查找成功；,查找“信息过滤”，则原文中的,12,号位置不能找到“信息过,滤”字符串，则查找失败；,更一般的例

31、子，如果输入的查询为“数据库”，在索引结构,中不能找到“数据”，则查找直接失败返回；,44,16,34,22,2,12,0,?,实例,?,?,?,技术,检索,检索,教材,是一,信息,这是,后缀数组的分析,?,?,?,?,?,?,对于需要大数据量的检索问题，后缀数组并不适用,因为构造出的后缀数组需要占用大量的空间，通常是原,文本的,1.7,倍,和倒排文档相比，后缀数组里面储存了较多的重复信息,同时，由于每个后缀位置的编号不能存储相对位置的变,化，所以很难被压缩，需要较多的存储空间；,后缀数组的另外一个缺点是不容易对检索结果进行排序，,因为计算查询单词的词频比较耗时；,实际上,后缀数组的大部分功能

32、可以通过倒排文档来实现,!,?,例如可以倒排索引文本中的二字串或者三字串，从而提高召回率,大纲,?,?,?,?,?,索引和搜索的概念,倒排文件索引,后缀数组索引,签名文件索引,文本搜索技术,签名文件,?,?,?,?,签名文件,(signature file),是基于散列技,术的面向单词的索引结构,索引占用的空间大约为原始文档集的,3040%,在检索时需要顺序比较，适用于小规模,的文本,在大多数应用中，其性能不如倒排文件,词的,Signatures,?,?,一个单词的“签名”是一个,位向量,由,F,位组成,其中有,m,位,置,1;,如下图给出了一段文本，以及文本中部分单词的“签名”,示例，其中,

33、F=12,m=4;,这,是,一本,关于,信息,检索,的,教材,。,介绍,了,检索,的,基本,技术,。,文本,单词,技术,教材,检索,信息,词“签名”,001 000 110 010,000 010 101 001,000 000 011 110,101 000 100 001,词,Signature,的生成算法,输入：词,W,，参数,F,和,m,输出：词,W,的,F,位“签名”,S,算法：,(1),将,W,转换为,ASCII,值，然后转换为,32,位整数,i,例如：,free,=,66726565,(hex),(2),初始化：,a),S,的,F,位全置,0,;,b),srandom(i);,/

34、,初始化随机种子,c),j,=,0,;,(3),while,(j,m),p,=,random();,/,生成,32,位随机数,p,=,p,mod,F;,/,映射到,0,和,F-1,之间,if,(Sp,=,0),/,确保,m,位置,1,Sp,=,1;,j+;,(4),结束，返回,S,签名文件,?,?,?,?,如果仅对每一个单词生成相应的“签名”，则在查询的,时候，需要逐个比较，非常浪费时间。,因此，通常把文本分成若干块，每个块有多个单词，块,的“签名”是通过块中单词的“签名”的按位“或”操,作得到的,因此，所谓的签名文件，就是文本中块“签名”的序列；,下图给出了一段文本以及其对应的签名文件,一段

35、文本对应的块签名,块,1,块,2,块,3,块,4,这,是,一本,关于,信息,检索,的,教材,。,介绍,了,检索,的,基本,技术,。,文本,000 000 000 000 101 010 111 111 000 000 011 110 001 000 110 010,签名文件,单词,技术,教材,检索,信息,词“签,名”,001 000 110 010,000 010 101 001,000 000 011 110,101 000 100 001,签名文件的使用和维护,?,?,?,使用签名文件检索单个单词的过程是，首先对这个单,词使用相同的算法生成其“签名”,S,，并与所有文本块,的签名,S,i,

36、依次比较,即计算,S,签名文件由于组织简单，因此较容易生成，维护费用,较小，它是在倒排文件和全文扫描之间做了空间和时,间的平衡，适合于小文本集合和查询频率较低的系统,签名文件的主要缺点是：,?,?,?,索引占用的空间和检索的时间复杂性与原始文档集成线性关,系。,误检的发生数也基本和文本集合中的文本个数成正比。,即使对于比较短的查询，也需要大量的磁盘访问操作。,大纲,?,?,?,?,?,索引和搜索的概念,倒排文件索引,后缀数组索引,签名文件索引,文本搜索技术,文本搜索技术,?,?,前面的文本检索技术需要事先建立索引,然后才能,快速查找,.,在某些应用中,这种建立索引的方法并不适用,?,?,?,情

37、况,1:,在签名文件的候选块确认过程中,就需要在块中查,找某一查询是否真正存在,;,情况,2:,在文本过滤技术中,一般文本仅需查询一次,这就,没必要建立索引,;,情况,3:,在搜索引擎结果后处理中,需要对搜索结果中包含,的查询关键词进行加亮显示,也需要用到文本搜索技术,;,?,快速的文本搜索非常必要,!,文本搜索技术,?,精确的字符串匹配问题可以如下描述,:,?,结定一个长度为,m,的模式,P,(,p1p2,pm,),，以及一个,长度为,n,的长文本,T,(,t1t2,tn,),，其中,n,m,。在文本,T,中找出模式,P,出现的位置。,?,三种常用的精确匹配算法,?,?,?,BF,算法,KM

38、P,算法,BM,算法,文本搜索技术,?,精确的字符串匹配问题可以如下描述,:,?,结定一个长度为,m,的模式,P,(,p1p2,pm,),，以及一个,长度为,n,的长文本,T,(,t1t2,tn,),，其中,n,m,。在文本,T,中找出模式,P,出现的位置。,?,三种常用的精确匹配算法,?,?,?,BF,算法,KMP,算法,BM,算法,BF,算法,?,?,?,BF,算法是,Brute-Force(,蛮力,),算法的简称,是一种简单、直接、容易实现的字符串,匹配算法,基本思想：,?,?,?,将模式,P,和文本,T,中的,m,个字符的子串,t,k,t,k+1,t,k+m-1,进行匹配，,1kn,。

39、,若模式和子串匹配，则返回匹配的位置，,若模式和子串不匹配，则从,t,k+1,位置开始新,的考察,BF,算法,输入：,文本,T,和模式,P,输出：,文本,T,中如果包含模式,P,返回匹配位置，否则返回匹配不成功,算法：,i = 1; j = 1;,while (i m and j n) ,if (pi = tj) ,i = i + 1; j = j + 1;, else ,j = j -,i + 2; i = 1;,if (i m),return,匹配位置,j;,else,return,“匹配不成功”,;,BF,算法分析,?,?,?,?,在,BF,算法中，可以更改循环条件为,j,n-m+1,使

40、得循环,可以更早地终止；,因为存在,O(n),个文本位置，在最坏的情况下，验证每,个位置需要花费的时间为,O(m),所以,BF,算法的最长时,间为,O(mn),BF,算法的平均时间为,O(n),，因为对于一个随机文本，,一般在进行,O(l),次比较之后，就可以发现错误的匹配。,BF,算法无需进行任何形式的预处理，实现简单，被大,多数程序设计语言所采用,?,如,C,语言中的字符串查找函数,strstr(),使用的就是,BF,算法,?,BF,算法的时间复杂性与其他算法比较还是比较高的，,在对效率要求较高的系统中，应该避免大量使用,文本搜索技术,?,精确的字符串匹配问题可以如下描述,:,?,结定一个

41、长度为,m,的模式,P,(,p1p2,pm,),，以及一个,长度为,n,的长文本,T,(,t1t2,tn,),，其中,n,m,。在文本,T,中找出模式,P,出现的位置。,?,三种常用的精确匹配算法,?,?,?,BF,算法,KMP,算法,BM,算法,KMP,算法,?,?,?,D.E.Knuth,、,J.H.Morris,和,V,.R.Pratt,同时发现的改进的模式匹配算法,该算法是第一个可以在,O(n+m),的时间内完成串模式匹配的算法，,但平均来说，它的效率并不比,BF,算法快很多。,基本思想,?,?,每当匹配过程中出现字符串比较不等时，不像,BF,算法那样仅将模式向,右“滑动”一个位置，而

42、是利用已经得到的“部分匹配”结果将模式,向右“滑动”尽可能远的一段距离后，继续进行比较。,可以避免对那些能够推断出不匹配的位置进行徒劳的操作,KMP,算法,?,KMP,算法原则,?,?,从,匹配成功,的,子模式,中找出“能够相互匹配,的,最长的前缀,和,后缀,”,在使用,KMP,算法进行模式匹配时，需要根据模,式事先构造一个,shift,跳转表，用来决定在某,个位置匹配失败时应该移动多少个字符,?,Shift,表的构造方法,?,如果当前不匹配的位置为,j,重复字串的长度为,k,则跳过的字符个数为,j-k-1,KMP,算法的,shift,表,?,模式,P=,“,abcabcacab,”的,shift,表,如果当前不匹配的,位置为,j,重复字串,的长度为,k,则跳过,的字符个数为,j-k-1,?,?,KMP,算法的,shift,表可以在,O(m),的时间复杂,度下，通过对关键词的分析而获得,m,是模,式的长度,KMP,算法花费,O(m+n),的时间来解决模式匹,配问题,文本搜索技术,?,精确的字符串匹配问题可以如下描述,:,?,结定一个长度为,m,的模式,P,(,p1p2,pm,),，以及一个,长度为,n,的长文本,T,(,t1t2,tn,),，其中,n,