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

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

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

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

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

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

分組指紋；細(xì)粒度；文檔相似性檢測(cè)；海明距離

0 引言

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

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

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

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

1 系統(tǒng)架構(gòu)

1.1 系統(tǒng)目標(biāo)

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

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

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

1.2 系統(tǒng)功能結(jié)構(gòu)

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

圖2 功能結(jié)構(gòu)圖Fig.2Functional block diagram

1）文檔預(yù)處理

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

2）相似度計(jì)算

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

相似率計(jì)算。每篇文檔相當(dāng)于一個(gè)“句子”集合。每個(gè)“句子”通過分組指紋索引，可以快速檢索到相似的“句子”，采集相似證據(jù)并以相應(yīng)的XML結(jié)構(gòu)存儲(chǔ)。

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

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

著色比對(duì)。通過XML的解析，將當(dāng)前待查文檔的相似信息高亮著色，同時(shí)對(duì)于兩個(gè)相似性較高的文檔進(jìn)行著色比對(duì)。

1.3 系統(tǒng)拓?fù)浣Y(jié)構(gòu)

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

圖3 拓?fù)浣Y(jié)構(gòu)圖Fig.3The topological structure

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

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

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

2 系統(tǒng)關(guān)鍵技術(shù)

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

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

2.1 確定檢測(cè)粒度

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

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

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

2.2 建立細(xì)粒度分組指紋索引

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

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

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

式中fn,s,k為第n個(gè)文檔的第s個(gè)句子對(duì)應(yīng)的第k位海明碼。

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

2.3 檢索相似性

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

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

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

查詢條件（2）的時(shí)間復(fù)雜度是

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

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

2.4 系統(tǒng)界面

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

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

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

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

3 結(jié)語(yǔ)

Minwise Hash算法廣泛應(yīng)用于文本相似度檢測(cè)。因此，針對(duì)基金項(xiàng)目相似性檢測(cè)問題，在b位Minwise Hash算法的基礎(chǔ)上，本文提出了一種細(xì)粒度文檔相似性快速檢測(cè)方法。該方法采用b位Minwise Hash算法進(jìn)行相似度估值，生成特征指紋，并將相似度搜索問題轉(zhuǎn)換為海明距離搜索問題，建立了分組指紋索引，靈活運(yùn)用XML文檔來保存相似證據(jù)。實(shí)驗(yàn)結(jié)果表明了該系統(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)分?jǐn)?shù)位minwise哈希算法的研究[J].計(jì)算機(jī)科學(xué)，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].計(jì)算機(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].上海交通大學(xué)學(xué)報(bào)，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.

（責(zé)任編輯：鄧彬）

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

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

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

袁鑫攀（1982-），男，湖南株洲人，湖南工業(yè)大學(xué)教師，博士，主要研究方向?yàn)樾畔z索和數(shù)據(jù)挖掘，E-mail：xpyuanfly@163.com