基于SolrCloud的分布式相似性檢測系統(tǒng)

蔣佳洲　 北京師范大學(xué)株洲附屬學(xué)?！≈曛蕖?12000

基于SolrCloud的分布式相似性檢測系統(tǒng)

蔣佳洲 北京師范大學(xué)株洲附屬學(xué)校株洲412000

文檔相似性檢測中，很多文本的資源是碎片化存儲(chǔ)，實(shí)現(xiàn)全局的文本查重，在沒有統(tǒng)一管理的情況下，不可能短時(shí)間將數(shù)據(jù)集中，數(shù)據(jù)仍舊是分散存儲(chǔ)，為實(shí)現(xiàn)全局的檢查，采用基于SolrCloud的分布式查重。論文在b位Minwise Hash的基礎(chǔ)上，提出了彈性細(xì)粒度相似性檢測方法；通過分析多粒度特征提取的特點(diǎn)，設(shè)置項(xiàng)目模板進(jìn)行正則表達(dá)式匹配，提升了相似性檢索的效率，最后通過系統(tǒng)實(shí)現(xiàn)驗(yàn)證該系統(tǒng)的有效性。

SolrCloud；相似性檢測；哈希；分布式

0 引言

隨著信息時(shí)代的發(fā)展，數(shù)字文檔（如基金項(xiàng)目申報(bào)文檔，論文文檔，網(wǎng)頁等）呈幾何級(jí)數(shù)增長的同時(shí)，由于其本身的易復(fù)制性，導(dǎo)致項(xiàng)目重復(fù)申請(qǐng)，論文抄襲，網(wǎng)頁重復(fù)等不良現(xiàn)象頻頻出現(xiàn)；大量相似文檔的存在和數(shù)據(jù)孤島數(shù)量不斷的增加，也降低了信息檢索的效率和精度。在這種情況下，研究高性能的分布式相似性檢測系統(tǒng)顯得尤為重要。

Minwise Hash[1]算法作為目前主流的海量集合相似度估計(jì)算法，經(jīng)過不斷改進(jìn)[2]，在信息檢索中得到廣泛應(yīng)用[3]。Li等人[4]提出的b位Minwise Hash在Minwise Hash算法的基礎(chǔ)之上通過降低存儲(chǔ)空間和計(jì)算時(shí)間進(jìn)一步提高了算法的效率。同時(shí)，b位Minwise Hash也是對(duì)集合估計(jì)算法的一種理論創(chuàng)新，在三者相似性檢測[5]、大型線性支持向量機(jī)[6]以及基于最大似然估計(jì)的估計(jì)算法[7]等領(lǐng)域有了新的應(yīng)用發(fā)展[8]。論文在b位Minwise Hash的基礎(chǔ)上，提出了一種細(xì)粒度文檔相似性快速檢測方法，并將其應(yīng)用到分布式相似性檢測系統(tǒng)中，介紹它的系統(tǒng)框架、系統(tǒng)關(guān)鍵技術(shù)難點(diǎn)和解決方案以及軟件實(shí)際使用效果。

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

1.1基于SolrCloud的分布式系統(tǒng)

（1）SolrCloud是基于Solr和 ZooKeeper的分布式搜索方案。該方案具有集中配置、自動(dòng)容錯(cuò)、近實(shí)時(shí)搜索、負(fù)載均衡等特點(diǎn)。系統(tǒng)為滿足全局相似性檢查，基于SolrCloud提出一種分布式文檔相似檢測方案，較好解決跨數(shù)據(jù)源相似性檢測問題。這種分布式查重方式核心算法應(yīng)用了b位Minwise Hash，兼顧檢測的精度和效率，結(jié)合彈性細(xì)粒度，對(duì)各類數(shù)據(jù)進(jìn)行加工處理，準(zhǔn)確匹配各章節(jié)，將文檔最小原子鎖定到句子級(jí)，形成海量句子指紋庫；每個(gè)數(shù)據(jù)站點(diǎn)間的傳輸通道和統(tǒng)一的傳輸接口規(guī)范。

把所有的索引集合視為一個(gè)總索引庫，將總索引庫分為三個(gè)索引片，分別存放在三個(gè)站點(diǎn)，即為主索引庫，并且，考慮到平臺(tái)的健壯性，為每個(gè)索引片增設(shè)了一個(gè)備份，即為從索引庫。各個(gè)索引庫之間的聯(lián)系通過ZooKeeper提供的服務(wù)協(xié)調(diào)。

圖1　基于SolrCloud，ZooKeeper的檢測系統(tǒng)架構(gòu)圖

圖2　跨部門檢測模式

（2）聯(lián)盟式檢測的模式。如圖2所示，站點(diǎn)1是查重系統(tǒng)站點(diǎn)，主要進(jìn)行預(yù)處理數(shù)據(jù)，計(jì)算相似度。站點(diǎn)2和站點(diǎn)3主要是作為跨部門的數(shù)據(jù)采集點(diǎn)，在站點(diǎn)1需要的時(shí)候傳輸歷史數(shù)據(jù)至站點(diǎn)1，站點(diǎn)將獲得自身數(shù)據(jù)庫以外的待對(duì)比歷史庫，以期獲得更準(zhǔn)確的查重結(jié)果。

