嚴建軍，彭 雯

（江西理工大學(xué)（南昌校區(qū)），江西 南昌 330013）

1 文本挖掘

隨著計算機網(wǎng)絡(luò)技術(shù)的不斷進步，人類對未知領(lǐng)域的探索逐步從最開始的想象轉(zhuǎn)變?yōu)橥ㄟ^各項技術(shù)實際解決問題，其中，文本挖掘就是人們研究未知領(lǐng)域的一個熱門方向。所謂文本挖掘，指的就是從文本數(shù)據(jù)中獲取有價值的信息和知識，是數(shù)據(jù)挖掘的一種方法。文本挖掘最重要、最基本的運用是實現(xiàn)文本的分類與聚類，前者是有監(jiān)督的挖掘算法，后者是無監(jiān)督的挖掘算法[1]。

本文所研究詞典的文本是由20個字母構(gòu)成的全新未知語言，為此，從目前取得的30條文本（單個文本長度為5 000～8 000）中截取相同片段（長度為15～21），找到其共同特征，從而達到研究的目的。

由于記錄技術(shù)的限制，會存在部分語音的序列片段出現(xiàn)替換、插入和刪除錯誤。現(xiàn)只考慮替換錯誤，且容錯率在0～4之間，要求在30條文本中盡可能多地找到相同序列的片段，且容錯率不大于4。需要考慮的問題包括：（1）構(gòu)建文本模型，且單個長度為5 000～8 000。（2）運用相關(guān)原理找出相同序列的片段，并限制其長度為15～21。（3）定義變量，實現(xiàn)算法，并進行驗證。（4）以不同的算法與原有算法進行對比，對原有算法進行改進，使算法更優(yōu)。

首先，模型假設(shè)。為了簡化模型，對以下部分做出假設(shè)：未知的20個語言字母，用a～t 的20個小寫英文字母替代。取得的30條文本，由20個小寫字母通過隨機生成的方式構(gòu)成。長度為15～21的序列片段，在編纂算法時，可規(guī)定其長度為17。

其次，符號說明。r,s為兩個隨機生成的字符串，D(r,s)為替換距離，&為容錯值，D=D(r,s)為替換距離，τ為替換距離閾值[2]。

2 模型的建立與問題解決

（1）文本的生成。建立一個隨機生成算法系統(tǒng)，編纂算法，生成隨機數(shù)0～19，并與20個英文字母a～t相對應(yīng)，可建立一段符合要求的文本。

（2）總體變量的定義。給定兩個文本字符串集合，從兩個字符串集合中找到一對相似的字符串，稱作相似字符串對（r,s）。本文利用一對字符串容錯率不大于4，得出相似字符串，即文本中的相似片段。建立替換距離D(r,s),即將字符串r轉(zhuǎn)換成s所需改動的字符個數(shù)（只含替換錯誤）。當(dāng)兩個字符串相似時，給定其容錯值為&，&在0～4之間。

（3）字符串的劃分。

首先，鴿巢原理。若將一個字符串r劃分成X個分塊，存在替換距離D(r,s)為&的情況下，則滿足字符串r與另一個字符串s相似，字符串s中必然包括與字符串r的分塊相匹配的子串。所以，若已知字符串r,s以及容錯值&，當(dāng)字符串r被分為X個分塊，且s中包含與X個分塊中某個分塊相匹配的子串，則r與s可能相似，若進一步驗證替換距離D（r,s）為&，則r與s一定相似。反之，一定不相似，從而得到相似的字符片段。

