基于KMP算法的字符串查找匹配研究

陳天一 鄭聞悅 鄒健 邱修峰

摘 ? 要：目前，有學(xué)者提出了一種特殊的符號語言，了解到其文字是由20個字母組成。目前已獲得許多段由該語言寫成的文本，但缺少標(biāo)點符號與空格，導(dǎo)致無法理解其中的含義與規(guī)律。本文針對在不同段由特殊語言組成的文本中搜索在誤差允許范圍內(nèi)相同的字母序列片段問題，建立了基于KMP算法的相似字符串搜索匹配算法模型，在特定的多個文本中找出符合題意的子串，依據(jù)已知條件自定義模型生成外星語文本段落對該算法進(jìn)行檢驗，評判其優(yōu)缺點并進(jìn)一步優(yōu)化分析。

關(guān)鍵詞：KMP算法 ?字符串 ?查找匹配 ?主串 ?子串

中圖分類號：TP31 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A ? ? ? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2019）08（b）-0242-02

根據(jù)語言學(xué)家的猜測，在每段文本中都會出現(xiàn)的序列片段很可能具備某種固定的含義。因此，如何在不同段文本中搜索在誤差允許范圍內(nèi)相同的字母序列片段，將對該未知語言的研究提供重要的理論依據(jù)。

在不同段文本中搜索相同的字母序列片段可以通過字符串匹配算法來實現(xiàn)。這里我們基于使用較為普遍且高效的算法模型——KMP算法創(chuàng)建了相似字符串搜索匹配算法。此算法針對的是已知的字符串序列在文本串中進(jìn)行定位，而這里的序列片段是未知的。首先本文通過構(gòu)詞法組建出6000個包含15～21個字母的單詞，將其作為詞匯庫，之后規(guī)定1500個為高頻詞匯，另外4500個為低頻詞匯，分別以80%和20%的概率隨機(jī)抽選入30段文本中，形成我們所需的文本數(shù)據(jù)。在此基礎(chǔ)上，再使用相似字符串搜索匹配算法進(jìn)行主串與子串之間的匹配，得到分析結(jié)果。最后，我們對結(jié)果進(jìn)行了檢驗，評估模型的準(zhǔn)確度和高效性，同時針對算法中存在的問題提出了優(yōu)化與改進(jìn)措施。

1 ?原始KMP算法的過程

基于對不同段文本中相同的字母序列片段進(jìn)行查找，采用原始的KMP字符串匹配算法對不同文本中的字符串進(jìn)行匹配，具體流程如下。

假設(shè)現(xiàn)在文本串S（主串）匹配到i位置，模式串P（子串）匹配到j(luò)位置，即模式匹配過程執(zhí)行到比較字符Si和Pj，其中0≤i≤n-1，0≤j≤m-1。

（l）若當(dāng)前字符匹配成功，即Si=Pj，則繼續(xù)往右匹配下一個字符，即對Si+1和Pj+1進(jìn)行匹配檢測。

（2）若當(dāng)前字符匹配失敗，即Si≠Pj，此時當(dāng)j=0時，則對Si+1和Pj進(jìn)行匹配檢測，即把子串和主串向右移動一位再從子串的第一個字符進(jìn)行匹配;當(dāng)1≤j

經(jīng)判斷，KMP算法的時間復(fù)雜度為O（m+n），空間復(fù)雜度為O（m）。

2 ?建立相似字符串搜索匹配模型

我們首先采用KMP算法對生成的文本數(shù)據(jù)進(jìn)行了匹配，發(fā)現(xiàn)符合條件的字母序列數(shù)量非常少，由此進(jìn)行了相關(guān)分析，具體如下。

如圖1，進(jìn)行主串與字串的匹配，倘若目前主串匹配到2號位置，子串匹配到0號位置。假設(shè)容錯為4個字母，則大方框標(biāo)注出來的區(qū)域即是允許容錯的范圍。

如圖2，基于對前面過程的理解，主串S[2，3，4，5]與字串P[0，1，2，3]在容錯范圍內(nèi)可以進(jìn)行相互匹配，但當(dāng)主串i到達(dá)6號位置，字串j到達(dá)4號位置時，字母不匹配，超出容錯范圍，則匹配失敗。

如圖3，針對以上存在的問題，我們在KMP算法的基礎(chǔ)上加入了變異的概念，提出了以KMP為基礎(chǔ)的相似字符串搜索匹配模型以提高匹配的準(zhǔn)確度。在上述情況下，當(dāng)匹配失敗時，主串i返回3，子串j返回0進(jìn)行匹配，即令i=i-j+1。這樣，算法的準(zhǔn)確度會大大提高。

3 ?結(jié)果分析

我們定義了一個相似片段的概念，在這個相似片段中，我們匹配到的不是僅僅一個字符子串，而是一個字符片段。運(yùn)行算法，我們得到匹配結(jié)果。圖4內(nèi)容為程序運(yùn)行時匹配出來的一些相似片段，由于篇幅有限，未全部截取。通過這個相似片段我們可以發(fā)現(xiàn)在外星語中出現(xiàn)頻率高的子串。

4 ?結(jié)語

在此基礎(chǔ)上，本文更進(jìn)一步分析發(fā)現(xiàn)由于容錯性的存在，next數(shù)組不是解決相似字符串匹配問題的關(guān)鍵，由此提出了基于KMP的相似字符串搜索匹配模型，通過對主串進(jìn)行一定程度的回溯緩解現(xiàn)有KMP模型在相似字符串匹配問題上的不適用性，大大提高了算法的精確度。相比于KMP算法，該模型雖然準(zhǔn)確度得到了提高，但是由于主串回溯的原因提高了其時間復(fù)雜度。因此，在保證精確度的基礎(chǔ)上提高其運(yùn)行速度是該模型今后進(jìn)行優(yōu)化的關(guān)鍵。

參考文獻(xiàn)

[1] 蔡婷，楊衛(wèi)帥.一種改進(jìn)的字符串模式匹配算法[J].物聯(lián)網(wǎng)技術(shù)，2017，7（7）：89-91，95.

[2] 邵嵐，唐永群，孔令順.一種基于KMP算法思想的字符串匹配算法的研究與實現(xiàn)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2018（12）：61-67.

[3] 黃厚柱.相似字符串查找算法研究[D].安徽大學(xué)，2017.