基于分組指紋的細粒度相似性檢測系統(tǒng)

盛鑫海，袁鑫攀，滿君豐，涂慧

（1. 湖南工業(yè)大學計算機與通信學院，湖南株洲412007；2. 中南大學信息科學與工程學院，湖南長沙410083）

基于分組指紋的細粒度相似性檢測系統(tǒng)

盛鑫海1，袁鑫攀1，滿君豐1，涂慧2

（1. 湖南工業(yè)大學計算機與通信學院，湖南株洲412007；2. 中南大學信息科學與工程學院，湖南長沙410083）

在文檔相似性檢測中，粗粒度會降低準確度，粒度過細又會大幅增加計算時間。針對基金項目相似性檢測，在b位Minwise Hash算法的基礎上，提出了一種細粒度文檔相似性快速檢測方法。先對文檔進行預處理，提取文檔正文，并生成分組指紋特征，再構建細粒度的分組指紋索引結構，利用海明距離來計算文檔之間的相似性，以XML文檔形式存儲并顯示相似信息。通過系統(tǒng)的實現(xiàn)，驗證了該方法的有效性，且檢索效率有所提高。

分組指紋；細粒度；文檔相似性檢測；海明距離

0 引言

隨著信息時代的發(fā)展，數(shù)字文檔（如基金項目申報文檔、論文文檔、網(wǎng)頁等）呈幾何級增長。由于數(shù)字文檔具有易復制性，這導致項目重復申請、論文抄襲、網(wǎng)頁重復等不良現(xiàn)象頻頻出現(xiàn)。大量相似文檔的存在也降低了信息檢索效率。因此，文檔之間相似性的精確檢測顯得尤為重要。

在文檔相似性檢測中，經(jīng)常出現(xiàn)一個文檔的內(nèi)容與另外一個或者多個文檔具有一定的相似程度。其中，不僅僅只有兩個文檔完全一致的情況，還存在一些其他的相似，例如對其它文檔的移位變換、重新組織文檔結構等。假設一個文檔F的內(nèi)容全部抄襲于文檔集S={S1, S2, …, Sn}，即F中的段落分別來源于文檔集S中的文檔，相當于文檔F由集合S中的S1, S2, …, Sn拼湊而成。這種由多篇文檔拼湊抄襲的現(xiàn)象是常見的。針對上述現(xiàn)象，若以文檔級別作為相似性檢測系統(tǒng)的檢測粒度，則無法檢測出文檔F存在的段落或句子級的重復情況。因此，對于文檔中的段落或者更加細粒度的句子的相似性檢測具有十分重要的意義。

Minwise Hash[1]算法作為目前主流的海量集合相似度估計算法，在信息檢索中得到廣泛應用[2-3]。在Minwise Hash算法的基礎上，學者們有了很多的理論創(chuàng)新。例如，b位Minwise Hash[4]算法降低了存儲空間和計算時間，提高了算法效率；分數(shù)位Minwise Hash算法[5]對各種精度和存儲空間需求有著更加廣泛的選擇性；連接位Minwise Hash算法[6]將位連接起來進行相似度度量，犧牲了算法5%的精度，卻能成倍地減少比對的次數(shù)，提升算法的性能。Minwise Hash算法還能應用于三者相似性檢測[7-8]、大型線性支持向量機[9]以及基于最大似然估計改進的估計[10]算法。

本文以檢測基金項目相似性為應用背景，以在海量數(shù)據(jù)環(huán)境中快速而準確地檢測出文檔的相似性為目的，提出了基于分組指紋的細粒度相似性檢測系統(tǒng)。該系統(tǒng)在b位Minwise Hash算法的基礎上，以“句子”細粒度來檢測文檔相似性。本文設計了檢測系統(tǒng)框架，構建以細粒度為基本元素的分組指紋索引結構，并采用XML通用結構化的標記語言[11]作為相似性證據(jù)的存儲結構。本文解決了系統(tǒng)的關鍵技術難點，為基金項目相似性檢測系統(tǒng)的工程應用提供了理論依據(jù)。

1 系統(tǒng)架構

1.1 系統(tǒng)目標

