陳天一 鄭聞悅 鄒健 邱修峰

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

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

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

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

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

1 ?原始KMP算法的過(guò)程

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

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

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

（2）若當(dāng)前字符匹配失敗，即Si≠Pj，此時(shí)當(dāng)j=0時(shí)，則對(duì)Si+1和Pj進(jìn)行匹配檢測(cè)，即把子串和主串向右移動(dòng)一位再?gòu)淖哟牡谝粋€(gè)字符進(jìn)行匹配;當(dāng)1≤j

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

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

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

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

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

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

3 ?結(jié)果分析

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

4 ?結(jié)語(yǔ)

在此基礎(chǔ)上，本文更進(jìn)一步分析發(fā)現(xiàn)由于容錯(cuò)性的存在，next數(shù)組不是解決相似字符串匹配問(wèn)題的關(guān)鍵，由此提出了基于KMP的相似字符串搜索匹配模型，通過(guò)對(duì)主串進(jìn)行一定程度的回溯緩解現(xiàn)有KMP模型在相似字符串匹配問(wèn)題上的不適用性，大大提高了算法的精確度。相比于KMP算法，該模型雖然準(zhǔn)確度得到了提高，但是由于主串回溯的原因提高了其時(shí)間復(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算法思想的字符串匹配算法的研究與實(shí)現(xiàn)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2018（12）：61-67.

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