基于語義指紋的海量文本快速相似檢測算法研究

姜雪　萬正景　梁燕　陶以政

摘要：相似檢測算法在海量文本信息處理中具有廣泛的應用，尤其是Simhash算法因其指紋局部敏感特性、檢測效率高在文本查重、網(wǎng)頁檢測等大規(guī)模數(shù)據(jù)處理中都十分常見。針對傳統(tǒng)Simhash算法無法支持近義詞、多義詞等自然語言處理上的語義問題，通過對現(xiàn)有同義詞擴展方案的研究，提出基于語義指紋的相似檢測算法。在Simhash算法基礎上，融入同義詞擴展編碼信息，生成文本語義指紋進行匹配檢測，以提高文本相似度檢測性能。另外，根據(jù)文本語義指紋建立多層分段索引，實現(xiàn)在海量文本信息中快速匹配出相似文檔。通過與傳統(tǒng)的Simhash算法進行實驗對比，體現(xiàn)出該方法在準確率、效率等方面的優(yōu)勢。

關鍵詞：文本相似；語義指紋；Simhash；同義詞擴展；互信息

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2016）36-0175-03

Research on Fast Duplicate Detection Algorithm for Massive Documents Based on Semantic Fingerprints

JIANG Xue，WAN Zheng-jing，LIANG Yan，TAO Yi-zheng

（Institute of Computer Application， China Academy of Engineering Physics， Mianyang 621900， China）

Abstract： Simhash algorithm is widely used in large-scale data processing， such as document duplication detection or web page ， because of its local sensitive characteristics and high efficiency. In terms of the problem that traditional Simhash algorithm can not support the semantic analysis of natural language processing such as synonyms or polysemous words， a similarity detection algorithm based on semantic fingerprint is proposed by studying the existing synonym expansion scheme. On the basis of Simhash algorithm， the semantic fingerprints are generated by matching synonyms to improve the performance of text similarity detection. In addition， establishing multi-level segment indexes based on the text semantic fingerprints can aggregation the similar documents in the mass document data quickly. Compared with the traditional Simhash algorithm， this method shows the advantages in terms of accuracy， efficiency and so on.

Key words：document similarity； semantic fingerprint； simhash； synonym expansion； mutual information

1 概述

在這個海量信息充斥的時代，信息的重復也隨之增多，而其中一些相似文本的出現(xiàn)不僅不能豐富信息的價值，反而造成資源的浪費。因此，如何在大規(guī)模數(shù)據(jù)中快速檢測出這些相似的文檔是一項十分重要的技術。目前，國內、外在該領域的檢測手段普遍都采用將文本哈希成數(shù)字指紋的技術。特別是Simhash算法，由于其檢測準確率高，“降維”的思想使得檢測速度快，同時還可以根據(jù)指紋距離反映文本內容的差異程度，因此受到廣泛的應用。但由于中文語義的復雜性，包括同義詞，一詞多義等問題，現(xiàn)有Simhash算法對于不同文檔采用同義詞作為關鍵字的相似檢測性能并不是很理想。例如，兩篇文檔的關鍵詞分別為：大規(guī)模、文檔、去重、技術和海量、文本、查重、算法。

基于上述原因，本文在現(xiàn)有Simhash算法的基礎上，通過對其進行改進，提出一種基于同義詞擴展編碼的語義指紋生成方法，實現(xiàn)海量文本的快速相似檢測。該方法利用基于同義詞詞典的語義擴展編碼，通過Simhash函數(shù)映射生成固定長度的語義指紋，解決了其中普通哈希函數(shù)無法進行語義表達的問題，擴展了指紋的表達能力，提升了檢測準確率。再根據(jù)指紋信息進行分段索引建立，減少了比對過程中的冗余操作，提高整體檢測效率。通過實驗驗證，該算法在海量文本相似檢測過程中性能良好，其快速匹配機制也滿足了大數(shù)據(jù)環(huán)境下的檢測需求。

2 相關工作

2.1 Simhash算法

