资源描述：
《第6章-字符串匹配算法.newppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机技术与软件学院王佰玲信息内容安全技术第6章信息内容安全处理——字符串匹配算法本章内容6.1信息处理技术背景6.2串匹配算法概念6.3模式匹配算法分类6.3.1单模式匹配算法BF算法KMP算法BM算法6.3.2多模式匹配算法AC算法Agrep算法6.1.1字符串匹配与信息处理数据经过高性能数据捕包和协议分析与还原之后,就可以还原成相应的内容。例如,如果捕获到的数据经过http协议的还原,成为一个完整的网页；经过smtp协议还原后成为一封完整的邮件；之后，根据需要进行相应的分析,即使用字符串匹配技术串匹配（stringmatching），也叫模式匹配（patternmat
2、ching），可以简单地定义为在给定的字符流中查找出满足某些指定属性的字符串。这是计算机科学中最古老也最普遍的问题之一，计算机科学中串匹配的应用可以说随处可见。近年来，随着计算机技术（各种应用）的蓬勃发展，尤其是信息检索和生物计算领域中的许多共同需求，极大激发了人们对串匹配算法的研究兴趣。大概我们最熟悉的应用是文本编辑中所使用的查找替换，这是一种最简单的串匹配问题。6.1.2串匹配应用背景在生物计算领域在一个DNA链上查找某些特定特征，或者比较两个基因序列有多大差异，可以简单地归结为在“文本”中查找特定的“模式”的串匹配问题。在信号处理领域语音识别的一般情形可以大致描述为确
3、定一个语音信号是否符合某些特征。只要事先把语音信号转化为特定形式的数字信息，就可以应用串匹配算法来解决识别问题。6.1.2串匹配应用领域在自然语言处理方面信息检索在网络安全方面发现具有某些特征码的有害信息病毒和入侵检测NID（NetworkIntrusionDetection）串匹配问题不仅在各种实际应用中有着广泛的需要，而且在计算机理论研究中也占有着十分重要的地位，它可以不断地提出非常具有挑战性的理论问题。6.1.2串匹配应用领域(cont.)本章内容6.1信息处理技术背景6.2串匹配算法概念6.3模式匹配算法分类6.3.1单模式匹配算法BF算法KMP算法BM算法6.3.
4、2多模式匹配算法AC算法Agrep算法文本：由若干个字符组成的有限序列，设为y={y1y2y3…yn},其中n为文本长度，即文本中总的字符个数。模式：也称为关键字，由若干个字符组成的有限序列k={k1k2k3…km}，其中m为模式长度，即模式中字符总数。模式集：指所有需要匹配的模式形成的集合，记为P={p1,p2,p3,…,pr}，其中pi是模式集中第i个模式。记模式集中所有模式长度的总和为
5、P
6、。最小模式长度：假设模式集中各个模式长度分别为l1,l2,…lr,那么最小模式长度是指所有模式长度的最小值，即minlen=min{l1,l2,…lr}。前缀：两个字符串p和x，若
7、存在字符串v（v可为空串），使得p=xv成立，称x为p的前缀。6.2.1串匹配概念6.后缀：两个字符串p和x,若存在字符串u（u可为空串）,使得p=ux成立，称x为p的后缀。7.子串：两个字符串p和x,若存在字符串u,v（u,v可以为空串），使得p=uxv成立，称x为p的子串。8.字符集：在模式或文本中所有可能出现的字符形成的集合，记为Σ，其大小记为
8、Σ
9、。6.2.1串匹配概念(cont.)6.2.2模式匹配的分类模式匹配的模式数目单模式多模式匹配方式精确匹配近似匹配匹配的具体内容单词匹配字符类匹配正则表达匹配文本的角度实时(on-line)文本:文本可以动态地更新例如:网
10、络入侵监测非实时(off-line)文本:被查找文本是静态的例如:搜索引擎中查找的数据6.2.2模式匹配的分类单模式匹配单模式匹配可定义为：在一个文本text(设长度为n)中查找某个特定的子串pattern(设长度为m)。如果在text中找到等于pattern的子串，则称匹配成功，函数返回pattern在text中出现的位置(或序号)，否则匹配失败。多模式匹配多模式匹配可定义为：在一个文本text(设长度为n)中查找某些特定的子串patterns(设长度为m)。如果在text中找到等于patterns中的某些子串，则称匹配成功，函数返回pattern在text中出现的位置(
11、或序号)，否则匹配失败。6.2.3单模匹配vs多模匹配本章内容6.1信息处理技术背景6.2串匹配算法概念6.3模式匹配算法分类6.3.1单模式匹配算法BF算法KMP算法BM算法6.3.2多模式匹配算法AC算法Agrep算法6.3.1单模式匹配算法——BF算法BF（Brute-Force）算法(又称Naive算法)是最早出现的单关键字匹配算法思想简单理论上的时间复杂度很差实际使用效果尚可ANSIC中提供的strstr函数就是使用这种算法的改进版本。由于BF算法扫描字符串时常常需要回溯，这样当文本难于随机访问时，就显得
