基于文本挖掘的語詞典研究

嚴建軍，彭 雯

（江西理工大學（南昌校區），江西 南昌 330013）

1 文本挖掘

隨著計算機網絡技術的不斷進步，人類對未知領域的探索逐步從最開始的想象轉變為通過各項技術實際解決問題，其中，文本挖掘就是人們研究未知領域的一個熱門方向。所謂文本挖掘，指的就是從文本數據中獲取有價值的信息和知識，是數據挖掘的一種方法。文本挖掘最重要、最基本的運用是實現文本的分類與聚類，前者是有監督的挖掘算法，后者是無監督的挖掘算法[1]。

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

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

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

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

2 模型的建立與問題解決

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

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

（3）字符串的劃分。

首先，鴿巢原理。若將一個字符串r劃分成X個分塊，存在替換距離D(r,s)為&的情況下，則滿足字符串r與另一個字符串s相似，字符串s中必然包括與字符串r的分塊相匹配的子串。所以，若已知字符串r,s以及容錯值&，當字符串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，和一個正整數n，即用長度為n的窗口在字符串r上滑動，從首字母到末尾得到一組長度為n的字符串，該組字符串即為字符串r的一個N-gram的集合，記為G(n,r)。例如：字符串r：abcdfghije, n=2，則字符串r的2-gram的集合為{ab,cd,fg,hi,je}。最后，對字符串的過濾（基于劃分原理之上）。第一，倒排索引：根據屬性的值來查找記錄，在索引列表中每一項都包含一個屬性值和地址，用屬性值來確定記錄的位置，而不是用記錄來確定屬性值，故稱為倒排索引。倒排索引由關鍵字（索引項）和出現情況兩部分（索引項所對應的二元組列表）組成，本文用N-gram代表關鍵字來記錄信息。例如：對字符串r建立倒排索引，先將字符串r作N-gram處理，取出其中的關鍵字，將含有N-gram的字符串編號放入相應的倒排索引列表中。第二，劃分過濾：對于當前正在訪問的長度為|s|的字符串s，根據字符串r的索引列表，可判斷索引列表中的字符串是否與s相似，若相似，則s中必包含一個字串與r的索引列表中的一個劃分塊相匹配。

3 驗證框架

3.1 倒排索引的構造

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

3.2 字符串top-k的相似順序型搜索的構造

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

4 算法實施與實例驗證

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

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

5 結語

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