其次，文本及字符串的劃分。第一，均勻劃分：已知一段文本或者字符串將其劃為X個分塊的種類有很多，本文只含字符串的替換錯誤，則對于字符串長度L滿足|r|=|s|，且L滿足字符串長度為15～21，即采用均勻劃分的方法。對于字符串長度為5 000～8 000的文本或者字符串長度為|r|的字符串，可將其劃分為X個分塊，則每個分塊的長度L為[|r|/X]或者[|r|/X]+1。例如：令X=3,|r|=16，可得分塊的長度為3或4，若該字符串為abcdefghijklmnop，可分為4個分塊，即{abc,def,ghi,jkl,mnop}。第二，N-gram：確定一個字符串r，和一個正整數(shù)n，即用長度為n的窗口在字符串r上滑動，從首字母到末尾得到一組長度為n的字符串，該組字符串即為字符串r的一個N-gram的集合，記為G(n,r)。例如：字符串r：abcdfghije, n=2，則字符串r的2-gram的集合為{ab,cd,fg,hi,je}。最后，對字符串的過濾（基于劃分原理之上）。第一，倒排索引：根據(jù)屬性的值來查找記錄，在索引列表中每一項都包含一個屬性值和地址，用屬性值來確定記錄的位置，而不是用記錄來確定屬性值，故稱為倒排索引。倒排索引由關(guān)鍵字（索引項）和出現(xiàn)情況兩部分（索引項所對應(yīng)的二元組列表）組成，本文用N-gram代表關(guān)鍵字來記錄信息。例如：對字符串r建立倒排索引，先將字符串r作N-gram處理，取出其中的關(guān)鍵字，將含有N-gram的字符串編號放入相應(yīng)的倒排索引列表中。第二，劃分過濾：對于當(dāng)前正在訪問的長度為|s|的字符串s，根據(jù)字符串r的索引列表，可判斷索引列表中的字符串是否與s相似，若相似，則s中必包含一個字串與r的索引列表中的一個劃分塊相匹配。

3 驗證框架

3.1 倒排索引的構(gòu)造

本文所采用的倒排索引由索引項和索引項相對應(yīng)的二元組列表構(gòu)成，其中，索引項為N-gram，即索引列表中的每一個元素為一個二元組，其中，p表示該N-gram在字符串標識為d的起始位置，字母d標識包含該N-gram的字符串。可以采用數(shù)據(jù)結(jié)構(gòu)組織倒排索引，每一個N-gram的數(shù)據(jù)類型為string，并將N-gram進行映射，具體如下：將N-gram作為一個string類型對待，采用map方式存儲倒排列表，其中，key為string類型的N-gram, value為根據(jù)倒排索引列表所對應(yīng)的數(shù)據(jù)結(jié)構(gòu)。

3.2 字符串top-k的相似順序型搜索的構(gòu)造

在倒排索引二元組的基礎(chǔ)上，首先，應(yīng)該定位到倒排列表中和s最近的位置的二元組；其次，從該位置上遍歷該倒排列表和查詢字符串r相似的字符串s，s和q公共的N-gram位置相差很小，如果實現(xiàn)定位到倒排列表中和s位置最近的二元組，從該位置上遍歷該倒排列表累計每個字符串和查詢字符串公共N-gram的數(shù)量，可以以更高的概率先獲得和查詢字符串最相近的字符串。

4 算法實施與實例驗證

（1）倒排索引構(gòu)造算法。變量定義為InvertedList：倒排索引列表；maxLen為字符串集合中的最大字符串長度。

（2）雙向過濾驗證算法。首先，將字符串中已經(jīng)匹配的部分進行對齊，在滿足長度過濾約束的條件下，計算R1與S1之間的D1，當(dāng)D1大于左邊部分的τ則終止計算。否則，繼續(xù)計算Rτ與Sτ之間的Dτ，Dτ大于右面部分的τ則終止計算。其次，求得Rmid和Smid之間的Dmid，若D1+Dτ+Dmid＞τ，則該字符串對被排除，否則，該字符串對被認定為相似字符串對。

5 結(jié)語

本文的實例分析主要是從3個方面對算法進行分析，即分析字符串長度與字符串相似個數(shù)的關(guān)系、替換距離與字符串相似個數(shù)的關(guān)系、替換距離與響應(yīng)時間的關(guān)系，再進行比較，從而改進算法。算法改進時，在原倒排索引算法的基礎(chǔ)上，插入雙向過濾算法的先遞減后遞增算法，提高算法的運行速度。采用top-k順序型搜索原理，并編纂算法，減少容錯率，盡可能多地得到相同序列的片段。