（3）數(shù)據(jù)的檢測流程。如圖3所示，包含以下兩個(gè)流程。

1）本地檢測：將待查庫的文本發(fā)給本地引擎，對(duì)文本中每個(gè)段落進(jìn)行計(jì)算相似性，檢索出相似的段落。

2）遠(yuǎn)程檢測：系統(tǒng)中站點(diǎn)表保存了所有站點(diǎn)的IP地址及端口。索引庫表保存了能夠訪問到的遠(yuǎn)程所有索引庫的信息。

圖3　檢測流程

在兩種檢測的基礎(chǔ)上實(shí)現(xiàn)跨站點(diǎn)檢測步驟：以與遠(yuǎn)程站點(diǎn)1的歷史庫1比對(duì)為例。

第一步：用戶選擇遠(yuǎn)程站點(diǎn)，系統(tǒng)訪問站點(diǎn)表，獲取遠(yuǎn)程站點(diǎn)1的IP。然后向遠(yuǎn)程站點(diǎn)1發(fā)送請(qǐng)求獲取站點(diǎn)1可供查的索引庫列表。

第二步：用戶選擇歷史庫1，系統(tǒng)在任務(wù)表中新建檢測任務(wù)。

第三步：本地檢測引擎掃描數(shù)據(jù)庫，獲取檢測任務(wù)信息，檢測完后，沒有找到的句子，再將句子的指紋加密發(fā)送到遠(yuǎn)程站點(diǎn)1，遠(yuǎn)程站點(diǎn)1的引擎接收后檢測。

