信息内容安全管理及应用教学课件(共12章)第七章信息处理模型和算法.pptxVIP

第7章 信息处理模型和算法;在信息检索和文本编辑等等应用中，快速对用户定义的模式或者短语进行匹配是最常见的需求。在文本信息过滤的处理中，匹配算法也一直是人们所关注的。一个高效的匹配算法会使信息处理变得迅速而准确，从而得到使用者的认可；反之，会使处理过程变得冗长而模糊，让人难以忍受。本节首先简要介绍了三种经典的单模式匹配算法：Brute-Force算法、KMP算法、和QS算法的匹配思想。其次介绍了多模式匹配算法。;?;Brute-Force算法(直接匹配算法)是模式匹配最早、最简单的一个算法，它将正文T顺次分成n-m+1个长度为m的子串，检查每个这样的子串是否与模式串P匹配。该算法的匹配过程易于理解，最坏时间复杂度是O(m*n)。当第一次匹配成功时，仅需比较m次；当P中第一个字符不同于T中任意一个字符时，只需比较n次，所以该算法实际用起来效率尚高，因此还被采用。例如主串T= abcdefg’，模式串P= ’cde’，则模式匹配的过程如下图7-1所示： ;Brute-Force算法匹配过程可以简化为图7-2所示。 Brute-Force算法的缺点是对模式串的扫描常常要回溯，因此当模式串难于随机访问时，就会显得特别不方便。同时，这种算法匹配过程中存在许多重复操作，影响了执行效率。 ;1970年，S.A.Cook在理论上证明串匹配问题可以在O(m+n)时间内解决。随后D.E.Knuth和V.R.Pratt仿照Cook的证明构造了一个算法，与此同时，J.H.Morris在研究正文处理时也独立地得到与前述两人本质上相同的算法。这样两个算法殊途同归地构造出当前最普遍采用的算法，称为Knuth-Morris-Pratt算法(简记为KMP算法)。此算法实际可以在O(m+n)的时间数量级上完成串匹配运算，最大的特点是指示文本串的指针不需回溯，整个匹配过程中，对文本串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读边匹配，而无需回头重读。 ;?;?;?;?;?;?;?;?;?;（3）DFSA算法的查找过程 利用已构成的有限自动机进行多个模式串一次查找的过程如下： 1）从有限自动机的0状态出发，逐个取出{P}中模式Pk中的字符c，并按转向函数g(s, c)或失效函数f(s)进入下一状态。 2）当输出函数output(s)不为空时，输出output(s)。 如若用图7-4中的有限自动机扫描文本串“ushers”。开始为0状态，因g(0,u)=0，g(0,s)=7，g(7,h)=8，g(8,e)=9，而output(9)={he，she}，故输出{he，she}；因f(9)=g(f(8),e)=2，g(2,r)=3，g(3,s)=4，output(4)={hers}，故输出｛hers｝。即文本串“ushers”中含有he，she，hers这三个模式串。 ;（4）DFSA算法处理汉语文本的不足 DFSA多模式匹配算法在处理中文文本时，有一系列的问题。首先，该算法针对英文等ASCII代码集语言处理时，只需要一个字节即可表示，而汉字有多个字节，不同的编码有不同的字节数目，例如大陆的GB2312编码，汉字为2个字节。而台湾的Big5码则是1个到2个字节表示。在处理汉语古文字时，由于文字数量更多，有时还会使用四字节来表示。其次，在构建转向表的时候，由于汉字字符数量大，转向表的处理就不能等同于西文文本，否则过于浪费空间，查找效率低。另外，虽然中文字符集包含大量的字符，但各个字符的出现频率差别很大。常用的中文汉字由此可以分为一级汉字、二级汉字等。现代中文中的1300多常用字，已能覆盖现代中文中用字的95％以上；对应于一级汉字中的3755个字，它的出现频率覆盖率基本上已经在所用汉字中占99.9％以上。同时，中文词的平均词长也较短，只有1.83-2.09，这意味着通常待匹配的字串模式长度较短。 由于以上原因，上述算法一旦运用到中文里就有所欠缺。首先对于排序就不能按照英文的字母顺序，也就是说，不可能象处理英文那样直接比较字符的大小。况且，即使可以比较，也存在两个字符比较的问题，所以，按照英文的处理方式是不可行的。 其次，尤其是涉及到中英文混杂的时候，该算法有着无法解决的难处。现在越来越多的信息将中英文混杂在一起处理，比如常见的Intel处理器，Microsoft研究院，Dell服务器等等数不胜数的例子。对于这样的模式串，原始算法是没有办法处理的。 针对中文的处理，我国研究人员提出了很多专门针对汉语文本的多模式匹配算法。;第7章 信息处理模型和算法;分类算法在图像分类、索引和内容理解方面都有直接的应用，其主要功能是：通过分析不同图像类别各种图像特征之间存在的差异，将其按内容分成若干类别。经过几十年的研究与实践，目前已经有数十种的分类方法。图7-5给出了主