本文的研究目標是針對各類自然科學基金項目申請書的內(nèi)容特點，研究項目特征化與比對方法，開發(fā)能快速準確地發(fā)現(xiàn)抄襲、多頭申請和多次申請的申請書相似度檢測系統(tǒng)，解決基金項目形式審查中項目重復查證問題。以一份項目申報書作為查詢條件，在基于分組指紋的細粒度相似性檢測系統(tǒng)中進行相似度檢測。該檢測系統(tǒng)先從待檢測項目申報書中抽取細粒度的指紋特征，然后在海量項目指紋特征庫中進行檢索，找到滿足相似度閾值條件的項目文檔。

文檔相似性檢測模型如圖1所示。該模型包括：1）建立海量句子的分組指紋索引；2）提取待檢測申請書的特征指紋，形成細粒度的指紋特征，利用分組檢索算法檢索文檔相似性；3）對相似性項目的重復證據(jù)能夠記錄并呈現(xiàn)。

圖1 文檔相似性檢測模型Fig.1Document similarity detection model

1.2 系統(tǒng)功能結構

系統(tǒng)功能模塊可以劃分為文檔預處理、相似性計算與相似性證據(jù)顯示3大模塊，如圖2所示。

圖2 功能結構圖Fig.2Functional block diagram

1）文檔預處理

系統(tǒng)先提取待檢測文檔的正文（支持Word和PDF2種格式），再生成分組指紋特征。生成分組指紋特征的具體步驟為：將提取的文檔正文按照文章結構劃分段落，將每一個段落劃分成為“句子”的組合，對“句子”進行分詞，提取shingle，計算句子的b位Minwise Hash指紋。

2）相似度計算

索引建立。對每個“句子”的特征建立分組指紋索引。本文采用Lucene來建立索引，因為實驗證明Lucene建立的索引，檢索的速度更快。假設指紋特征存儲在Oracle數(shù)據(jù)庫，將k=64位指紋進行分組，分為m=6組（11,11,11,11,11,10）。分組數(shù)m勢必比海明距離閾值rh大，令c=m-rh。若每個分組命名為{A1, A2, A3, A4, A5, A6}，分別對6個分組指紋建立m=6個B+樹索引，該算法的時間復雜度為O(log(n))。

相似率計算。每篇文檔相當于一個“句子”集合。每個“句子”通過分組指紋索引，可以快速檢索到相似的“句子”，采集相似證據(jù)并以相應的XML結構存儲。

3）相似度證據(jù)顯示

XML解析。根據(jù)不同的證據(jù)顯示模式，解析存儲相似性證據(jù)的XML文檔，再顯示獲取的相似性信息。

著色比對。通過XML的解析，將當前待查文檔的相似信息高亮著色，同時對于兩個相似性較高的文檔進行著色比對。

1.3 系統(tǒng)拓撲結構

系統(tǒng)的拓撲結構如圖3所示。用戶上傳待查文檔，經(jīng)過Web Http服務傳輸?shù)綑z測引擎，建立“句子”細粒度待查索引，檢測完畢后，顯示文檔相似性結果。

圖3 拓撲結構圖Fig.3The topological structure

1.4 數(shù)據(jù)處理流程

系統(tǒng)的數(shù)據(jù)處理流程如圖4所示。后臺程序首先對數(shù)據(jù)源進行數(shù)據(jù)處理操作，從特征計算開始，進行細粒度指紋的提取，通過Lucene工具[12]構建細粒度“句子”指紋索引，利用指紋分組快速檢測相似度，并采集相似性證據(jù)，以XML格式結構進行存儲；前臺程序則解析XML文檔，展示相似性證據(jù)。

圖4 數(shù)據(jù)處理流程圖Fig.4The flow chart of data processing

2 系統(tǒng)關鍵技術

本文主要研究了文檔的提取、特征化、低復雜性的指紋化、細粒度分組指紋檢索算法、高效的比對技術和良好的相似性檢索結果界面呈現(xiàn)等關鍵技術，如圖5所示。

圖5 系統(tǒng)關鍵技術Fig.5The key technology of system

2.1 確定檢測粒度

細粒度文檔相似性檢測通常是先將文檔切割為多個自定義長度的文本塊集合，再通過相關檢索，計算并獲取每個文本塊與文本集合中的文本的相似程度。如果文本塊的長度選擇過大，則計算準確度不高，容易遺漏多方抄襲部分內(nèi)容的情況。如果文本塊長度選擇太小，就容易造成算法時間和算法空間的開銷過大。