Simhash算法在2002年由Charikar[1]提出，后由Manku對其進行擴展研究，被認為是當前文本相似檢測處理中最有效的算法之一[2]。Simhash算法實質上是一種具有局部敏感特征的哈希算法，它能夠將文本內容特征向量映射到一個指定維度的二進制比特向量上，并由這個二進制哈希值來表示文本內容的數(shù)字指紋（ Digital Fingerprint） 。區(qū)別于其他哈希算法，Simhash不僅在保證低碰撞率的條件下通過哈希映射將原本不同的文本內容映射到不同的哈?？臻g中，同時還能通過比特位數(shù)的不同體現(xiàn)兩個比較文本的相似性，這也正是其局部敏感特性的體現(xiàn)。根據(jù)局部敏感哈希算法（Local Sensitive Hashing，LSH）的基本思想[3]，兩篇文本p，q相似的可能性與其距離呈負相關關系，即它們之間的距離越小，相似的可能性就越高，反之，則相似的可能性就越低。這里我們定義Simhash函數(shù)h，則映射后h（p），h（q）與其距離的關系滿足以下兩個局部敏感性質（公式1）：

[If||p-q||≤R，thenPrH（h（p）=h（q））≥P1If||p-q||≥cR，thenPrH（h（p）=h（q））≤P2] （1）

這里參數(shù)c>1，概率P1>P2，p與q的距離也就是我們所需計算的文本相似度，h（p），h（q）的距離由二者的漢明距離來確定。兩篇文檔的相似性計算經(jīng)過哈希映射后，轉化為兩篇文本的指紋值漢明距離計算。

基于Simhash的相似文本檢測需要經(jīng)過文本特征提取、指紋生成和指紋索引匹配三個數(shù)據(jù)處理過程。首先，算法以經(jīng)過分詞的文檔詞項作為文檔的特征，其對應的頻率作為每個特征的權值wi。通過普通的hash函數(shù)計算得到每個分詞的一個f位的二進制哈希值，再將所有特征的哈希值加權累加，得到一個同樣為f位的總向量V，根據(jù)V中各位的符號生成文檔的數(shù)字指紋F。最后根據(jù)指紋的索引值指紋庫中進行比對，找到滿足一定條件的其他指紋作為相似比對結果。

2.2同義詞詞林

在信息檢索領域，將關鍵詞進行同義詞擴展實現(xiàn)模糊檢索，這類方案目前已有一定研究[4][5][6]一般地，通過同義詞挖掘算法事先建立同義詞詞庫，再運用該詞庫對檢索關鍵詞進行語義擴展，生成一個擴展關鍵詞集合。在檢索時，根據(jù)集合內的關鍵詞生成索引，依據(jù)索引進行查詢比對。在本文中，需要對關鍵詞的語義進行同義詞概念的擴展，把從屬于某一概念下的同義詞和關聯(lián)詞均劃歸到該概念下的集合中，并以該集合的編碼作為語義編碼返回處理。

同義詞的擴展是以同義詞詞典作為基礎進行操作，而“同義詞詞林”作為其中一個具有代表性的中文詞典，在中文自然語言處理領域受到廣泛關注。在詞林中，將所有詞匯按照樹狀結構分層地組織到其中，樹中的每個結點代表一個概念域。自頂向下整個詞林樹共有5層，依次對應1到2個編碼進行標識，將各個標識排列后就形成詞元的編碼。詞林的層次與其分類相對應，而分類的原則是依據(jù)漢語語言特點，以詞義為主，兼顧詞類，充分體現(xiàn)詞義的聚集。

同義詞詞林依據(jù)“詞義為主，兼顧詞類”的原則，結合漢語語言本身的特點及其使用規(guī)則將收錄的所有詞語劃分為三個等級：其中大類共12個，中類94個，小類多達1428個。再向下根據(jù)詞義集中的原則劃分成3925個詞群并排列，每個詞群對應一個標題詞。最后按照以下三個原則劃分成最小的子群：一、詞義的細微差別；二、修辭色彩與使用范圍的不同；三、詞語結構的差異。其中第一個是主要的。

3 基于語義指紋的快速相似檢測算法

