季傳靈 江西理工大學

1 引言

在所給定的大量外星語的樣本文本，該文本語言只由20 個字母組成，無法知道該語言的具體含義。假設在所有的分段文本中，部分序列都會出現(xiàn)，以英文構(gòu)詞作為依據(jù)，很可能這些重復出現(xiàn)的片段是具有具體含義。在記錄的過程中，就會發(fā)生一些錯誤，在只考慮替換錯誤的情況下，要設計合理的數(shù)學模型，實現(xiàn)對符合要求的字母片段的查找，以較快的速度找到較多的片段。針對本題中的問題，將每段長度在5000-8000 字母的30 段文本中，找到長度在15-21 字母片段，并且該片段在每段文本中都有出現(xiàn)。

2 模型假設

(1）假定記錄文本錯誤中只有替換錯誤，且不會出現(xiàn)超過4 個字母的錯誤

(2）假設所要查找的字母片段，在所有的文本中，每次都會出現(xiàn)

3 問題分析

先要獲得只由20 個字母構(gòu)成的30 段5000-8000 個字母的文本，將文本進行分詞處理，再讓每個文本進行匹配，在錯誤允許的范圍內(nèi)每個文本所都出現(xiàn)的片段就是我們要查找的。將所建立的數(shù)學模型和編寫的算法，對文本進行處理。在得到較好的效果后，對算法進行優(yōu)化，提高算法的效率，對30 段文本以外的樣本進行處理，要達到較快的速度得到較多的片段的效果。

4 模型的建立與求解

4.1 Simhash1 算法的介紹與不足

基于Sim Hash 指紋的近似文本檢測是主流的檢測方法之一，能將一個文檔，最后轉(zhuǎn)換成一個64 位的字節(jié)，稱之為特征字，可根據(jù)文檔間的特征字的距離是不超過n，就可以判斷兩個文檔是否相似。通過查閱大量的文獻資料，該算法有以下幾點不足：

1.Simhash 的hash 值變化敏感，任一字母的微小變動即引起hash 值的巨大變化

2.指紋位數(shù)單一, 故導致其會丟失一定量的信息

3.Simhash 算法適用于在文本相似度較高的情況下，但當文檔數(shù)據(jù)量較多時則效果較差

4.2 基于編輯距離模糊匹配2和KMP非線性跳轉(zhuǎn)移位的綜合算法

4.2.1 算法建立

步驟一：取第一段文本，將所有的數(shù)據(jù)映射為一個數(shù)組的數(shù)據(jù)結(jié)構(gòu)，以6 個單詞為間距對文本進行平移連續(xù)切詞，每隔一個字母移動一次，得到一個切詞a[i](0 ＜= i ＜= 5000)，所以能得到5000 左右的片段；同理將第二段的文本也按此法進行切詞得到b[j](0 ＜= j ＜= 5000)。

用偽代碼描述如下：

a[i]={"第一段火星文"};

for(i=0; i++; i＜=5005)

{

片段i：A[i]={a[i]～a[i+5]};

}

步驟二：將步驟一中的切詞與余下29 段文本分別進行編輯距離的模糊匹配；此模糊匹配分為兩步：（1）非線性跳轉(zhuǎn)移位；（2）利用編輯距離算法進行模糊匹配；

4.3 編輯距離算法的定義及步驟

編輯距離算法是根據(jù)二個字符串的差異程度的檢測，檢測方式是計算將一個字符串變成另一個字符串的最少操作次數(shù)。

編輯距離算法步驟：

a.先將第一個文本段的第一個字母片段a[0]與第二段所得的第一個切詞b[0]進行模糊匹配，計算其匹配度。

b.將a[0]與b[i]相匹配，且匹配度符合容錯率3k ≤2，則將a[0]與余下的28 段的字母片段相比較；若a[0]與b 段中的字母片段匹配時，匹配度不符合其容錯率，則將a[0]片段丟棄；

c.當a[0]與剩余的字母片段相匹配時，都滿足匹配度符合容錯率k ≤2，a[0]就是我們所要找的片段；若a[0]與其中一段不匹配時，則停止匹配。將a 段的a[1]與余下的片段相匹配，重復步驟b;

d.在執(zhí)行完上述步驟之后，直到找到a[i]與其余的文本中的字母片段模糊匹配的匹配度符合容錯率k＜=2，則a[i]就是我們要找的片段。

5 模型的改進

針對前文提出的用KMP 來實現(xiàn)的非線性跳轉(zhuǎn)移位算法的不足之處，主要體現(xiàn)在其時間復雜度較大。如果某個字符匹配成功，模式串首字符的位置保持不動，僅僅是i++、j++；如果匹配失配，i 不變，模式串會跳過匹配過的next [j]4個字符。整個算法最壞的情況是，當模式串首字符位于i - j 的位置時才匹配成功，算法結(jié)束。

BM 算法5 是由Bob Boyer 和JStrother Moore 提出的，其基本思路是：首先設計一個數(shù)組bm Bc[]，如bm Bc[‘K’]（表示壞字符‘k’在所給的模式串中的最右邊所出現(xiàn)的位置與模式串末尾之間的長度），當匹配時遇到壞字符，所給的模式串要移動 shift(壞字符) = bm Bc[T[i]]-（m-1-i) 的距離，（T[i]是指在i 位置上的壞字符，(m-1-i)是指壞字符的位置與模式串末尾之間的長度），當壞字符位置與在模式串出現(xiàn)壞字符位置的距離為負時，模式串向后移動一位，重新開始匹配，因為有好后綴規(guī)則，移動時的距離選擇較大的。如圖 2 所示：

圖 2 bm 流程圖

改進方案為：在該題中，考慮本題每個片段可能有4 個字母替換錯誤的情況，我們可以先對要匹配的片段最后四位進行依次匹配，如果這四個后綴字母都不匹配，則放棄繼續(xù)匹配。此時再用BM 算法，即將最后一個后綴字母判為“壞字符”，然后將模塊字符直接移到壞字符后面一格，余下的所有片段按該步驟循環(huán)進行。

6 結(jié)束語

該模型是從第一段文本段取15-20 的字母片段，如果在余下的每一文本段里找到了一個符合題意的字母片段，放棄繼續(xù)匹配，但這樣最后得到的詞根不知道其在30 段文本中出現(xiàn)的頻率次數(shù)，所以數(shù)據(jù)利用價值不高，不太利于專家對外星語的研究。若將每一個字母片段賦予其權重，權重即是最后得到的詞根在30 段文本出現(xiàn)的頻率，使所得到的外星詞根按重要程度進行排列。