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.