本文提出的文本相似檢測算法主要是基于經(jīng)典的Simhash 算法，而其主體思想是“降維”，通過將高維的文本特征向量映射成一個唯一的二進制指紋值，從而達到減少文本表示空間的作用。不同于其他指紋生成算法，Simhash算法可以將兩篇相似的文本映射到一個距離相對較近的低維特征空間中，通過在該空間中距離的大小判別兩個文本向量的相似程度。但由于中文語義的復雜性，包括同義詞，一詞多義等問題，現(xiàn)有Simhash算法對于不同文檔采用同義詞作為關鍵字的相似檢測性能并不是很理想。例如，兩篇文檔的關鍵詞分別為：大規(guī)模、文檔、去重、技術和海量、文本、查重、算法?；谏鲜鲈颍菊n題在現(xiàn)有Simhash指紋生成算法的基礎上，通過對其進行改進，提出一種基于同義詞擴展編碼的語義指紋生成方法。語義指紋的生成流程如圖1所示。

文本最終的語義指紋值是基于離散化的文本特征提取的結果，數(shù)據(jù)指紋間的漢明距離越接近，則代表文本的語義越相似。根據(jù)同義詞詞林在詞語組織上的層次架構，對待文本中的關鍵詞進行定位標識，在詞林層級結構樹中找到該關鍵詞所有義項所屬的層次，考慮到一詞多義的情況，一個詞的不同義項間可能差距較大，因此根據(jù)其上下文信息進行篩選，取最大概率的詞項所屬詞群編碼進行擴展。概率判定的指標主要基于該詞與其上下文詞匯的互信息。

[I（wx，wy）=wx∈Xwy∈Yp（wx，wy）logp（wx，wy）p（wx）p（wy）] （2）

一般地，在應用Simhash算法時，將劃分出的詞語作為文本的基本特征，再結合每一個詞語的詞頻作為其權重?？紤]到本課題算法中，文本塊的劃分以句子為單位，而各個單詞在一句話中出現(xiàn)的頻率區(qū)分度并不會很大，因此在本課題中特征的權值采用另一個指標——單詞的詞性。從詞性角度來說，名詞表征著文檔更多的特征，因此其權重應該最高，動詞次之，形容詞再次之，其余詞權重最低。

根據(jù)文本的特征向量信息生成文本語義指紋的算法如下：

輸入： 一個64維特征向量 V = {w1，w2…，wn}，其中 w1，w2，…，wn 分別是文本關鍵詞特征，其對應相對值分別為we1，we2，……wen；

輸出： 一個64位的二進制語義指紋 F = {f1，f2，…，fb}；

1） 初始化一組64位的二進制向量，其中一個向量F作為文本的語義指紋，其他向量用來存儲關鍵詞對應的同義詞擴展詞群編碼；

2） 將各個關鍵詞在同義詞詞林中找到對應多個詞項，并根據(jù)與前一個詞以及后一個詞互信息（公式2），計算該詞匯對應的詞群編碼，并轉換成64位二進制hash值；

3） 根據(jù)關鍵詞各位的hash值以及其標注詞性的權重進行調整。如果第i位為1，則將該詞hash值的第i位置為權值，如果為0，則將該位置為負權值；

4） 將所有詞向量的對應位進行求和運算，結果向量記為F；

5） 按照向量F各個位的正負確定語義指紋F的數(shù)值：如果F第i位為正，則指紋F的第i位置為1，反之，則置對應位為0。

這樣，就得到了經(jīng)過同義詞擴展后的文本特征hash值的加權綜合結果。

4 實驗驗證

4.1實驗數(shù)據(jù)及工具

由于漢語中沒有句子相似度檢索用的標準測試數(shù)據(jù)集，因此本實驗的數(shù)據(jù)是通過從搜狗語料庫網(wǎng)頁數(shù)據(jù)中進行處理得到。實驗所用語料為標準中文數(shù)據(jù)集SOGOU-T，從中選取800篇文檔作為基礎數(shù)據(jù)集，經(jīng)過本課題語義指紋生成算法處理后形成指紋存入數(shù)據(jù)庫中，作為相似檢測依據(jù)。測試文檔集中，其中一部分從基礎數(shù)據(jù)集中選取200篇，并作不同種類的修改，構成論文相似目標數(shù)據(jù)集。通過將本文算法和其他算法，包括經(jīng)典的詞頻統(tǒng)計算法，未改進的simhash算法進行比較。