圖4　系統(tǒng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

第四步：遠(yuǎn)程站點(diǎn)1查完將檢測結(jié)果發(fā)回本地站點(diǎn)，本地結(jié)合遠(yuǎn)程站點(diǎn)1的相似性證據(jù)一起寫回待查表。

1.2系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

由于相似性檢測系統(tǒng)通常都是單位內(nèi)部人員使用，因此系統(tǒng)一般部署在內(nèi)部局域網(wǎng)環(huán)境中。當(dāng)然，對(duì)于大眾用戶的相似性檢測需求，系統(tǒng)也可以對(duì)Internet開放。

本文構(gòu)建系統(tǒng)部署的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖4所示。

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

2.1確定檢測粒度

圖5　確定檢測粒度流程圖

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

在文檔切割的過程中，通常會(huì)首先按照自然段對(duì)文檔進(jìn)行初步的劃分，這是由于自然段可以表達(dá)作者相對(duì)完整的思想，同時(shí)也提供了對(duì)文檔結(jié)構(gòu)的換行。而另一方面，大部分抄襲者也都是選擇以段落為單位進(jìn)行抄襲的。然而，文檔中通常也會(huì)存在一些很長的自然段。例如，在論文中又包括了引言、研究方法和內(nèi)容、實(shí)驗(yàn)結(jié)果、討論和結(jié)論等，每項(xiàng)內(nèi)容又包括了段、句子、文本塊、詞等，這些特征都是多層次的。大量過長自然段和多層次特征的存在使得單單基于自然段落的劃分是行不通的。

如圖5所示，通過將自然段落切分為150字符左右的“句子”作為檢測單元粒度。同時(shí)對(duì)于特殊的獨(dú)句段，短句段等段落，這類段落通常具有很強(qiáng)的同義性，使用頻度很高，并且通常在文章中是起起承轉(zhuǎn)合的作用而與文檔的核心內(nèi)容無關(guān)。因此，對(duì)于這類段落不進(jìn)行相似性的檢測。

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

實(shí)際上文檔相似性檢測就是文檔間“句子”指紋的海明距離的范圍檢索。令細(xì)粒度的檢測單位“句子”的指紋為100位的海明碼指紋（fs,1-fs,100），將k=100位指紋進(jìn)行分組，分為m=5組（20,20,20,20,20,20）[11]。如(1)所示，則一個(gè)具有s個(gè)長句的文檔D可以表示為：

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

其中fn,s,k為第n個(gè)文檔的第s個(gè)句子對(duì)應(yīng)的第k位海明碼。若每個(gè)分組命名為{A,B,C,D,E}，則定義向量VA,VB,VC,VD,VE。

分別對(duì)向量VA,VB,VC,VD,VE建立m=5個(gè)B+樹索引。

在實(shí)際的系統(tǒng)應(yīng)用中，可以利用數(shù)據(jù)庫管理技術(shù)在指定的表中建立m=5個(gè)字段，并對(duì)這5個(gè)字段分別建立INDEX索引。論文采用了lucene4.9的版本來建立索引，Lucene作為一種全文檢索引擎架構(gòu)，具有優(yōu)秀的檢索效率，增量插入和刪除等操作非常方便。

2.3細(xì)粒度相似性比對(duì)

步驟2：分別在m=5個(gè)B+樹上執(zhí)行查詢條件（3），執(zhí)行查詢條件后的集合定義為Set(Pre_Query)。

步驟3：對(duì)Set(Pre_Quer y)中的所有元素進(jìn)行Disthamm距離計(jì)算，將所有滿足條件：Disthamm＜rhamm的加入集合Set(Query)中。其中上述rhamm為海明距離的閾值。

2.4系統(tǒng)相似性實(shí)施效果

為測試聯(lián)盟式相似性檢測的實(shí)際效果，論文在普通PC機(jī)上搭建起分布式處理平臺(tái)，其中一臺(tái)主機(jī)和三臺(tái)機(jī)器子節(jié)點(diǎn)。本章采用的實(shí)驗(yàn)數(shù)據(jù)來至知網(wǎng)的的1萬論文文檔對(duì)，將數(shù)據(jù)分為數(shù)據(jù)集1，數(shù)據(jù)集2和數(shù)據(jù)集3，每個(gè)數(shù)據(jù)集大小不同，每個(gè)數(shù)據(jù)集都有一定的重復(fù)率。通過三個(gè)不同的數(shù)據(jù)集的實(shí)驗(yàn)，可以有效的評(píng)估出聯(lián)盟式檢測的性能。數(shù)據(jù)集詳情如表1所示。數(shù)據(jù)集1，數(shù)據(jù)集2和數(shù)據(jù)集3的實(shí)驗(yàn)結(jié)果分別如表2，3所示。

表1　數(shù)據(jù)集詳情

表2　閾值R0=0.3時(shí)，單個(gè)數(shù)據(jù)集相似性檢測效果

表3　閾值R0=0.3時(shí)，3個(gè)數(shù)據(jù)集聯(lián)盟相似性檢測效果

圖6　(a)　一對(duì)多相似性證據(jù)顯示

圖6　(b)　一對(duì)一相似性證據(jù)顯示

三個(gè)數(shù)據(jù)集存在重復(fù)數(shù)據(jù)，要對(duì)數(shù)據(jù)進(jìn)行相似性檢測，首先要讀取將要存儲(chǔ)的文件數(shù)據(jù)，然后將文件數(shù)據(jù)進(jìn)行處理，求出文件的特征指紋，將指紋與索引表進(jìn)行匹配，最后計(jì)算出文檔的相似度。如表2，3所示，聯(lián)盟式相似性檢測的結(jié)果表明，三個(gè)數(shù)據(jù)集獨(dú)立的相似性檢測輸出文檔對(duì)共為1333，三個(gè)數(shù)據(jù)集聯(lián)盟相似性檢測輸出文檔對(duì)2100，多輸出了767份文檔對(duì)，證明了跨數(shù)據(jù)源抄襲現(xiàn)象的存在。因此，在以后的查重工作中，根據(jù)實(shí)際情況有必要進(jìn)行跨數(shù)據(jù)源檢測，提升項(xiàng)目查重的整體效果。

如圖6所示，系統(tǒng)給出的相似性證據(jù)界面，其中包括一對(duì)一直觀比對(duì)顯示以及一對(duì)多的細(xì)粒度抄襲證據(jù)顯示。

3 結(jié)語

分組指紋的彈性細(xì)粒度檢測主要解決了文檔內(nèi)容的分區(qū)查重問題，讓結(jié)果更加智能和準(zhǔn)確；聯(lián)盟式相似性檢測主要解決了不同數(shù)據(jù)源聯(lián)合查重的問題，使得異源抄襲也無所遁形。本論文的工作對(duì)分布式相似性檢測系統(tǒng)的推廣起到了一定作用。

[1] Broder A Z, Charikar M, Frieze 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．SODA '11 Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms，SIAM，2011．57-66

[3] Kane DM，Nelson J，Woodruff DP．An optimal algorithm for the distinct elements problem．PODS '10 Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems．NY, USA：ACM，2010．41-52

[4] Li P，K?nig AC．B-bit minwise hashing[A]. In Proceedings of the 19th international conference on World Wide Web, pages 671-680. ACM, 2010.

[5] Li P，K?nig AC，Gui W．B-bit minwise hashing for estimating three-way similarities．Neural Information Processing Systems (NIPS) BC, Canada：Vancouver．2010

[6] Li P，Moore J，K?nig AC．B-bit minwise hashing for large-scale linear SVM．Neural Information Processing Systems (NIPS) BC，Canada：Vancouver．2011

[7] Li P，K?nig AC．Accurate Estimators for improving Minwise Hashing and b-bit Minwise Hashing．Technical Report，New York：Cornell university library，2011

[8] Li P, K?nig AC．Theory and applications of b-bit minwise hashing [J]. Communications of the ACM, 2011, 54(8): 101-109

[9] T.Bray，J.Pao Li，CM.Sperberg-McQueen．Extensible markup language(XML) 1.0 W3C recommendation.Technical report，W3C，1998.

[10] E Hatcher.，O Gospodnetic，M McCandless．softsearch2.googlecode.com. 2004

[11] 袁鑫攀，龍軍，張祖平，桂衛(wèi)華．Near-duplicate document detection with improved similarity measurement [J]．Journal of Central South University of Technology 中南大學(xué)學(xué)報(bào)（英文版），2012，19(8):2231?2237

TP301.6

A

10.3969/j.issn.1000-386x.2013.01.001