|
150 图4-1 RFC2616 文档匹配比较 图4-1 中，纵坐标表示单次匹配所消耗的时间，单位为毫秒，三种颜色柱状图分别表示 三种算法，可以看出BMH 算法和文中提出算法对BM 做了相对较大的改进，性能明显有所 提升，而表4-3 中也可以看出，文中算法在一定程度上在匹配耗时上略低于BMH，对BMH 155 有了改进。在更改匹配文档和模式串做统计分析也可以得到相同的结论，如表4-4 和图4-2。 表4-4 RFC3069 文档匹配比较 匹配算法 BM BMH 改进算法 匹配文档 RFC3069.txt 文档大小 16KB 模式串 implementation 重复次数 50 总耗时（毫秒） 1.57 0.91 0.79 平均耗时（毫秒） 0.031 0.018 0.015 160 图4-2 RFC3069 文档匹配比较 其次，考虑到不同长度对三种匹配算法的影响，对不同长度模式串下三种匹配算法耗时 165 进行了比较分析。文中模式串长度从2 到16 进行了匹配，记录了每次匹配的时间，比较结 果如下所示。 图4-3 三种模式匹配算法在不同模式串长度下耗时 图4-4 BMH 算法和改进算法比较 图4-3 所示为BM 算法、BMH 算法和改进算法在不同模式串长度情况下对同一文档进 行匹配耗时的比较，从图中可以看出，模式串长度变化的情况下，BMH 算法和改进算法都 175 会比BM 算法拥有更好的性能，因此，主要对BMH 算法和改进算法进行了单独比较分析， 如图4-4 所示，从图中可以看出，在模式串长度较短（此次实验中为小于4）的情况下改进 算法并不能很好的提升BMH 算法的性能，但是随着模式串长度的提升，模式串后缀相同的 概率也提升，因此改进算法的性能要优于BMH 算法。 180 图4-5 BMH 算法和改进算法时间差（单位：毫秒） 由于BMH 和文中算法已经对BM算法做了很大的改进，因此笔者分析的侧重点为BMH 算法和文中算法的分析。图4-5 所示为两种算法的时间差，纵坐标的值为BMH 耗时减去文 中算法消耗时间，如果为负数表示BMH 算法耗时较文中算法少，如果为正数则表示文中算 185 法耗时比BMH 算法少。 从图中我们可以看出，随着模式串长度的增大（大于4），文中算法的优势较为明显， 都会比BMH 算法耗时少。这可以利用文中算法的思想来解释，文中算法的主要思想和理论 依据是英文文本中，后缀相同的概率要比首尾字节相同的概率大，而当英文单词比较短的情 况下，这个区别不是很明显，因此会出现文中算法表现没有BMH 好。但是随着模式串长度 190 的提高，而且多数情况下也会比较长，文中算法的优势就会有所表现，由于英文单词的这个 特点使得文中算法可以比BMH 算法进行更少的匹配。实验中使用的不同长度模式串以及详 细的信息如表4-5 所示 表4-5 不同长度模式串下三种算法耗时 模式串 长度 BM（毫秒） BMH (毫秒) 文中算法 （毫秒） 时间差 (毫秒) Ex 2 24.15 5.49 9.65 ‐4.16 add 3 24.08 8.15 9.55 ‐1.40 WILL 4 305.23 107.99 122.34 ‐14.34 solve 5 79.98 34.64 33.20 1.44 cached 6 15.12 6.43 5.75 0.68 amounts 7 161.70 75.71 70.63 5.08 www-talk 8 137.77 58.00 57.81 0.18 confusion 9 141.66 69.99 60.86 9.13 unexpected 10 39.23 17.98 16.76 1.22 contributed 11 114.51 63.33 54.15 9.18 transmission 12 20.15 9.09 8.18 0.91 unsatisfiable 13 76.67 45.73 41.35 4.38 full length of 14 130.58 64.61 58.02 6.59 MERCHANTABILITY 15 75.39 41.63 40.73 0.89 interoperability 16 9.66 4.49 4.13 0.35 195 5 结论 本文在全面分析BM 算法和BMH 算法的基础上，提出了一种基于BMH 的改进算法， 主要思想源于对模式串特点的分析，由于无论是入侵检测系统还是网络数据监控中模式串多 数是一个英文单词，本文从模式串为英文单词的这个特点重新设计了BMH 的匹配思路，只 200 有当首尾字节都匹配的情况下才对文本进行匹配，从实验结果分析中可以看出，文中提出的 算法在一定程度上改进了BMH 算法，而BMH 算法是BM 算法的一种改进。特别是利用到 英文单词匹配中文中算法相比较BMH算法有一定的优势。从而能够较大的提升系统的性能。 由于该算法还是单模式匹配算法，运用也比较局限，因此在以后的研究中，在多模式匹配中 也可以做相应的改进，从而更好的提升系统的性能。 205 [参考文献] (References) [1] BOYER R S. MOORE J S. A fast string searching algorithm[J]. CACM,1977, 20 (10): 762-772. [2] 陈军卫，梅进杰. 一种基于BM 算法的新算法[J]. 空军雷达学院学报，2010，24(6)：439-442. [3] 巫喜红，凌捷. BM 模式匹配算法剖析[J]. 计算机工程与设计，2007 年，28（1）：29-31. 210 [4] 孙克雷. IDS 中一种快速模式匹配算法[J]. 安徽理工大学学报，2006，26（3）：52-55. [5] R. NIGEL HORSPOOL. Practical Fast Searching in Strings[J]. SOFTWARE-PRACTICE AND EXPERIENCE,1980,10(6):501-506. [6] 李雪莹，刘宝旭. 字符串匹配技术研究[J].计算机工程，2004，30（22）：24-26. 学术论文网Tag：代写代发论文 计算机论文 代发论文 代写工科论文 职称论文发表 |
