龐 宇，張 倩，韓 凱，肖 彬

（北方工業(yè)大學(xué)信息學(xué)院，北京 100144）

隨著數(shù)據(jù)爆發(fā)時(shí)代的到來，復(fù)雜度高、冗余度高的數(shù)字化信息逐漸在各行各業(yè)帶來了問題。例如網(wǎng)頁上大量的相似性文檔使用戶無法精確獲取想查詢的信息，所需的巨大存儲(chǔ)空間也會(huì)影響文件處理效率并導(dǎo)致成本急劇增加。

在文本相似度計(jì)算方面，Simhash算法是目前比較準(zhǔn)確且高效的方法之一。其主要思想是降維，將高維的特征向量映射為一個(gè)F位的指紋，通過比較兩篇文本指紋的漢明距離來確定其相似度。文中就Simhash算法進(jìn)行研究和改進(jìn)，以期在保證Simhash算法本身高效性的前提下，優(yōu)化其效率和準(zhǔn)確率，并設(shè)計(jì)系統(tǒng)實(shí)現(xiàn)文本查重。

1 傳統(tǒng)Simhash算法分析

Simhash算法中，定義一個(gè)N維空間，在其中定義每個(gè)特征向量，然后結(jié)合向量本身的權(quán)值進(jìn)行加權(quán)、求和等過程，得出一個(gè)和向量作為結(jié)果，最后對(duì)其進(jìn)行降維處理，形成最終的F位二進(jìn)制簽名。其具體步驟如下：

（1）分詞及預(yù)處理：將文本分詞且去掉停用詞，形成單詞序列，并為每個(gè)詞加上權(quán)值（weight）。

（2）生成hash值：通過hash算法把每個(gè)詞變成hash值，此為降維過程。

（3）加權(quán)：根據(jù)hash值，按照單詞的權(quán)值形成加權(quán)數(shù)字串，1為weight，0為-weight。

（4）合并：將各單詞計(jì)算出的序列值累加，形成一個(gè)序列串。

（5）降維：將上述序列串轉(zhuǎn)換為01串，大于0記為1，小于0記為0。

算法流程如圖1所示。

圖1 Simhash指紋生成

在信息論中，漢明距離指的是，在一個(gè)碼組集合內(nèi)，兩個(gè)碼字對(duì)應(yīng)位碼元取值不同的位數(shù)。即d（x，y）=∑x[i]⊕y[i]。在本例中，兩個(gè)文本的Simhash指紋a，b，其漢明距離通過a XOR b運(yùn)算得出。

傳統(tǒng)Simhash算法通常將特征詞出現(xiàn)的次數(shù)設(shè)為其權(quán)值，這就易于造成信息丟失，降低最終指紋的準(zhǔn)確性。同時(shí)，它不表現(xiàn)出詞匯分布信息，關(guān)鍵特征詞順序變化后，指紋不受影響。

2 改進(jìn)的Simhash算法

為解決上述問題，本文使用TF-IDF算法計(jì)算權(quán)值。TF-IDF是一種統(tǒng)計(jì)學(xué)算法，其主要思想是：特征詞的權(quán)重與其在文件中出現(xiàn)的次數(shù)成正比，與其在語料庫中出現(xiàn)的頻率成反比。

特征詞tj在文本dk中的TF-IDF值記為tfidf（tj，dk），用tf（tj，dk）表示tj在文本dk中出現(xiàn)的頻率，記為

式中，分子表示特征詞tj在文本dk中出現(xiàn)的次數(shù)；分母表示文檔dk中所有特征詞的個(gè)數(shù)。

用idf（tj，dk）表示逆向文件頻率，記為

式中，分子表示文本庫中總文檔數(shù)；分母表示其中包含特征詞tj的所有文檔。

特 征 詞 的 權(quán) 值tfidf（tj，dk） = tf（tj，dk） * idf（tj）。因 此，TF-IDF算法可以有效過濾常見詞，保留重要詞。

3 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

本實(shí)驗(yàn)采用Django搭建web項(xiàng)目實(shí)現(xiàn)文本查重系統(tǒng)。系統(tǒng)劃分為3個(gè)功能模塊：文件格式轉(zhuǎn)換、文本相似比對(duì)、檢測(cè)結(jié)果查看。工作流描述如下：

（1）用戶上傳本地txt、word或pdf等文件格式的文本。

（2）服務(wù)器接收文件后統(tǒng)一轉(zhuǎn)換格式為txt。

（3）服務(wù)器將形成的txt文件輸入到模型中進(jìn)行查重。

（4）模型輸出分析結(jié)果返回給服務(wù)器。

（5）通過用戶設(shè)定的閾值顯示檢測(cè)報(bào)告。

在文件格式轉(zhuǎn)換模塊，需要將pdf、word格式的文本轉(zhuǎn)換為txt格式，利于文本查重時(shí)對(duì)文件的打開、讀取等操作。

文本比對(duì)模塊是本系統(tǒng)的核心功能。目標(biāo)文檔輸入后端已經(jīng)建立好的模型后，以自然段落為執(zhí)行單位，經(jīng)過預(yù)處理形成詞組，根據(jù)TF-IDF算法計(jì)算各詞的權(quán)值，再依次經(jīng)過Simhash算法中生成hash值、加權(quán)、合并、降維等過程，最終形成目標(biāo)文檔的Simhash指紋。經(jīng)過與已經(jīng)形成的庫文檔各指紋的對(duì)比，查找到與目標(biāo)文檔漢明距離最小的某庫文檔中的某段落，將其文本內(nèi)容添加到結(jié)果數(shù)組中，最后由服務(wù)器返回至瀏覽器，用戶此時(shí)可以查看生成的檢測(cè)報(bào)告。