算法書和數(shù)據(jù)結(jié)構(gòu)書對(duì) KMP算法多有介紹，稱只需對(duì)字符串掃描一遍不需回溯云云 .然而 ,它恐怕只應(yīng)該作為一種思想存在 ;用于實(shí)際的字符串查找并不理想 .要費(fèi)勁心血實(shí)現(xiàn)和優(yōu)化它 ,才能在特定的字符串上略微超過 (也可能略微遜過 )std::search.

?

　　KMP算法的基本思想,是利用需要匹配字符串的自身信息來避免回溯.(這里討論的算法是以C/C++為編程語言,因此下標(biāo)索引以0開始)?

　　例如:字符串PAT=”abcabcde”,里面第二段的abc和PAT開頭的字符是匹配的.

　　假如我們有個(gè)要查找的字符串TEXT=”abcabD...”,在比較到TEXT的'D'處(TEXT[5])也即到了PAT的第二個(gè)'c'(PAT[5])時(shí)比較失敗,一般的字符串查找又得從TEXT[1](即'b')開始查找PAT.而KMP算法知道PAT的第二段abc匹配自身的開頭字符串，它會(huì)對(duì)PAT存儲(chǔ)如下next表:0 0 0 1 2 3 0 0數(shù)字代表匹配失敗后應(yīng)該從PAT的第多少個(gè)位置開始比較.我們這里在PAT[5]處失敗,而前面的PAT[0...4]都比較成功,因此先看看PAT[5]的上一個(gè)成功位置的next信息:next[4]=2,這代表應(yīng)該從PAT[2]處重新開始比較(即說明有2個(gè)字符不需要比了),就不需要跳到TEXT[1]處重新啟動(dòng)查找,這時(shí)的PAT[0...1]為”ab”,TEXT的'D'的前面兩個(gè)也是”ab”,只需要開始比較TEXT[5]和PAT[2],KMP說的無回溯意義正是如此:不需要回溯TEXT的比較位置.如果PAT[2]又失敗了,next[1]=0.那么TEXT[5]與PAT[0]開始比較,不成功的話TEXT遞增到TEXT[6],一直遞增到成功為止,成功的話當(dāng)然PAT也開始遞增.

　　

偽碼如下:

template<class I>I find(I beg,I end){int patPos=0;while (beg!=end){if (*beg==PatChar[patPos]){//匹配時(shí)遞增文本和模式的指針. ++beg;if (++patPos!=sizePat)continue;//如果模式指針遞增了模式的長(zhǎng)度那么多次,說明比較成功,返回指針 return beg-=failFunc.size(); }else if (patPos)//根據(jù)next表信息調(diào)整模式串要比較的位置 patPos=nextTable(--patPos);else++beg;}return end;}

　　我用微軟的wingdi.h頭文件測(cè)試,方法是讀入后自加到1M以上,在里面找”IN HDC, IN UINT””PolyPolyline”這樣的串若干次.

　　實(shí)測(cè)性能非常低,既比不過std::string::find,也比不過std::search.

?

　　于是我進(jìn)行了第一次優(yōu)化.像很多書本的作者正確指出的那樣,一般的程序員對(duì)該優(yōu)化的地方常常估計(jì)錯(cuò)誤:

　　請(qǐng)看前面說的PAT[5]失敗的地方,它跳轉(zhuǎn)到PAT[2]開始比較,然而PAT[2]比較必定失敗,為什么?因?yàn)镻AT[5]==PAT[2]='c',PAT[5]失敗當(dāng)然PAT[2]也會(huì)失敗,我的優(yōu)化移除此類情況,也即next表:0 0 0 1 2 3 0 0優(yōu)化后變?yōu)?0 0 0 0 0 3 0 0 .

　　興沖沖的重新編譯運(yùn)行換來的卻是些微的提升.顯然這不是影響性能的地方.

?

　　分析良久后也沒找到應(yīng)該改進(jìn)的地方,因?yàn)閟td::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慢...)

?

