|
4.3 改进的BM算法与BM算法的性能比较 4.3.1 性能实例比较 内容来自www.paper51.com
在字符T串astringsearchingexamplienvolingrelative中查找字符P串relative。 paper51.com
(1)使用BM算法的结果如下： 内容来自www.paper51.com
astringsearchingexamplienvolingrelative http://www.paper51.com
relative① copyright paper51.com 失配字符s不在模式P中，Skip数组使得模式P向右移动，跳过字符s。 copyright paper51.com
astringsearchingexamplienvolingrelative copyright paper51.com relative② copyright paper51.com 失配字符g不在模式P中，Skip数组使得模式P向右移动，跳过字符g。 http://www.paper51.com astringsearchingexamplienvolingrelative http://www.paper51.com
relative③ http://www.paper51.com 失配字符为i，已经匹配过的字符部分e在模式P中再次出现，且其前缀不为i，Shift数组使得模式P向右移动，使得文本T串中的匹配字符e与模式P串中最右边的前缀不为i的e对齐。(相比Skip数组的将两个i字符对齐的移动量更大，故选择Shift数组的移动量。) http://www.paper51.com astringsearchingexamplienvolingrelative 内容来自www.paper51.com relative④ 内容来自论文无忧网 www.paper51.com 失配字符n不在模式P中，Skip数组使得模式P向右移动，跳过字符n。 paper51.com astringsearchingexamplienvolingrelative paper51.com relative⑤ 内容来自www.paper51.com 失配字符v在模式P中，Skip数组使得模式P向右移动，使两个字符的v对齐。 内容来自www.paper51.com astringsearchingexamplienvolingrelative http://www.paper51.com
relative⑥ copyright paper51.com 至此，成功的找到了匹配模式串。 内容来自www.paper51.com (2)使用改进的BM算法的结果如下： copyright paper51.com astringsearchingexamplienvolingrelative 内容来自www.paper51.com relative① 内容来自www.paper51.com 失配字符s不在模式P中，其skip数组为模式P串的长度8，k值为7。模式P串向右移动8，即刚好跳过字符s。 内容来自论文无忧网 www.paper51.com
astringsearchingexamplienvolingrelative 内容来自www.paper51.com relative② paper51.com 失配字符g与e不匹配，它在模式P串中也没有出现，可知字符g的skip值为8，k值为15，模式T串向右移动8。 copyright paper51.com astringsearchingexamplienvolingrelative 内容来自论文无忧网 www.paper51.com
relative③ paper51.com 字符i与字符v不匹配，但i出现在模式串P中，故其skip数组为2，k值为22，模式P向右移动1。 paper51.com
astringsearchingexamplienvolingrelative 内容来自论文无忧网 www.paper51.com relative④ 内容来自论文无忧网 www.paper51.com 字符n与e不匹配，它在模式P串中没有出现，其skip值为8，k值为29，模式T串向右移动8。 http://www.paper51.com astringsearchingexamplienvolingrelative copyright paper51.com relative⑤ 内容来自论文无忧网 www.paper51.com 字符v与e不匹配，但它在模式P串中有出现，其skip值为7，k值为37，模式P串向右移动1。 http://www.paper51.com astringsearchingexamplienvolingrelative 内容来自论文无忧网 www.paper51.com relative⑥ copyright paper51.com
至此，成功的找到了匹配模式串。 paper51.com 综合上述内容，我们可以看出，改进的BM算法只使用了一个数组，并简化了初始化过程，还省去了求Skip和Shift数组的复杂计算，故更具有可操作性，也更容易实现。 paper51.com
4.3.2 性能测试比较 http://www.paper51.com 在同一台机器上，分别对BM算法和改进的BM算法进行测试，用同一主程序调用这两种匹配算法，匹配算法中均插入CPU内部时间戳进行高精度计时，同时统计每种算法一次匹配过程中模式匹配串右移次数。 paper51.com
实验一:对文本串earolteoelheiafcealrnireoapfye进行不同长度模式串i,re, rel, rela, relat, relati, relatio, relation的匹配，字符数由1增至8，分别使用BM和改进的BM算法统计其模式串的移动次数，结果如下表4-3： 内容来自论文无忧网 www.paper51.com 表4-3 实验一结果 内容来自www.paper51.com
模式串 http://www.paper51.com 移动次数 内容来自www.paper51.com r 内容来自www.paper51.com re http://www.paper51.com rel 内容来自www.paper51.com rela paper51.com relat 内容来自www.paper51.com relati 内容来自论文无忧网 www.paper51.com relatio 内容来自www.paper51.com relation 内容来自www.paper51.com BM算法 内容来自www.paper51.com
31 paper51.com 24 http://www.paper51.com 15 内容来自www.paper51.com 10 copyright paper51.com 9 内容来自论文无忧网 www.paper51.com 7 http://www.paper51.com 6 内容来自论文无忧网 www.paper51.com 6 copyright paper51.com
改进的BM算法 copyright paper51.com 32 http://www.paper51.com 17 copyright paper51.com 12 内容来自www.paper51.com 9 内容来自www.paper51.com 9 copyright paper51.com 6 内容来自www.paper51.com 6 http://www.paper51.com 5 内容来自论文无忧网 www.paper51.com
实验二:对文本串epodemdrepgdvifghkmvmpiovmdfnp进行不同长度模式串i，im，imp,impr,impro，improv,improve,improved的匹配，字符数由1增至8，分别使用BM和改进的BM算法统计其模式串的移动次数，结果如下表4-4： paper51.com 表4-4 实验二结果 内容来自www.paper51.com
模式串 内容来自www.paper51.com 移动次数 内容来自www.paper51.com
i http://www.paper51.com im 内容来自论文无忧网 www.paper51.com imp 内容来自论文无忧网 www.paper51.com
impr paper51.com impro paper51.com improv http://www.paper51.com improve copyright paper51.com improved http://www.paper51.com BM算法 内容来自论文无忧网 www.paper51.com
31 内容来自www.paper51.com 26 copyright paper51.com 15 paper51.com 11 paper51.com
7 copyright paper51.com 6 内容来自论文无忧网 www.paper51.com 7 http://www.paper51.com 5 copyright paper51.com 改进的BM算法 paper51.com 32 copyright paper51.com 17 内容来自论文无忧网 www.paper51.com 12 copyright paper51.com 8 内容来自www.paper51.com 7 paper51.com
6 内容来自论文无忧网 www.paper51.com 6 内容来自论文无忧网 www.paper51.com 5 paper51.com
|