文本處理過程中，采用ICTALAS中文分詞系統(tǒng)實現(xiàn)，該系統(tǒng)采用層疊隱馬模型，該工具具有 160 萬字/秒的高速處理能力，同時支持外文字母以及數(shù)字等的分詞處理和用戶自定義詞典的擴展，目前共收錄有392755個詞匯。

4.2 評價標準

本文采用傳統(tǒng)的準確率、召回率兩個關鍵指標來對本文提出的算法進行性能評價。假設在進行文本相似性檢測的實驗結果如表1所列，則其各參數(shù)的定義如下：

準確率：被檢測相似句子中實際相似句子所占的比例，衡量的是查準率；

[Precision=TP/（TP+FP）] （3）

召回率：實際相似句子中被檢測出的比例，衡量的是查全率；

[Recall=TP/（TP+TN）] （4）

4.3 實驗結果分析

通過上述流程介紹，下面進行實驗，對本文提出的相似度檢測算法進行驗證。實驗運行環(huán)境是CPU 為Intel（R） i5 3210 .2.50GHz，內存 4GB，操作系統(tǒng)為 windows8.1 64bit，采用Java 語言實現(xiàn)算法，并在My Eclipse上運行。

首先對算法運行情況進行分析。從整體流程上看，本文采用的相似檢測方法可以分為個主要步驟：文本的語句劃分及分詞處理、構建特征向量、文本語義指紋生成、指紋對比計算四個過程。

如圖2、圖3所示，本文算法的經(jīng)過加入同義詞替換等處理的測試文本，文本的準確率和召回率都達到80%以上。而相比之下，傳統(tǒng)simhash算法和詞頻統(tǒng)計算法的兩項指標都只有70%左右，通過圖2曲線的比較可以很直觀地發(fā)現(xiàn)本文算法在語義識別上準確率有很大提升。同時，由于簡化傳統(tǒng)simhash算法根據(jù)Tfidf來計算關鍵詞相對值的過程，本文算法在計算速度上也有一定提高，這與理論預期結果相一致。

5 結束語

針對傳統(tǒng)的Simhash算法無法處理中文文本信息中一詞多義、同義詞等語義問題，本文提出一種基于同義詞擴展詞群編碼的語義指紋改進算法，利用同義詞詞林中的語義項層次結構關系，對檢測文本中關鍵詞進行語義詞群的擴展，利用詞群中的關系信息來融合不同的同義詞，再通過基于詞性對關鍵詞權值的確定，生成具有語義信息的語義指紋。經(jīng)過與Simhash算法以及詞頻統(tǒng)計算法進行比對研究，實驗表明，本文中的算法能對相似文本實現(xiàn)快速去重，而且能夠保持較高的準確率、召回率以及F1值，彌補了其他算法在文本語義表達方面的不足，特別針對同義詞替換的情況。同時，在時間效率上，本文提出的算法相比原始simhash算法，節(jié)省了大量無意義的比較計算處理，總體上提高了檢測效率。

今后的研究目標是完善語料庫，不斷改進文本相似檢測算法，不僅考慮到詞匯對相似度計算的影響，同時挖掘更復雜情況如詞匯組合、語句結構修改等方面的檢測算法，力求在文本相似度計算中達到更高的準確度。

參考文獻：

[1] Moses S.Charikar. Similarity Estimation Techniques from Roundings Algorithms[R].ACM STOC`02. May，2002：19-21.

[2] Sadowski C， Levin G. Simhash： Hash-based similarity detection[R]. Technical report， Google，2007.

[3] Datar M， Immorlica N， Indyk P， et al. Locality sensitive hashing scheme based on p-stable distributions[R].In Proceedings of the ACM Symposium on Computational Geometry.2004.23-36.

[4] 田久樂，趙蔚.基于同義詞詞林的詞語相似度計算方法[J].吉林大學學報：信息科學版，2012，28（6）：602-608.

[5] 張繼東，劉萍.基于語料庫同義詞辨析的一般方法[J].解放軍外國語學院學報，2005，28（6）：49-52.

[6] 張敏，宋睿華，馬少平，等. 基于語義關系查詢擴展的文檔重構方法[J].計算機學報，2004，27（10）：1395-1401.