嚴(yán)建軍，彭 雯

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

1 文本挖掘

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

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

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

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

其次，符號(hào)說(shuō)明。r,s為兩個(gè)隨機(jī)生成的字符串，D(r,s)為替換距離，&為容錯(cuò)值，D=D(r,s)為替換距離，τ為替換距離閾值[2]。

2 模型的建立與問(wèn)題解決

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

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

（3）字符串的劃分。

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

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

3 驗(yàn)證框架

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

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

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

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

4 算法實(shí)施與實(shí)例驗(yàn)證

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

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

5 結(jié)語(yǔ)

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