信息检索 第04章 文本搜索技术专业课课件

信息检索

第04章文本搜索技术软件学院教研室陈鄞信息检索系统的体系结构文本数据库数据库管理建索引索引查询处理搜索排序排序后的文档用户反馈文本处理用户界面检出的文档用户需求文本提问逻辑视图倒排文档引言文本搜索方法全文扫描基于索引的文本搜索什么是索引？索引是一种数据结构，它在关键词与包含关键词的文档之间建立了一种映射关系，从而加快检索的速度。建立索引的目的加快检索速度常用的索引技术倒排文档后缀数组签名文件本章内容4.1倒排文档4.2后缀数组4.3签名文件4.4全文扫描4.1倒排文档4.1.1什么是倒排文档4.1.2倒排文档的建立4.1.3倒排文档的维护4.1.4倒排文档的压缩4.1.5倒排文档性能分析4.1.1什么是倒排文档文档编号题目关键词1…知识管理，管理信息系统，企业信息化2…知识管理，知识链，学习型组织，知识创新3…知识管理，知识创新，知识共享4…知识管理，学习型组织5…技术创新，知识空间，知识创新6…企业信息化，信息结构，竞争情报7…知识管理，知识创新，竞争情报8…管理信息系统，企业文化9…管理信息系统，竞争情报10…知识管理，企业文化，管理创新关键词目长文档集合1管理创新1102管理信息系统31;8;93技术创新154竞争情报36;7;95企业文化28;106企业信息化21;67信息结构168学习型组织22;49知识创新42;3;5;710知识管理61;2;3;4;7;1011知识共享1312知识空间1513知识链12建立索引以记录集合的某一属性作为索引对象，记录该属性的每一个属性值在记录集合中的出现位置倒排文档的定义倒排文档是从关键词快速查询到文档的索引结构。文档正常表示为关键词的集合，建立倒排文档是把每个关键词表示为其所在文档的集合，这个过程称为inversion，即倒排。有些书在最后提供的索引（单词—页码列表对），就可以看成是一种倒排文档倒排文档的结构倒排文档组成词项词典（dictionary）索引项（词项）组成的集合倒排记录表（PostingList）索引项在文档集合中的位置组成的集合architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3词项词典全体倒排记录表Q=term1,term2,term3,...在实际应用中，记录表的组织形式和存储的内容是多种多样的可以在一个文件内部建立倒排文档文本倒排文档12345678910111213141516这是一本关于信息检索的教材。介绍了检索的基本技术。…技术教材检索信息…15,…8,…6,12,…5,……词汇表记录表保存句子位置保存段落、句子和词的位置databasefilesystems...D345,25D348,37D350,8D123,5D128,25D345,25文档D350第8句databasefilesystems...D345,2,3,5D348,37,5,9D350,8,12,1D123,5,4,3D128,25,1,12D345,2,3,6文档D350第8段第12句第1个词在记录表中存储关键词所在的文档编号段落编号句子编号词编号所在的特殊单元（如标题、小标题）保存位置序号的目的：支持上下文条件查询短语查询例如：搜索“StanfordUniversity”TheinventorStanfordOvshinskyneverwenttouniversity.近邻查询“database”和“systems”之间不能间隔超过3个词“database”和“architecture”在同一个句子（段落）里databaseD1,2,97,104D3,43systemD1,5D3,44“database”在D1中出现的词序号在记录表中存储指针在记录表中存储统计信息频率权重databasefilesystems...D345,10D348,20D350,1D123,82D128,8D345,12在D345中，“systems”

比“database”重要1.2倍总结——记录表中的内容位置信息形式上：序号或指针内容上：文档、段落、句子、词附加信息特殊位置信息：所在单元（标题、小标题）统计信息同义词扩展词汇表同义词对于提高检索的召回率很有意义同义词可以通过指针指向同一个记录表...databasedatabasessystemsD345,2,3,5D348,37,5,9D350,8,12,1D123,5,4,3D128,25,1,12D345,2,3,6dataset4.1.2词典的确定词条化（

