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

陳天一 鄭聞悅 鄒健 邱修峰

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

關鍵詞：KMP算法 ?字符串 ?查找匹配 ?主串 ?子串

中圖分類號：TP31 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2019）08（b）-0242-02

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

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

1 ?原始KMP算法的過程

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

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

（l）若當前字符匹配成功，即Si=Pj，則繼續往右匹配下一個字符，即對Si+1和Pj+1進行匹配檢測。

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

經判斷，KMP算法的時間復雜度為O（m+n），空間復雜度為O（m）。

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

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

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

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

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

3 ?結果分析

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

4 ?結語

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

參考文獻

[1] 蔡婷，楊衛帥.一種改進的字符串模式匹配算法[J].物聯網技術，2017，7（7）：89-91，95.

[2] 邵嵐，唐永群，孔令順.一種基于KMP算法思想的字符串匹配算法的研究與實現[J].網絡安全技術與應用，2018（12）：61-67.

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