　　恩,總算發(fā)現(xiàn)性能低下的真正原因了:在一大塊文本中找少量匹配的文本,最好是先濾掉不匹配的.對(duì)于不匹配的情況,std::find需要的指令更少;因此先用它來跳過不匹配的字符后在進(jìn)入KMP比較算法的核心會(huì)帶來可觀的速度提升.

?

　　那么接下來還有什么高級(jí)手段使得KMP算法大大改進(jìn)嗎?我嘗試了很久.然而很遺憾,沒有什么再值得慶祝的優(yōu)化了:它們?cè)黾恿?0倍的煩惱,換來一點(diǎn)點(diǎn)的性能提升.比方說:對(duì)于PAT=”abcabcde”,它的前置串”abcab”的next值都為0,意味著可以先提前用簡(jiǎn)單的代碼去比較”abcab”，一旦比較失敗又繼續(xù)從失敗處開始找而不需要去查看next表.因此我的實(shí)際代碼是用findFront_代替了std::find來干這事.這讓KMP算法提升了一點(diǎn)點(diǎn)性能,付出了n天思考和除錯(cuò)的時(shí)間.

?

　　最終的成型算法是這樣的結(jié)果:比gcc自帶的string::find要快,偶爾(通過對(duì)比較文本串的大小和比較次數(shù)調(diào)整)快于gcc的std::search;比vs 2008的std::search快,被vs 2008的string::find秒殺....

?

結(jié)論:

?1.簡(jiǎn)單的代碼編譯器容易優(yōu)化.也適合現(xiàn)代處理器的預(yù)測(cè)執(zhí)行技術(shù)和cache.

2.日常用的要查找的字符串不會(huì)有多少適合KMP查找:”abcabcabcabc”的next表是什么值?優(yōu)化后應(yīng)該全為0!我對(duì)著wingdi.h看了幾遍才找到了像”WINGDIAPI BOOL WINAPI”,”PATPAINT”這些歪瓜劣棗,它們的next表優(yōu)化后也只有一兩個(gè)地方有值.KMP算法應(yīng)該適用在文本中大量字符串重復(fù)且要找的子串也自身重復(fù)的情況.

3.去實(shí)現(xiàn)KMP查找不如用std::search.

花絮:

??? gcc的string::find很低效;因?yàn)樗鼈兙褪怯胏har_trait的eq一個(gè)個(gè)去找,vs2008的是用memchr先找到一個(gè)再去比較整個(gè)串.也許unix世界習(xí)慣了用正則庫根本不怎么用標(biāo)準(zhǔn)庫自帶的.

? 不過gcc的string::find低效是相對(duì)自己的其它庫函數(shù)而言.它編譯的測(cè)試代碼普遍比vs2008的快上一倍以上.

?? vs2008的std::search比較低效;就是平凡地一個(gè)字符一個(gè)字符對(duì)比;而gcc的std::search先用std::find找到第一個(gè)相等的字符后再去比較整個(gè)串.(看這里和string::find情況反過來了)

?? vs2008的std::find很平凡,只是對(duì)char的情況特化成memchr;gcc的find對(duì)隨機(jī)迭代器做了優(yōu)化,循環(huán)展開成4個(gè)4個(gè)地比較.

?

測(cè)試環(huán)境:xp sp3?

Cpu:amd 5000超頻到2.7G?

內(nèi)存:ddr2 2G.

回復(fù)：

1#

　　同意樓主的觀點(diǎn)。大體來說，
　　1.少量字符串，標(biāo)準(zhǔn)庫的執(zhí)行效率是最好的。
　　2.中等規(guī)模字符串，KMP 算法比較有優(yōu)勢(shì)。
　　3.大量字符串，BM 及其變種算法比較有優(yōu)勢(shì)。
　　這個(gè)是我對(duì)字符串精確匹配算法應(yīng)用的認(rèn)識(shí)。不對(duì)之處，還請(qǐng)指教。

2#

glibc中用SSE4.2指令集優(yōu)化的KMP算法，號(hào)稱最快可以比c的strstr函數(shù)加速10倍。

總結(jié)

以上是生活随笔為你收集整理的KMP 算法并非字符串查找的优化 [转]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。