Tokenizing）词条归一化(TokenNormalization)去除停用词某些情况下，一些常见词在文档和用户需求进行匹配时价值并不大，需要彻底从词汇表中去除。这些词称为停用词（stopword）预处理对倒排索引的影响例：Reuters-RCV1语料规模：1GB文本数据内容：1996年8月20日到1997年8月19日一年间的路透社新闻180对Reuters-RCV1进行预处理前后词项、无位置信息倒排记录及词条的数目4.1.3倒排文档的建立DocidTermpaperreportnovelnovel……1111…reporthuman……22…humannovelnovelpaperreportreport……211112…排序归并human2,1novel1,2paper1,1report1,12,11112在此记录文档频率在此记录词项频率基于排序的索引构建方法对于小规模文档集来说，上述过程均可在内存中完成在大规模文档条件下需要引入二级存储介质时的索引方法基于块排序的索引方法分布式索引构建方法为使索引构建过程效率更高，将词项用其ID来代替，每个词项的ID是唯一的序列编号①基于块排序的索引方法BSBI(blockedsort-basedindexing)第1步，将文档集分割成几个大小相等的部分；第2步，将每个部分的词项ID—文档ID对排序；第3步，将中间产生的临时排序结果存放到磁盘中；第4步，将所有的中间文件合并成最终的索引。BSBINDEXCONSTRUCTION()1n←02while(alldocumentshavenotbeenprocessed)3don←n+14

block←PARSENEXTBLOCK()5 BSBI-INVERT(block)6 WRITEBLOCKTODISK(block,fn)7MERGEBLOCKS(f1,...,fn;fmerged)MERGEBLOCKS(f1,...,fn;fmerged)合并时，同时打开所有块对应的文件，内存中维护为n个块准备的读缓冲区和一个为最终合并索引准备的写缓冲区每次迭代中，利用优先级队列或者类似的数据结构选择最小的未处理词项ID进行处理。读入该词项的各个倒排记录表并合并，合并结果写回磁盘中②内存式单遍扫描索引构建方法SPIMI(single-passin-memoryindexing)SPIMI使用词项而不是其ID，它将每个块的词典写入磁盘，对于下一个块则重新采用新的词典只要硬盘空间足够大，就能够索引任何大小的文档集性能分析优点：由于不需要排序操作，因此处理的速度更快由于保留了倒排记录表对词项的归属关系，因此能够节省内存，词项的ID也不需要保存这样，每次单独的SPIMI-Invert调用能够够处理的块大小可以非常大，整个倒排索引的构建过程也因此会非常高效。缺点每次当空间放满的时候，就会申请加倍的空间。这意味着一些空间被浪费正好抵消了不用保存词项ID所省下的空间。总体来说，SPIMI所需的内存空间仍然比BSBI少③