在文檔切割的過程中，通常會按照自然段對文檔進行初步劃分，這是由于自然段可以表達作者相對完整的思想。另一方面，大部分抄襲者也都選擇以段落或長句為單位進行抄襲。然而，文檔中也常出現(xiàn)一些很長的自然段，完全基于自然段落的劃分會降低檢測精度。本文將自然段落切分為150字符左右的“句子”，將“句子”作為檢測單元粒度。對于特殊的獨句段和短句段等，不進行相似性的檢測。因為這類段落通常具有較高的同義性，使用頻度也很高，在文章中一般具有起承轉合作用，與文檔的實際內(nèi)容無關。檢測粒度劃分流程如圖6所示。

圖6 確定檢測粒度流程圖Fig.6The flow chart of detection granularity

2.2 建立細粒度分組指紋索引

實際上，文檔相似性檢測就是檢測與具有s個“句子”的文檔D′相似度在海明距離范圍內(nèi)的文檔集合，即檢索文檔相似度R大于閾值rh的文檔集合。故文檔的相似性查詢問題轉換為：給定一個k位指紋的集合，查詢該集合中與指紋q的海明距離在rh以內(nèi)的指紋集合。例如：當k=100時，檢索文檔相似度大于80%的文檔集合，該集合為指紋海明距離在rh以內(nèi)的指紋集合。

令細粒度的檢測單位“句子”的指紋為k=100位的海明碼指紋（fi,1～fi,100），將100位指紋進行分組，分為m=5組{A, B, C, D, E}，各組的位數(shù)為（20, 20, 20, 20, 20, 20）[11]。具有s個長句的文檔D′可表示為

文檔數(shù)為n的文檔集M表示為

式中fn,s,k為第n個文檔的第s個句子對應的第k位海明碼。

為M定義向量VA, VB, VC, VD, VE，即

2.3 檢索相似性

將待查文檔分為“句子”的集合，然后提取“句子”的指紋，將其作為檢測的基本粒度單元，檢索每個待查“句子”與指紋庫的重復情況。設海明距離閾值rh為2，即100位中不得超過2位以上不同。檢索文檔相似性的具體步驟如下。

步驟1將待查文檔的“句子”指紋分組為{Aq, Bq, Cq, Dq, Eq}。從5組中選出2組，不同組合共有種。

步驟2分別在5個B+樹上執(zhí)行查詢條件式（2），執(zhí)行查詢條件后的候選集合為Set（Pre_Query）。

查詢條件（2）的時間復雜度是

由于候選集Set（Pre_Query）中的數(shù)量遠小于問題規(guī)模n，從而可以避免大量的海明距離計算。

步驟3對Set（Pre_Query）中的所有元素進行海明距離計算，將滿足海明距離小于rh的元素加入集合Set(Query) 中。

2.4 系統(tǒng)界面

相似性檢索界面如圖7所示。在檢索條件區(qū)域，用戶可以輸入申報書的時間、單位等信息進行查詢。分模塊相似率查詢區(qū)域中，可以對申報書進行多樣化的檢索，如申報書的項目基礎信息相似度、整體相似度、章節(jié)粒度的相似度等。計算結果按照相似度由大到小排序。點擊“詳細”按鈕，可以得到兩個文檔的詳細比對結果。

圖7 相似性檢索界面Fig.7The similarity retrieval interface

相似性證據(jù)界面如圖8所示。其中包括一對一直觀比對顯示以及一對多的抄襲證據(jù)顯示。

圖8 相似性證據(jù)顯示圖Fig.8Evidence of similarity

3 結語

Minwise Hash算法廣泛應用于文本相似度檢測。因此，針對基金項目相似性檢測問題，在b位Minwise Hash算法的基礎上，本文提出了一種細粒度文檔相似性快速檢測方法。該方法采用b位Minwise Hash算法進行相似度估值，生成特征指紋，并將相似度搜索問題轉換為海明距離搜索問題，建立了分組指紋索引，靈活運用XML文檔來保存相似證據(jù)。實驗結果表明了該系統(tǒng)的有效性。

[1]Broder A Z，Charikar M，F(xiàn)rieze A M，et al. Min-Wise Independent Permutations[J]. Journal of Computer Systems and Sciences，2000，60(3)：630-659.

[2]Feigenblat G，Porat E，Shiftan A. Exponential Time Improvement for Min-Wise Based Algorithms[C]// SODA’11 Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco： SIAM，2011：57-66.

