KMP 算法并非优化
算法书和数据结构书对KMP算法多有介绍，称只需对字符串扫描一遍不需回溯云云.然而,它恐怕只应该作为一种思想存在;用于实际的字符串查找并不理想.要费劲心血实现和优化它,才能在特定的字符串上略微超过(也可能略微逊过)std::search.
KMP算法的基本思想,是利用需要匹配字符串的自身信息来避免回溯.(这里讨论的算法是以C/C++为编程语言,因此下标索引以0开始)
例如:字符串PAT=”abcabcde”,里面第二段的abc和PAT开头的字符是匹配的.
假如我们有个要查找的字符串TEXT=”abcabD...”,在比较到TEXT的'D'处(TEXT[5])也即到了PAT的第二个'c'(PAT[5])时比较失败,一般的字符串查找又得从TEXT[1](即'b')开始查找PAT.而KMP算法知道PAT的第二段abc匹配自身的开头字符串，它会对PAT存储如下next表:0 0 0 1 2 3 0 0数字代表匹配失败后应该从PAT的第多少个位置开始比较.我们这里在PAT[5]处失败,而前面的PAT[0...4]都比较成功,因此先看看PAT[5]的上一个成功位置的next信息:next[4]=2,这代表应该从PAT[2]处重新开始比较(即说明有2个字符不需要比了),就不需要跳到TEXT[1]处重新启动查找,这时的PAT[0...1]为”ab”,TEXT的'D'的前面两个也是”ab”,只需要开始比较TEXT[5]和PAT[2],KMP说的无回溯意义正是如此:不需要回溯TEXT的比较位置.如果PAT[2]又失败了,next[1]=0.那么TEXT[5]与PAT[0]开始比较,不成功的话TEXT递增到TEXT[6],一直递增到成功为止,成功的话当然PAT也开始递增.
伪码如下:
template<class I>
I find(I beg,I end)
{
int patPos=0;
while (beg!=end)
{
if (*beg==PatChar[patPos])
{//匹配时递增文本和模式的指针.
++beg;
if (++patPos!=sizePat)
continue;
//如果模式指针递增了模式的长度那么多次,说明比较成功,返回指针
return beg-=failFunc.size();
}
else if (patPos)//根据next表信息调整模式串要比较的位置
patPos=nextTable(--patPos);
else
++beg;
}
return end;
}
我用微软的wingdi.h头文件测试,方法是读入后自加到1M以上,在里面找”IN HDC, IN UINT””PolyPolyline”这样的串若干次.
实测性能非常低,既比不过std::string::find,也比不过std::search.
于是我进行了第一次优化.像很多书本的作者正确指出的那样,一般的程序员对该优化的地方常常估计错误:
请看前面说的PAT[5]失败的地方,它跳转到PAT[2]开始比较,然而PAT[2]比较必定失败,为什么?因为PAT[5]==PAT[2]='c',PAT[5]失败当然PAT[2]也会失败,我的优化移除此类情况,也即next表:0 0 0 1 2 3 0 0优化后变为:0 0 0 0 0 3 0 0 .
兴冲冲的重新编译运行换来的却是些微的提升.显然这不是影响性能的地方.
分析良久后也没找到应该改进的地方,因为std::search的代码比较平凡.最后抱着试试看的心理,把代码替换了:
template<class I>
I find(I beg,I end)
{ …
beg=std::find(beg,end, PatChar[0]);
int patPos=0;
else if (patPos)
patPos=nextTable(--patPos);
else
{
beg=std::find(beg,end, PatChar[0]);
patPos=0;
}
}
return end;
}
带来了巨大的速度提升,使得KMP查找的速度大大提升,在gcc上比string.find快,在vs 2008比std::search快了(恩,换句话说就是比gcc的std::search慢,比vs 2008的string.find慢...)
恩,总算发现性能低下的真正原因了:在一大块文本中找少量匹配的文本,最好是先滤掉不匹配的.对于不匹配的情况,std::find需要的指令更少;因此先用它来跳过不匹配的字符后在进入KMP比较算法的核心会带来可观的速度提升.
那么接下来还有什么高级手段使得KMP算法大大改进吗?我尝试了很久.然而很遗憾,没有什么再值得庆祝的优化了:它们增加了10倍的烦恼,换来一点点的性能提升.比方说:对于PAT=”abcabcde”,它的前置串”abcab”的next值都为0,意味着可以先提前用简单的代码去比较”abcab”，一旦比较失败又继续从失败处开始找而不需要去查看next表.因此我的实际代码是用findFront_代替了std::find来干这事.这让KMP算法提升了一点点性能,付出了n天思考和除错的时间.
最终的成型算法是这样的结果:比gcc自带的string::find要快,偶尔(通过对比较文本串的大小和比较次数调整)快于gcc的std::search;比vs 2008的std::search快,被vs 2008的string::find秒杀....
结论:
1.简单的代码编译器容易优化.也适合现代处理器的预测执行技术和cache.
2.日常用的要查找的字符串不会有多少适合KMP查找:”abcabcabcabc”的next表是什么值?优化后应该全为0!我对着wingdi.h看了几遍才找到了像”WINGDIAPI BOOL WINAPI”,”PATPAINT”这些歪瓜劣枣,它们的next表优化后也只有一两个地方有值.KMP算法应该适用在文本中大量字符串重复且要找的子串也自身重复的情况.
3.去实现KMP查找不如用std::search.
代码下载
花絮:
gcc的string::find很低效;因为它们就是用char_trait的eq一个个去找,vs2008的是用memchr先找到一个再去比较整个串.也许unix世界习惯了用正则库根本不怎么用标准库自带的.
不过gcc的string::find低效是相对自己的其它库函数而言.它编译的测试代码普遍比vs2008的快上一倍以上.
vs2008的std::search比较低效;就是平凡地一个字符一个字符对比;而gcc的std::search先用std::find找到第一个相等的字符后再去比较整个串.(看这里和string::find情况反过来了)
vs2008的std::find很平凡,只是对char的情况特化成memchr;gcc的find对随机迭代器做了优化,循环展开成4个4个地比较.
测试环境:xp sp3
Cpu:amd 5000超频到2.7G
内存:ddr2 2G.