分布式索引构建方法实际当中的文档集通常很大，在单台计算机上很难高效的构建索引Web搜索引擎通常需要大规模计算机集群，使用分布式算法来构建索引，其索引结果也是分布式的，它往往按照词项或文档进行分割后分布在多台计算机上MapReduceMapReduce是一个通用的分布式计算框架，它面向大规模计算机集群而设计集群的关键是，利用价格低廉的日用计算机（称为节点node）来解决大型的计算问题。这些计算机都采用通用的标准部件（处理器、内存和磁盘），而不像超级计算机那样采用专用硬件一般来说，MapReduce会通过键-值对（key-valuepair）的转换处理，将一个大型的计算问题转化成较小的子问题在索引构建中，键-值对的形式就是(词项ID,文档ID)Map阶段将输入的数据片映射成键-值对。在索引构建中，该阶段对应于BSBI和SPIMI算法中的文档分析任务，因此也将执行map过程的机器称为分析器（parser）Reduce阶段将同一键（词项ID）的所有值（文档ID）集中存储在索引构建中，对应于倒排任务，因此也将执行reduce过程的机器称为倒排器（inverter）使用MapReduce进行分布式索引构建的例子4.1.4倒排文档的维护插入文档删除文档更新文档①插入文档方法调用该文档包含的关键词所对应的记录表，在后面插入关键词在该文档中的位置信息，该表再放回倒排文档中最坏的情况文档包含n个关键词，并且每个关键词都不重复，插入时需要调用并更新n个记录表批量插入如果每插入一个文档，都要调用几十次或几百次记录表，时间上开销很大事实上，倒排文档中文档的插入工作都是成批进行的首先为待插入的多个文档建立辅助索引（临时内存索引）检索时，同时遍历主索引和临时内存索引，并将结果合并当辅助索引变得很大时，就将它合并到主索引中批量插入为什么能提高效率？一个词可能出现在多个文档中批处理过程从倒排文档中调出一个记录表，可插入若干记录项批量插入需要注意的问题索引内容滞后问题对临时内存索引进行检索使用后台进程在机器空闲时进行插入操作批量插入的规模批不能太小，否则很少会出现多个文件包含一个词的情况批不能太大，否则批的生成本身开销也很大设计一个新的插入操作时，必须考虑主存和临时存储器中可利用的空间大小倒排文档的插入开销依赖于更新的频度，对索引的即时性的要求，以及系统的工作负荷能力对于图书馆应用来说，插入操作不是问题对新闻和互联网方面的应用而言，就是一个问题②删除文档前向索引（ForwardIndex）步骤找到将要被删除的文档ID从前向索引中获得该文档中包含的词根据该文档中的词定位倒排文档中的记录表，并在这些记录表中将该文档ID删除DocIDword1,word2,….批量删除保持删除的及时性维护一张“删除文件列表”，在检索过程中，忽略那些被登记在表中的文档ID使用后台进程在机器空闲时进行删除操作③更新文档代价较高一般不进行更新操作，而是使用“删除+插入”操作代替对于数据量不大的应用，甚至可以考虑重建索引4.1.5基于倒排文档的检索布尔模型中的检索VSM中的检索4.1.5.1布尔模型中基于倒排文档的检索例：BrutusANDCalpurnia该并发扫描算法要求倒排记录表必须按照全局统一的指标进行排序布尔模型中的查询优化查询优化(queryoptimization)指的是如何通过组织查询的处理过程来使处理工作量最小对布尔查询进行优化要考虑的一个主要因素是倒排记录表的访问顺序a

AND

b

AND

c按照词项的文档频率（也就是倒排记录表的长度）从小到大依次进行处理(maddingORcrowd)AND(ignobleORstrife)AND(killedORslain)保守地估计出每个OR操作后的结果大小，然后按照结果从小到大的顺序执行AND操作基于跳表的倒排记录表快速合并算法例

跳表指针个数多少跳跃的步长短长跳跃的可能性大小指针比较次数多少存储空间多少4.1.5.2倒排记录表在VSM中的应用基于倒排文档的向量相似度计算以文档为单位的评分方法（document-at-a-time）以词项为单位的评分方法（term-at-a-time）以文档为单位的评分方法给定查询q，并发扫描q中各词项的倒排记录表，得到并集A对A中的文档进行余弦相似度计算该算法要求倒排记录表必须按照全局统一的指标进行排序以词项为单位的评分方法算法要点根据每个t的贡献对文档得分进行累加数组Scores的N个元素也称为累加器（accumulator）非精确返回前K篇文档的方法精确返回前K篇得分最高文档的主要计算开销源于大量文档都参与的余弦相似度计算非精确返回前K篇得分最高文档基本思想：只集中关注那些可能具有很高最终得分的文档，减少参与计算的文档数目，产生“可能”排名最高的K篇文档的方法①索引去除技术只考虑那些词项的idf值超过一定阈值的文档只考虑包含多个查询词项（一个特例是包含全部查询词项）的文档存在的问题：有可能最后的候选结果文档数目少于K个例：q=“risinginterestrates”解决办法：层次型索引（tieredindex）risinginterestrates②胜者表（championlist）基本思路对于词典中的每个词项t，预先计算出倒排记录表中tf值最高的r个文档构成t的胜者表给定查询q，对查询q中所有词项的胜者表求并集，得到集合A。只对A中的文档进行余弦相似度计算如果胜者表按照全局统一的指标进行排序（如文档ID），既可以采用以文档为单位的评分方法，并发扫描查询q中所有词项的胜者表，也可以采用以词项为单位的评分方法如果胜者表按照tf值降序排列，只可以采用以词项为单位的评分方法直观上说，r应该比K大没有必要将所有词项的r设成一样的值，比如对于罕见词项，r值可以适当设大一些③全局胜者表(globalchampionlist)静态质量得分（staticqualityscore，简称静态得分）很多搜索引擎中，每篇文档d往往都有一个与查询无关的静态得分g(d)，该得分函数的取值往往在0到1之间静态得分也是一种全局统一的指标如果将所有文档按照其静态得分g(d)在倒排记录表中降序排列，也可以采用并发扫描的方法进行倒排记录表的合并操作一篇文档d的最后得分可以定义为静态得分g(d)和某个与查询相关的得分的某种组合例：score(q,d)=g(d)+cossim(q,d)公式(1)基于静态得分的全局胜者表对于词典中的每个词项tj，预先计算出g(di)+