[3]Kane D M，Nelson J，Woodruff D P. An Optimal Algorithm for the Distinct Elements Problem[C]// PODS’10 Proceedings of the Twenty-Ninth ACM SIGMODSIGACT-SIGART Symposium on Principles of Database Systems. New York：ACM，2010：41-52.

[4]Li Ping，Knig A C. b-Bit Minwise Hashing[C]// Proceedings of the 19th International Conference on World Wide Web. [S. l. ]：ACM，2010：671-680.

[5]袁鑫攀，龍軍，張祖平，等.最優(yōu)分數(shù)位minwise哈希算法的研究[J].計算機科學，2012，39(8)：182-185. Yuan Xinpan，Long Jun，Zhang Zuping，et al. Research on Optimal Fractional Bit Minwise Hashing[J]. Computer Science，2012，39(8)：182-185.

[6]袁鑫攀，龍軍，張祖平，等.連接位Minwise哈希算法的研究[J].計算機研究與發(fā)展，2013，50(4)：883-890. Yuan Xinpan，Long Jun，Zhang Zuping，et al. Connected Bit Minwise Hashing[J]. Journal of Compuer Research and Development，2013，50(4)：883-890.

[7]Li Ping，Knig A C，Gui W. b-Bit Minwise Hashing for Estimating Three-Way Similarities[C]//Neural Information Processing Systems (NIPS). Vancouver：[s. n.]，2010：1387-1395．

[8]袁鑫攀，盛鑫海，龍軍，等.基于連接位Minwise哈希的三者相似性度量算法[J].上海交通大學學報，2014，48(7)：936-941. Yuan Xinpan，Sheng Xinhai，Long Jun，et al. Connected Bit Minwise Hashing for Estimating Three-Way Similarities [J]. Journal of Shanghai Jiaotong University，2014，48(7)：936-941.

[9]Li Ping，Moore J，Knig A C. b-Bit Minwise Hashing for Large-Scale Linear SVM[J]. Neural Information Processing Systems ，2011：101-109.

[10]Li Ping，Knig A C. Accurate Estimators for Improving Minwise Hashing and b-Bit Minwise Hashing[R/OL]. [2014-06-27]. http://arxiv.org/pdf/1108.0895.pdf.

[11]Bray T，Paoli J. Sperberg-McQueen：Extensible Markup Language(XML) 1.0[R/OL]. [2014-03-27]. http://www. w3.org/TR/REC-xml/.

[12]Yuan Xinpan，Long Jun，Zhang Zuping，et al. Near-Duplicate Document Detection with Improved Similarity Measurement[J]. Journal of Central South University，2012，19(8)：2231-2237.

（責任編輯：鄧彬）

The Fine-Grained Similarity Detection System Based on Grouping Fingerprint

Sheng Xinhai1，Yuan Xinpan1，Man Junfeng1，Tu Hui2
（1. School of Computer and Communication，Hunan University of Technology，Zhuzhou Hunan 412007，China；2. School of Information Science and Engineering，Central South University，Changsha 410083，China）

In document similarity detection, coarse grain will reduce the accuracy and too small particle size will increase the computation time. Proposes a quick document similarity detection method based on b-bit Minwise Hash. Firstly extracts the document text to generate a grouping fingerprint features; Then establishes the index structure of finegrained grouping fingerprint; Finally computes the resemblance of document part by Hamming distance, and stores and displays the evidence of similarity by XML document format. Through system practice, verifies the effectiveness of the method and increases the efficiency of retrieval.

grouping fingerprint；fine-grained；document similarity detection；Hamming distance

TP391.3

A

1673-9833(2014)06-0081-05

10.3969/j.issn.1673-9833.2014.06.016

2014-09-25

國家自然科學基金資助項目(61350011, 61402165)，湖南省自然科學面上基金資助項目（14JJ2115, 2015JJ3058），湖南省教育廳科技研究基金資助項目（14C0325），湖南工業(yè)大學自然科學研究基金資助項目（2014HZX17）

盛鑫海（1987-），男，湖南岳陽人，湖南工業(yè)大學碩士生，主要研究方向為數(shù)據(jù)挖掘，E-mail：2213499@163.com

袁鑫攀（1982-），男，湖南株洲人，湖南工業(yè)大學教師，博士，主要研究方向為信息檢索和數(shù)據(jù)挖掘，E-mail：xpyuanfly@163.com