预先计算模式树在坏字符规则和好前缀规则下的移动距离。建立个大小为的字符型数组，并初始化为。④通过字符串空间映射方法，将模式树的前个字符两两相邻地映射到中，相应值置为。匹配阶段初始时，模式树的根节点对齐文本串的倒数第个字符。从左至右依次比较文本字符和模式树节点，每当匹配到个模式串，记录匹配信息并继续向后比较。如果发生失配或匹配到模式树的叶子节点时，需要计算模式树的左移距离。设当前匹配窗口前个字符及其后继字符组成字符串为，则检查的值若，则将模式树左移个字符若，则启用坏字符规则和好前缀规则计算模式表值字符串移动距离输出信息树的移动距离，取其较大者作为实际移动距离移动模式树。④重复步骤和直到模式树第层节点对齐文本串第个字符。算法举例设文本串，模式串为，最短模式串长度。预处理阶段将模式串构建成模式树即正向有限状态自动机，模式树如图所示。图算法示例模式树模式树前层内需要地址映射的字符串有，建立的表如表所示。表算法示例表字符串移动距离输出信息↑↑↑↑↑项数目据模式串数量直接移动个字符次数移动距离小于的次数合计移动次数直接移动个字符所占比率，匹配阶段表算法举例算法匹配过程如表所示，↑标示出了模式树第层字符的位置，发生失配的字符以灰色背景标出，模式树从右向左移动。匹配过程如下初始状态模式树的第层字符对齐文本串的第个字符，发生失配，待检查的字符串为。由于，故需要进步检查失配字符。由于出现在模式树的第层，没有好前缀，故模式树移动距离为个字符，为坏字符对应模式树层数，为坏字符在模式树中的最右出现层数。模式树第层字符对齐文本串第个字符，模式串匹配成功，模式树向左移动个字符。模式树的第层字符对齐文本串第个字符，发生失配，待检查的字符串为。由于，故模式树移动距离为个字符。④模式树的第层字符对齐文本串第个字符，发生失配，待检查的字符串为。由于，故模式树移动距离为个字符。模式树的第层字符对齐文本串第个字符，模式串匹配成功，匹配结束。算法时间性能分析最大化模式树的移动距离算法发生失配时，坏字符规则检查当前失配的坏字符是否出现在其后的模式树中。当该坏字符未出现时，模式树移动距离为个字符为最短模式串长度，为坏字符对应的模式树层数否则，模式树移动距离小于个字符。在最好情况下，仅当时即模式树的第层与文本串字符发生失配，模式树的移动距离才可以达到个字符。然而，失配的坏字符往往出现在模式树前层地内部。因此，算法的坏字符规则导致了模式树移动距离不足，往往小于个字符。算法的坏字符规则进行两次检查检查当前匹配窗口末字符及其后继字符组成的字符串是否出现在模式树的前层内。若不出现，则直接将模式树移动个字符，且不需要计算好前缀规则下模式树移动距离否则进行下步检查。使用算法的坏字符规则检查失配的坏字符是否出现在其后的模式树中。单个字符有种取值，如果模式串数量较多，那么模式串中的字符就有可能包含各种取值。若仅查找单个字符是否出现在模式树中时，显然找到的概率会很大。两个相邻字符组成的字符串的可能取值有种，比单个字符的取值空间大大提高，因此算法每次查找两个相邻字符可以提高不存在于模式树中的概率，从而直接移动模式树个字符。同时，算法在字符串存在于模式树中的情况下，继续检查坏字符是否出现在其后的模式树中，使得模式树移动距离始终大于等于算法模式树的移动距离。综上所述，算法最大化了模式树的移动距离，尽可能使模式树每次移动个字符。快速地查找两个相邻字符算法每次移动模式树前，都要检查当前匹配窗口末字符及其后继字符组成的字符串是否出现在模式树的前层中。因此，在模式树的前层中快速查找字符串，可以有效地提高算法效率。算法使用了字符串地址映射的方法来提高检查速度。该方法将所有模式树前层内的两两相邻的字符作为位的偏移地址映射到个大小为数组中，匹配阶段只要进行次按偏移地址取值操作就可以检查字符串是否出现在模式树的前层，从而节约了时间消耗。使用正向有限状态自动机针对很多英文单词具有相同后缀的特点，算法使用正向有限状态自动机，将大部分模式串的后缀排除在模式树的前层之外，从而提高字符串不存在于模式树中的概率，使模式树移动尽可能达到最大安全移动距离。第五章算法时间性能测试本章通过实验比较算法与算法的时间性能。实验结果表明算法的坏字符规则有效地提高了模式树的平均移动距离，减少了不必要的字符比较次数，从而提高了算法的时间效率。实验环境与资源实验环境酷睿双核处理器主频，内存，环境，语言实现。文本串和模式串文本串由中英文小说合并组成，大小为文本，内容涉及古典名著政治经济军事现代科普等模式串的从文本中提取，其余为随机生成字符串。实验方案实验算法坏字符规则效果测试在最短模式串长度相同的情况下均为，分别使用个模式串测试算法坏字符规则效果模式树直接移动个字符的次数占总移动次数的比率为最短模式串长度。实验二算法和算法时间性能从两方面比较算法和算法的匹配阶段时间效率匹配阶段耗时和模式树总移动次数。匹配阶段耗时越短，算法的时间效率越高模式树总移动次数越少，说明平均移动距离越长比较次数越少，算法的时间效率越高。测试模式串数量对算法性能的影响。在固定最短模式串长度为的情况下，分别使用个模式串测试两个算法的时间性能。测试最短模式串长度对算法性能的影响。在固定模式串数量为个的情况下，分别使用最短模式串长度为的模式串测试两个算法的时间性能。实验数据与分析实验算法坏字符规则效果测试分别使用个长度均为的模式串测试算法坏字符规则效果模式树直接移动个字符的次数占字符串移动距离输出信息↑↑↑↑↑项数目据模式串数量直接移动个字符次数移动距离小于的次数合计移动次数直接移动个字符所占比率，总移动次数的比率。表算法坏字符规则效果如表，算法坏字符规则在未找到字符串时直接移动个字符的次数占总移动次数的比率均大于，最好时达到，说明算法坏字符规则是有效的。模式串数量从个到个变化过程中未找到字符串所占的比率呈明显上升趋势，说明模式串数量越少，字符串未找到的概率越高。实验二与算法时间性能在最短模式串长度为的情况下，测试模式串数量对算法的时间性能影响图模式串数量对算法时间性能的影响黄昆高性能正则表达式匹配算法评估计算机工程图模式串数量对模式树移动次数的影响如图所示，在最短模式串长度和文本串大小相同情况下，模式串数量从到个增加过程中，算法时间性能始终优于原算法。如图所示，算法的模式树左移次数最好时只占算法的，有效减少了模式树移动次数。在模式串数量为个的情况下，测试最短模式串长度对算法的时间性能影响图最短模式串长度对算法时间性能的影响图最短模式串长度对模式树移动次数的影响如图所示，在模式串数量相同，最短模式串长度从到增加过程中，算法时间性能始终优于算法，且最短模式串长度越长，算法的时间性能越好。如图所示，算法的模式树左移次数最好时只占算法的，有效减少了模式树移动次数。第六章总结与展望总结模式匹配是计算机信息技术领域研究的基本问题之，广泛应用于文本编辑搜索引擎系统计算机病毒检测内容过滤入侵检测生物科学计算等方面。近年来，随着计算机网络的普及和快速发展，网络信息流量出现了爆炸式增长，模式匹配算法的时间性能正日渐成为网络发展的瓶颈。因此，进行模式匹配算法的研究具有重要的理论和现实意义。本文工作总结研究了典型的单模式匹配算法算法算法算法算法算法等，阐述了它们的原理分析了它们的时间性能，并举例说明了它们的匹配过程。研究了典型的多模式匹配算法算法算法算法等，阐述了它们的原理分析了它们的时间性能，并举例说明了它们的匹配过程。分析了算法模式树移动距离不足的缺点，提出了种改进的算法，该算法使用改进的坏字符规则，使模式树移动距离尽可能达到最大值最大值为最短模式串长度。算法的坏字符规则提高了模式树移动距离达到最大值得概率，从而提高了模式树的平均移动距离，减少了不必要的字符比较次数。通过仿真实验比较算法和算法的时间性能。实验结果表明，算法具有较好的时间性能。展望随着计算机互联网技术的发展，网络信息流量随之爆发式增长，对模式匹配算法的性能提出了更高的要求。未来的研究工作主要有算法使用模式树有限自动机存储模式串信息，当模式串数量较多且模式串信息差异较大时，模式树的节点数会大幅度增加。可以尝试使用压缩树来减少模式树存储的空间消耗。最短模式串长度过短时，对算法性能影响较大。因此，如何对长度过短的模式串进行预处理以降低其对全体模式串匹配速度的影响，仍是需要解决的重要问题。网络处理器的应用要求模式匹配算法具有并发性。因此，如何利用多核多线程技术对模式匹配算法进行优化，是模式匹配研究的方向之。硬件匹配速度快数据吞吐量大，是未来模式匹配技术的发展趋势。参考文献中国互联网络信息中心中国互联网络发展状况统计报告年月，，王继成，萧嵘，孙正兴等信息检索研究进展计算机研究与发展王慧强，杜晔，庞永刚入侵检测技术研究计算机应用研究宋华，戴奇种用于内容过滤和检测的快速多关键词识别算法计算机研究与发展，卢开澄计算机算法导引设计与分析清华大学出版社，章张基于层次分类的网络内容监管系统中串匹配算法的设计与实现，南京理工大学硕士学位论文，年月，，，，，，