wij得分最高的r个文档构成tj

的胜者表给定查询q，对查询q中所有词项的全局胜者表求并集，得到集合A。利用公式(1)只对集合A中的文档计算其最后得分胜者表存在的问题并集A中的元素个数可能会少于K解决办法对每个词项t，维持两个无交集的倒排文件表第一张表称为高端表，由m篇具有最高tf值的文档组成；第二张表称为低端表，由剩下的包含t的文档组成。

每个表均以g(d)值来排序给定查询q，对查询q中所有词项的高端表求并集，得到集合A。只对集合A中的文档计算其最后得分如果该过程能够产生前K篇得分最高的文档，则处理结束。否则，需要继续扫描低端表并计算其中文档的得分。④簇剪枝方法（clusterpruning）

簇剪枝方法之变形

b1

=b2=1时是原始簇剪枝方法增加b1

和b2

会增加找到真实的前K篇文档的可能性，但也会消耗更大的代价4.1.6倒排文档的压缩为什么要进行压缩?节省磁盘空间经过适当的压缩，索引的大小可以降为原始文档的25%左右加快数据从磁盘到内存的传输效率将压缩的数据块传输到内存并解压所需的总时间往往比将未压缩的数据块传输到内存要快提高了倒排文档的缓存能力，因为压缩技术使得内存的利用率大大提高。随着缓存能力的提高，检索的速度也得到相应提高。压缩技术的分类有损压缩会损失一些原文信息大小写转换、去停用词、词干提取、……LSA降维技术无损压缩在压缩文件的同时，其原始信息完全保留，不会缺损倒排文档压缩的内容词汇表记录表（1）词汇表的压缩定宽数组浪费存储空间不能表示所有的词字符串表词汇表关键词文档数链接………………检索3………………计算机2………………记录表文档号……127……29……词汇表关键词指针文档数链接………………3………………2………………记录表文档号……127……29…………检索\0……计算机\0……既紧凑，又不会出现溢出现象压缩率可达50%左右使用定宽数组表示一个单词（2）记录表的压缩问题一般用16位或32位整数表示文档和单词位置的绝对编号。16位很容易溢出，16位整数最多可以表示65536个文档或单词位置编号，这在实际中是很容易造成溢出的（尤其是文档编号）。32位又浪费空间对于大多数文档和单词位置编号而言，很难达到这个数值①定长整数描述相对变化用比较少的位数（如16位）记录位置间的相对变化仅记录相邻位置之间的差异databaseD345,25,34,98,120D348,37,71,85database345,25,9,64,223,37,34,14Wordpositions类似视频压缩中仅记录本帧和上一帧的差异②变长整数描述变化定长整数描述相对变化存在的问题有些常用词（例如“的”），文本编号的相对变化多数是1，如果仍然使用16位编码，显然浪费了太多的空间某些词可能仅存在于少数的文本之中，而这些文本编号的相对变化也很有可能超过65,536，即216。这时，如果仍然使用16位整数表示，就会溢出变长整数描述相对变化基本原理：使用较少的位数表示较小的整数，而较大的整数，则需要使用较多的位数表示压缩技术带来的负面影响在搜索时必须花些时间对压缩的数据进行解码在维护时，特别是进行删除操作时，由于某些文档被删除，所以不得不对剩余的文档编号进行重新编码但是，以上这些都是处理器的计算问题，在目前的硬件条件下，磁盘的I/O速度过慢才是影响IR的瓶颈。由于索引被压缩，提高了磁盘的传输效率，因此，压缩技术仍然是利大于弊的4.1.7倒排文档的性能分析倒排文档的优点检索速度较快存储的信息类型较多，支持复杂的检索操作4.1.7倒排文档的性能分析倒排文档的优点倒排文档的缺点很大的存储开销很高的维护开销文本被看作是词的序列，在某种程度上限制了其应用在某些应用中，如基因数据库，不存在词的概念对于中文等东亚语言，词的概念不明确适合于在相对静态的环境中使用q=人民/生活di:报纸/上/有/一/篇/题/为/“/提高/人/民生/活水/平/”/的/文章但可以压缩提纲4.1倒排文档4.2后缀数组4.3签名文件4.4全文扫描4.2后缀数组后缀（Suffix）是指从某个位置i开始到整个串末尾结束的一个特殊子串。i∈{1,2,…,n}，n为字符串的长度例后缀数组（SuffixArray）是一个一维数组，它按“字典顺序”保存字符串的n个后缀及其起始位置，即SA[i]<SA[i+1]字符串后缀后缀起始位置iS=s1s2s3s4s5 s1s2s3s4s51s2s3s4s52s3s4s53s4s54s55由n个字符组成的字符串有n个后缀4.2.1后缀数组的构造原始文本文本中的部分后缀后缀数组（按字典序索引）024681012141618202224262830323436384042444648…这是一本关于信息检索的教材。介绍了检索的基本技术。…021216223444…这是…是一…信息…检索…教材…检索…技术……441634222120…技术…检索…检索…教材…是一…信息…这是……在实际构造后缀数组时，其实存放的只是各个后缀的前m个字节其实质是倒排索引文本长度为m的字附串4.2.2基于后缀数组的检索原始文本后缀数组q=“信息检索”“信息”→“信息检索” √q=“信息过滤”“信息”→“信息过滤” ×q=“数据结构”“数据” ×024681012141618202224262830323436384042444648…这是一本关于信息检索的教材。介绍了检索的基本技术。…441634222120…技术…检索…检索…教材…是一…信息…这是……在使用后缀数组进行检索的时候，将每个查询同样截取前n个字节，并于索引中进行查找如果没有找到，则表明不包含所需查询如果查找成功，则需要在相应的文本位置上，进行进一步的字符串比较，以确定文本中是否包含查询4.2.3后缀数组的性能分析倒排文档vs.后缀数组从形式上看，后缀数组是一种特殊的倒排文档特指倒排索引文本中长度为n的字符串检索机制不同倒排文档提取完整的查询词，即可确定该查询词的位置信息后缀数组只提取查询词的前几个字，然后逐一匹配后面的字符串，以确定查询词的位置信息后缀数组的缺点没有倒排文档速度快存储开销较大，有重复信息例如：“提高人民生活水平”占用更多的存储单元后缀数组的缺点没有倒排文档速度快存储开销较大，有重复信息很难支持排序操作优点后缀数组可以避免部分分词错误造成的影响，从而提高系统的召回率q=人民/生活di:报纸/上/有/一/篇/题/为/“/提高/人/民生/活水/平/”/的/文章提纲4.1倒排索引4.2后缀数组4.3签名文件4.4全文扫描4.3签名文件4.3.1签名文件的构造词的签名是一个位向量，由F位组成，其中有m位置1Wordshash(wordsignatures)free001000110010text000010101001information000000011110retrieval101000100001freetextinformationretrieval文本串:F=12m=4一种单词“签名”的生成算法输入：词W，参数F和m输出：词W的F位“签名”S算法：1)将W转换为ASCII值（每个字符8位），构成整数i

