《一种快速的单模式匹配算法.doc》由会员分享，可在线阅读，更多相关《一种快速的单模式匹配算法.doc（4页珍藏版）》请在三一文库上搜索。
1、一种快速的单模式匹配算法0引言 模式匹配是计算机技术领域的一个基本问题。它在入侵检测、数据压缩、WWW搜索引擎以及计算机病毒特征码匹配等系统中都有十分重要的应用价值。模式匹配就是在给定的文本串中查找模式串的出现次数。若出现次数为0，称匹配失败；若出现的次数大于或等于1，则称匹配成功。 本文使用P=P0.m-1表示要匹配的模式串，长度为m；文本串表示为T=T0.n 1，长度为n；字符表以表示，大小为。将匹配过程中P与T中长度为m的子串作一次比较称为一次尝试，并将当前尝试中与模式串对齐的T的子串称为当前窗口。 在通常应用中，BM1算法被看做是最有效的单模式匹配算法。它采用从右向左的比较方式，并利用
2、当前尝试中的已匹配信息和匹配失败的字符，查找预处理好的好后缀跳跃表(good suffix shift table)和坏字符跳跃表(bad character shift table)，使尝试跳跃式地进行。其最大可能跳跃距离为m。TunedBM2算法则是BM算法的简化实现。由于它只使用了坏字符跳跃表，有效地减少了字符比较次数，在实际应用中效率比BM算法高，但最坏情况时的性能不如BM。本文在对这两种算法进行简要介绍和分析的基础上，综合两者之长，提出了一种更加快速的单模式匹配算法，即NFS。该算法充分利用当前尝试中匹配失败字符的位置信息，以期在每一次跳跃中跳跃尽量大的距离。实验结果表明，与其他同类
3、算法相比，NFS算法更加有效。尤其是在模式长度较短的情况下，表现出优越的查找性能。考虑到汉语词的平均长度约为4 Byte，故该算法对中文信息处理中的信息检索问题尤为适用。 1BM和TunedBM算法 1)BM算法 BM算法在当前窗口中对模式P自右向左进行扫描。当匹配失败或完全匹配时，用两个预先计算的偏移函数BadCha racter和GoodSuffix来确定文本指针的右移距离。该算法预处理阶段的时间复杂度为O(m+)；匹配阶段的时间复杂度为O(mn)，但当匹配一个非周期化的模式时至多需要匹配3n个文本字符,最好情况下的时间复杂度为O(n/m)。 2)TunedBM算法 考虑到字符的比较操作是
4、模式匹配算法中最费时的部分，可以在实际比较前尽量向前移动模式。TunedBM算法只使用了BadCharacter偏移函数。在匹配阶段，算法在文本串中查找Pm-1(即模式P的最后一个字符)。若不匹配则指针一直向前移动，直到找到它。在找到Pm-1的情况下，再比较模式中的其他字符。此后无论相等与否都将使文本指针向前移动Pm-1对应的偏移位置。预处理阶段的时间复杂度为O(m+)。匹配阶段时间复杂度最坏情况下可达到平方级，但在实际应用中效率很高。 2NFS算法 进一步提高模式匹配算法效率的主要途径是利用当前尝试中可以获取的信息进一步增大跳跃距离。综合BM和TunedBM算法的优点，本文提出了NFS算法。它采用TunedBM的BadCharacter和BM的GoodSuffix对模式进行预处理；然后根据当前尝试中匹配失败字符的位置信息，决定是查找好后缀跳跃表还是坏字符跳跃表，以期获得更大的跳跃距离。算法分为模式的预处理阶段和文本的查找阶段。 21预处理阶段 预处理阶段的任务是计算BadCharacter和GoodSuffix两个偏移量函数。 1)BadCharacter函数的计算 5结束语 NFS算法综合了BM和TunedBM算法的优点，使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配，有效地提高了匹配速度。由于查找问题的普遍性，该方法具有广阔的应用前景。