例如：free=66726565(hex)2)初始化：F位全置0；srandom(i)；

//初始化随机种子j=0；3)whilej<m {

p=random();

//生成一个随机整数

y=pmodF；

//

映射到0和F-1之间

if(S[y]==0)

//确保m位置1

{S[y]=1；

j++；

}

}4)结束，返回Sblocksignatures块的签名Block1Block2WordsWordsignaturesfree001000110010text000010101001information000000011110retrieval101000100001101000111111001010111011freetextinformationretrieval文本串:假设一个块包含两个连续的词块的签名是通过块中所有词的签名按位进行“或”操作得到签名文件按顺序存放块签名的文件签名文件指针文件文档N块Fbits0010101110111010001111114.3.2签名文件的使用和维护对单个词的查询q进行检索Step1：使用相同的散列算法生成q的签名sqStep2：将sq与所有文本块的签名si进行匹配 匹配条件：sq∩si

=sq

如果si在sq取1的位置上也取1，则该块被返回000010101001querysignature∩=000010101001√=000000101001×block1

001010111011block2

101000111111blocksignature如果sq与si

匹配成功,就一定能够确保是一次正确的匹配吗?4.3.2签名文件的使用和维护对单个词的查询q进行检索Step1：使用相同的散列算法生成q的签名sqStep2：将sq与所有文本块的签名si进行匹配falsedrops产生的原因主要原因：不同词的签名重叠次要原因：hash冲突001

000

110

010Query=“free”bitsfrom‘retrieval’signaturebitsfrom‘information’signature误检FalseDrop误检产生的原因？4.3.2签名文件的使用和维护对单个词的查询q进行检索Step1：使用相同的散列算法生成q的签名sqStep2：将sq与所有文本块的签名si进行匹配Step3：对所有匹配上的文本块执行字符串匹配，确定其是否真正含有要查找的单词签名文件的设计签名文件的性能指标存储开销M误检率F一个文本块据其签名看包含某个关键词，但事实上并不包含该关键词的概率需要确定的参数块的大小一般将一个文本看作是一块Signature的长度经验表明，取文本平均长度的30%~40%为宜每个词的Signature中多少位置1签名文件应用：作为过滤器排除不包含查询关键词的文档=过滤出的文本匹配的文本QuerySignature文件文档集合Query

signature4.3.3签名文件的性能分析优点组织简单，容易生成，维护费用较低缺点和倒排文档相比，搜索速度较慢检索的时间复杂性与原始文档集成线性关系去除Falsedrops需要昂贵的开销很难支持排序操作很难使用其它查询函数，例如同义词、通配符、分离条件、邻近操作提纲4.1倒排索引4.2后缀数组4.3签名文件4.4全文扫描4.4全文扫描全文扫描不使用任何索引技术而快速在给定文本或文本集合中查找某一关键词的技术。这种技术通常被称为单模式匹配某些应用中，建立索引的方法并不适用签名文件的候选块确认过程文本过滤搜索引擎的结果后处理全文扫描技术也具有很广阔的应用场合模式匹配问题的定义输入模式P=p1p2…pm文本S=

s1s2…sn(通常

n>>m)输出如果文本S包含模式P，则返回匹配位置否则返回不成功常用的单模式匹配算法BruteForce算法（BF）Knuth-Morris-Pratt

算法（KMP

）Boyer-Moore算法（BM

）4.4.1BruteForce算法

{ i:=1

j:=1

while(i

mandj

n) {if(pi==

sj)

{ i:=i+1;

j:=j+1 }

else

{

j:=j-i+2;

i:=1 } }

if(i>m)

returnj

else

returnfalse; }此循环可以更早地终止:j

n-m+1i=1j=8i=7j=14travelinformationinformingi=1j=9travelinformationinforming模板向右移动算法描述将模式P=p1p2…pm

和文本S的m个字符的子串sksk+1…sk+m-1进行匹配(1≤k≤n)如果匹配，则返回匹配的位置如果不匹配，则从sk+1位置开始新的考察BruteForce算法—性能优点简单、直接、容易实现，无需进行任何形式的预处理缺点时间复杂性较高在模式的末尾发现不匹配在模式的开头发现不匹配4.4.2KMP算法KMP算法是一种改进的字符串匹配算法，由D.E.Knuth、V.R.Pratt、J.H.Morris同时发现位置

12345678文本

abdadefg模式

abdfabdfBruteForce:移动一个字符abdf聪明的做法：移动三个字符在已经匹配成功的部分(abd)没有重复字串，因此“a”不可能出现在下两个字符中KMP算法的基本思想每当匹配过程中出现字符串比较不等时，不象BF算法那样仅将模式向右滑动一个位置，而是利用已经得到的部分匹配结果将模式向右滑动尽可能远的一段距离后，继续进行比较。这种方法可以避免对那些能够推断出不匹配的位置进行徒劳的操作KMP匹配算法–举例abcabcacab3个字符后发现不匹配，在已经匹配成功的部分(abc)没有重复字串将P中的第1个字符与S中不匹配的字符对齐abcabcacab子串abcabca匹配成功;其中最长的重复部分是abca;将P向右移动3个位置，

和重复部分对齐第1个字符不匹配，向右移动1次abcabcacab第1个字符不匹配，向右移动1次P:abcabcacabS:babcbabcabcaabcaabcabcacabKMP–一般原则从匹配成功的子模式中找出“能够相互匹配的最长的前缀和后缀”如果P中已经匹配成功的部分[1..i]首尾有重复部分，重复字串的长度为k，则跳过的字符个数为i-k如果P中已经匹配成功的部分[1..i]首尾没有重复部分,

则可以直接移动

i个字符ββx模式1ii+1文本ββy1jj+ij+i+1ββx为什么要求“最长”？为什么要求“最长”P:abcabcacababcabcacab3个字符后发现不匹配，在已经匹配成功的部分(abc)没有重复字串将P中的第1个字符与S中不匹配的字符对齐abcabcacab子串abcabca匹配成功;其中最长的重复部分是abca;将P向右移动3个位置，

和重复部分对齐第1个字符不匹配，向右移动1次abcabcacab第1个字符不匹配，向右移动1次P:abcabcacabS:babcbabcabca

bcacababcabcacab在不确定的情况下，模板滑动的距离要尽量短，以免错过可能的匹配Shift表例:模式P=“abcabcacab”匹配失败的位置(i+1)模式字符重复子串长度(k)跳过字符数(i-k)1a012b013c024a035b136c237a338c439a0810b18构造Shift表

的时间复杂度：O(m)课后练习：编写分析表构造算法4.4.3Boyer-Moore算法S:BANANA^CREAMP:CREAMS:BANANA^CREAMP:CREAMS:BANANA^CREAMP:CREAMN(sm)

和M(pm)不匹配，且N不在P中出现;向右移动

m=5

个位置,D1=5E和M不匹配，E(sm)

在p中出现;移动P使之相互对齐，D1=2如果有多个E，应该和哪个E对齐？Shift表tm

m12345Cφ1234R1φ123E12φ12A123φ1M1234Φα12345最右不匹配的字母位置编号模式P=CREAM=字母表Σ–{C,R,E,A,M}另一个例子模式P=“BANANA”123456Bφ12345A1φ1φ1φN12φ1φ1α123456过程描述先令模式和文本左边对齐，然后对模式中最右一个字符pm与其在文本中相对应的字符tm进行比较如果比较的结果是不匹配第一种情况，tm根本没有在模式中的任何一个位置出现，那么就可以放心大胆地将模式向后移动m个字符如果tm是模式中的第r个字符（指最后一次出现的位置），那么就可以将模式向后移动m-r个字符如果比较的结果是匹配对模式中右数第2个字符pm-1与其在文本中相对应的字符tm-1进行比较。此过程往复循环。BM算法--D2Shift仅基于

D1,移动一个字符abcabdacababcabdacab仅基于D2,移动5个字符S:babcbadcabcaabcaP:abcabdacab根据模式中是否还包含已经匹配上的子模式”cab”来确定模板移动的距离如何计算Δ2？ijD2Shift的实现如果在

p[i]处不匹配，令：

len=m-i

找到最大的j

使p[j..(j+len-1)]=p[(i+1)..m]

则：shift2[i]=i–j+1P:abcabdacabij是否D2

总是大于D1

？

S:babcbadcabcaabcaP:abcabcacababcabcacab

D1=7