金哲凡,俞定國,林生佑,周忠成

浙江傳媒學(xué)院,浙江 杭州 310018

基于音位的網(wǎng)絡(luò)盜版文本查重方法

金哲凡,俞定國,林生佑,周忠成

浙江傳媒學(xué)院,浙江 杭州 310018

傳統(tǒng)的文本查重算法是對文本作分詞以構(gòu)建關(guān)鍵詞向量，而對于某些特殊應(yīng)用的網(wǎng)絡(luò)盜版檢測，分詞的開銷則未必合理和必要。因此，本文提出一種基于漢語音位信息的文本查重方法。文本被表達(dá)為聲、韻、調(diào)三個空間向量，以余弦距離作相似性度量。提出兩種相似性判斷公式，一種假定三向量獨(dú)立分布；一種取其線性組合，系數(shù)可由音位元素的信息熵算出，通過大文本統(tǒng)計得出信息熵的估計值，以傳統(tǒng)的關(guān)鍵詞向量/SimHash方法做參照產(chǎn)生語料，對其作統(tǒng)計得到模型參數(shù)。實(shí)驗結(jié)果表明該方法有一定的精確率和很好的召回率，計算開銷低于傳統(tǒng)的方法，適合需要過濾大量TN類型文本的場合。

音位;盜版文本;查重

文本查重是根據(jù)一定相似度模型從數(shù)據(jù)流中發(fā)現(xiàn)相重文本的過程。它在搜索引擎構(gòu)建、抄襲檢測、新聞分類等領(lǐng)域有廣泛的應(yīng)用。文本查重是一種特殊的文本過濾[1]，過濾條件是目標(biāo)文本與源文本相似度大于閾值。文本查重方法基于兩種基礎(chǔ)技術(shù)：文本向量空間模型和文本指紋，前者解決相似性度量的問題，后者優(yōu)化檢索。

向量空間模型的作用是將無結(jié)構(gòu)的文本表示成計算機(jī)易處理的特征向量，文本間的相似性問題隨之轉(zhuǎn)變成向量間距離的問題。特征提取算法包括TF-IDF、詞頻方法、互信息方法、信息增益方法等。其中TF-IDF用關(guān)鍵詞的權(quán)重做特征，權(quán)重計算兼顧了關(guān)鍵詞在全局的重要性和在局部的頻率這兩種信息，使用廣泛，是經(jīng)典方法[2]。有些場合如文獻(xiàn)[3]修改TF-IDF的權(quán)重公式以優(yōu)化排序。針對中文，文獻(xiàn)[4]在特征選取中考慮了詞頻，也考慮了標(biāo)點(diǎn)符號，并且將文本的位置因素加入在內(nèi)；文獻(xiàn)[5]的提出"動詞中心詞"的概念，將文本中的部分動詞組成動詞序列作為一種特征；文獻(xiàn)[6]用以中文句號為基礎(chǔ)的特征實(shí)現(xiàn)了大規(guī)模的新聞網(wǎng)頁查重。

特征向量確定后，文本間的相似性可用某種空間距離來表示，如余弦距離、數(shù)量積、相關(guān)系數(shù)、指數(shù)相似系數(shù)、幾何平均最小、算數(shù)平均最小等[7,8]。特征向量與距離公式配合，就可以進(jìn)行文本查重的計算。以網(wǎng)絡(luò)盜版檢測為例，網(wǎng)絡(luò)文本的特征向量如果與源文本特征向量的余弦值大于閾值，就可以認(rèn)為它有盜版嫌疑?，F(xiàn)實(shí)中某些應(yīng)用，如Google的搜索引擎對存儲空間和計算時間特別敏感，需要使用文本指紋技術(shù)。它將文本的特征向量通過Hash函數(shù)映射為一定字長比如64 bit的二進(jìn)制數(shù)，稱為指紋，文本的比較通過指紋進(jìn)行。長度固定的指紋適合構(gòu)造指紋庫，可進(jìn)行快速檢索。

從原始文本到特征向量、再到文本指紋是一個單向不可逆的信息減少過程。64 bit的指紋實(shí)際只保留了64維向量空間的方向信息。在各種指紋算法之中，Google的SimHash保留了較多向量間的相似性，可根據(jù)指紋間的海明距離反映文檔間的差異程度，因此優(yōu)于MD5等Hash算法，是主要使用的指紋技術(shù)。根據(jù)Google的經(jīng)驗，64位SimHash值的海明距離在3～5之間可認(rèn)為是同一文本。

中文文本的分詞是提取關(guān)鍵詞向量的前置步驟。分詞算法已非常成熟，基于統(tǒng)計的方法是其主流[9]；與人工智能新技術(shù)結(jié)合的、基于大規(guī)模神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的方法是當(dāng)前的熱點(diǎn)[10,11]。分詞算法至少是O（n2）的復(fù)雜度。定性地看，關(guān)鍵詞向量可以看做文本“含義”的一種統(tǒng)計表達(dá)，大部分文本處理應(yīng)用如摘要生成、倒排索引、機(jī)器翻譯等的后續(xù)計算需要對文本的含義作一定程度的理解，因此分詞的計算開銷是完全必要的。而在一些特殊應(yīng)用盜版檢測中，文本查重、判斷是否相同文本是唯一重要的計算，“含義”并不是必須的。如能用其他特征、如音位代替關(guān)鍵詞，或作為關(guān)鍵詞向量方法的前置和補(bǔ)充，可以避免大量分詞計算，提高速度。

中文是極其獨(dú)特的語言，“字”是獨(dú)一無二的“音/意”載體，是其他語言沒有的構(gòu)造單位[12]。字的音位構(gòu)成規(guī)整一致，音節(jié)占用時長和書寫占位大體平均。從字的二進(jìn)制表示得到其拼音只需一次內(nèi)存訪問的開銷，遠(yuǎn)低于最好的分詞算法。以字的音位統(tǒng)計信息作為特征進(jìn)行文本查重，是一個符合漢字規(guī)律的方法。

本文的查重方法對文本提取聲母、韻母、聲調(diào)三個特征向量，以余弦距離為度量，實(shí)驗了兩種文本相似性模型。首先通過大樣本的訓(xùn)練，獲得模型參數(shù)的估計。之后以二種模型對大量文本進(jìn)行測試，實(shí)驗結(jié)果證明可以達(dá)到區(qū)分和過濾的目的。與傳統(tǒng)的基于關(guān)鍵詞向量方法比較，本文方法避免了分詞，計算開銷較低。

1 音位特征選取

國家漢語拼音標(biāo)準(zhǔn)規(guī)定了23個聲母、24個韻母和16個整體認(rèn)讀音節(jié)。一些語言學(xué)的統(tǒng)計工作[12]把w、y排除在聲母之外，而韻母包括了三拼。本文如下處理：

(1)聲母為標(biāo)準(zhǔn)的23個加上零聲母，共24個。

(2)韻母為標(biāo)準(zhǔn)的24個加10個三拼韻母：ia,ua,uo,uai,iao,ian,iang,uan,uang,iong，共34個。

(3)聲調(diào)為“陰、陽、上、去、輕”5種不變。

(4)繼承“ü”去兩點(diǎn)的規(guī)則，除了nü、lü、nüe、lüe四個音節(jié)之外，都作“u”計。

如此覆蓋漢語拼音標(biāo)準(zhǔn)下包括整體認(rèn)讀音節(jié)的所有情況，使從漢字到音位的映射可做到1字1聲1韻1調(diào)。設(shè)文本d是字zk的序列，如忽略標(biāo)點(diǎn)、數(shù)字等非漢字元素，字長n的文本為：d=(z1z2z3…zk…zn)

其中zk∈Z，Z為漢字集。漢字z的音位由聲母a、韻母b和聲調(diào)c組成。若對多音字取其第一種發(fā)音，則zk=(ak,bk,ck)，其中ak∈S,bk∈Y,ck∈T。S={s1,s2,s3,…si…s24},是聲母集合；Y={y1,y2, y3,…yi…y34},是韻母集合；T={t1,t2,t3,…t5},是聲調(diào)集合。

令f(si,d)、f(yi,d)、f(ti,d)是聲母si、韻母yi、聲調(diào)ti在文檔d中的頻率，即

其中I為指示函數(shù)，參數(shù)表達(dá)式成立時為1，否則為0。則文檔d可表示為三個特征向量的組合，其中設(shè)有兩個文檔d1,d2，可在空間各定義余弦距離如下：

cos_s( d1,d2)余弦距離cos_s(d1,d2)、cos_y(d1,d2)和cos_t(d1,d2)可對d1、d2間的相似度作出基于音位的度量。

2 相似性模型

實(shí)驗了兩種文本相似性模型：

(1)假定聲、韻、調(diào)獨(dú)立分布，當(dāng)d1、d2在三個空間上的余弦都超過閾值時，它們被認(rèn)為相似（相重）。即文本d1，d2相似的條件為：

其中I為指示函數(shù)，gs，gy，gt為三個空間上的閾值。

假定聲、韻、調(diào)在文本相似性上的貢獻(xiàn)度可通過權(quán)值表達(dá)，將它們線性組合來定義相似度指標(biāo)Similarity：Similarity=αcos_s(d1,d2)+βcos_y(d1,d2)+θcos_t(d1,d2)，其中α+β+θ=1。

文本d1，d2相似的條件為：Similarity＞gsimilairty，gsimilairty為相似度閾值。

對模型2的權(quán)重系數(shù)α、β、θ，作如下考慮：某一特征向量對相似度的貢獻(xiàn)應(yīng)和它包含的信息量相關(guān)，

而信息量可用信息熵H度量。令聲母、韻母、聲調(diào)向量的信息熵為Hs、Hy、Ht，可定義：

其中p(si)、p(yi)、p(ti)是聲母si、韻母yi、聲調(diào)ti在文本中出現(xiàn)的概率。

p(si)、p(yi)、p(ti)可通過對大語料統(tǒng)計的頻率值來近似。對1,41 1,996篇、共481,065,247字的現(xiàn)代漢語語料作統(tǒng)計的結(jié)果如表1～3所示(none表示零聲母)。

表1 聲母頻率統(tǒng)計Table 1 Frequencies of Chinese initials

表2 韻母頻率統(tǒng)計Table 2 Frequencies of Chinese finals

表3 聲調(diào)頻率統(tǒng)計Table 3 Frequencies of Chinese tones

文獻(xiàn)[12]列出了對7754個現(xiàn)代漢字的音位的靜態(tài)統(tǒng)計結(jié)果，表1-表3是對動態(tài)文本的統(tǒng)計且所取統(tǒng)計項目不同，故有較大差異。但兩者還是有一些相似點(diǎn)，比如“d”是使用頻率最高的聲母，“i”是使用頻率最高的韻母，去聲是出現(xiàn)頻率最高的聲調(diào)。統(tǒng)計程序通過Java語言實(shí)現(xiàn)。用聲、韻、調(diào)頻率的統(tǒng)計值作為概率值的估計，得到Hs、Hy、Ht的估計值：Hs’=4.3644；Hy’=4.5300；Ht’=2.1081。進(jìn)而得到模型2系數(shù)α、β、θ的估計值：α’=0.3967；β’=0.4117；θ’=0.1916。

3 實(shí)驗和測試結(jié)果

實(shí)驗分為參數(shù)計算和過濾測試兩部分。參數(shù)計算目的是獲得前述2個相似性模型的參數(shù)的估計值：模型1參數(shù)為gs，gy，gt；模型2參數(shù)為gsimilairty。

計算過程用傳統(tǒng)的“關(guān)鍵詞向量+SimHash指紋”辦法作為參照，以行業(yè)的經(jīng)驗值、指紋海明距離3作為文檔相重的閾值。用隨機(jī)字替換的辦法給源文本摻入噪聲，直至海明距離為閾值3為止。訓(xùn)練選用包含925個文本共534,924漢字的現(xiàn)代漢語語料，命名為D，首先對其摻入噪聲獲得語料D’，摻噪聲的流程如下：

(1)預(yù)先準(zhǔn)備噪聲模板NoiseTemplate.txt，這是一個包含7000余字的現(xiàn)代漢語文本。

(2)對D中文本d，獲取關(guān)鍵詞向量及其SimHash指紋u1。

(3)從噪聲模板中隨機(jī)取一個字z，選擇d文中一隨機(jī)位置，用z替換原文字。

(4)獲取d的新指紋u2。

(5)計算u1和u2的海明距離H_dist。若H_dist＜3，跳轉(zhuǎn)3，循環(huán)。若H_dist==3，轉(zhuǎn)6，出循環(huán)。若H_dist＞3，比較本次摻噪聲前的文本和摻噪聲后的文本的指紋哪個更接近3，取接近者為輸出文本，轉(zhuǎn)6。

(6)若最終H_dist==3，d的處理結(jié)束。否則，若累積嘗試次數(shù)小于上限，轉(zhuǎn)2，文本d的處理重新開始；否則若嘗試次數(shù)大于上限，結(jié)束。

有時摻入一個字的噪聲會導(dǎo)致海明距離躍遷，比如從2跳到6，此時回到原狀、重新嘗試，直至語料中所有文本d都得到了對應(yīng)的含噪聲為海明距離3的相似文本d’。

語料D={di|i=1..925}摻噪聲后得語料D’={di’|i=1..925}，對每對文本di與di’，提取文字音位的聲、韻、調(diào)成分，計算各成分頻率，獲得向量之后計算它們在S、Y、T空間的夾角cos_s(di,di’)，cos_y(di,di’)和cos_t(di,di’)。 針對模型2，則按如下公式得一組Similarity計算值：Similarityi=α’cos_s(di,di’)+β’cos_y(di,di’)+θ’cos_t(di,di’)。最終結(jié)果如表4。

表4 模型參數(shù)訓(xùn)練結(jié)果Table 4 Training results for parameters of models

兩個相似性模型需要的參數(shù)為閾值，且表4中均方差較小，故不妨取最小值做模型參數(shù)。得模型1的參數(shù)為：gs=0.953，gy=0.932，gt=0.964；模型2的參數(shù)gsimilairty=0.962。過濾測試包括兩部分工作：測試語料生成和測試。先對源語料E隨機(jī)摻入噪聲，流程如下：

(1)預(yù)先準(zhǔn)備噪聲模板NoiseTemplate.txt，這是一個包含7000余字的現(xiàn)代漢語文本。

(2)對E中文本e，若其長度為l，在[0,[kl]]區(qū)間內(nèi)產(chǎn)生隨機(jī)數(shù)r。系數(shù)k是一個經(jīng)驗值，0＜k＜1。

(3)循環(huán)r次，每次取噪聲模板中一個隨機(jī)漢字替換e中一個隨機(jī)位置的漢字。最終得到摻入噪聲后的文檔e’。

(4)求得e和e’文本指紋的海明距離Hamming(e,e’)。

取與訓(xùn)練語料無交集、共455,464字的1000個文本作為源語料E，用上述流程摻入噪聲后得E’，E’與E的差距如表5。

表5 測試語料生成結(jié)果Table 5 Results of generating testing corpus

根據(jù)Google的經(jīng)驗值，若Hamming(e,e’)≤3，則e和e’是相重文本，若用基于音位的方法測得正，則為TP；若測得負(fù)，則為FN。若Hamming(e,e’)＞3，則e和e’是不同文本，若用基于音位的方法測得正，則為FP；若測得負(fù)，則為TN。

將訓(xùn)練所得參數(shù)代入模型1和模型2，對E和E’作查重計算，統(tǒng)計各文本分類結(jié)果，并計算精確率P、召回率R、調(diào)和指標(biāo)F1和運(yùn)行時間t，結(jié)果如表6：

表6 測試結(jié)果Table 6 Test results

試將模型使用的參數(shù)（閾值）都調(diào)低10%，再運(yùn)行測試，結(jié)果如表7。

表7 調(diào)低閾值后測試結(jié)果Table 7 Test results after lowing threshold value

可以看出兩個模型都可以過濾大部分相似文本，模型2略好于模型1，且都有很好的召回率。降低閾值后，精確率P下降，召回率R升高。作為對比，對同數(shù)據(jù)集進(jìn)行分詞、關(guān)鍵詞提取和算關(guān)鍵詞向量余弦操作，執(zhí)行時間t’=28.355 s。運(yùn)行時間的計取都剔除了文件讀取等無關(guān)操作。對表3和表4中運(yùn)行時間取均值，模型1均值t1，模型2均值t2，t1/t’=23.86%，t2/t’=24.51%。文本基于音位的方法在計算時間上明顯優(yōu)于關(guān)鍵詞向量方法。

實(shí)際應(yīng)用是一個用于互聯(lián)網(wǎng)盜版發(fā)現(xiàn)的系統(tǒng)。對出版社等擁有的原作庫提取音位特征，網(wǎng)絡(luò)爬蟲連續(xù)獲取網(wǎng)絡(luò)文本，對其內(nèi)容逐個提取音位信息，用本文方法進(jìn)行前置過濾，之后再作同一性（查重）檢測。之后進(jìn)行違法性檢測，找到真正的侵權(quán)項目。網(wǎng)絡(luò)盜版行為猖獗，但在海量的文本流中涉嫌盜版的畢竟是少數(shù)，絕大部分是無關(guān)的。由于內(nèi)容庫文本數(shù)量巨大，系統(tǒng)效率很大程度取決于能否將這99%以上的無關(guān)文本快速排除，因此在精確率和速度之間，系統(tǒng)更關(guān)注速度；在精確率和召回率之間，系統(tǒng)更關(guān)注召回率。本文方法有很好速度和召回率，非常適合做前置過濾。精確率隨閾值的下調(diào)而下降是個問題，對于FP類型的文本，可以在后續(xù)步驟用其他方法濾去，比如用傳統(tǒng)的關(guān)鍵詞向量+SimHash的辦法作交叉驗證，或人工驗證。由于這部分文本數(shù)量已極少，因此不影響系統(tǒng)整體性能。

實(shí)驗程序的分詞、向量提取和SimHash計算使用了軟件simHash，漢字的拼音轉(zhuǎn)換使用了軟件包pinyin4j，語料使用了搜狐實(shí)驗室的全網(wǎng)新聞?wù)Z料資源。音位相關(guān)的程序用Java實(shí)現(xiàn)，Simhash相關(guān)的程序用gcc實(shí)現(xiàn)，用Java本地進(jìn)程調(diào)用機(jī)制處理二者的協(xié)同。

4 結(jié)論

文本查重方法基于兩種基礎(chǔ)技術(shù)：以TF/IDF為代表的向量表示和以SimHash為代表的文本指紋。研究者提出了各種改進(jìn)，針對特殊的領(lǐng)域進(jìn)行優(yōu)化。本文基于漢語“字”音位均勻的特點(diǎn)，提出基于音位的查重辦法。文本被表示為聲、韻、調(diào)三個空間的向量，相似性以余弦距離度量。提出兩種距離模型，一種假定三向量獨(dú)立分布；一種假定三向量可線性組合，其系數(shù)由音位元素的信息熵算出。測試結(jié)果表明兩種模型都可以實(shí)現(xiàn)過濾，且有召回率優(yōu)于精確率的特點(diǎn)。這個特點(diǎn)非常適合于類似網(wǎng)絡(luò)盜版文本發(fā)現(xiàn)的應(yīng)用：輸入文檔的數(shù)量巨大，要求快速處理，但其中99%以上是不涉嫌盜版（True Negative型）的。將本文方法用于其前置過濾，由于音位頻率的計算只需一次內(nèi)存訪問的開銷，不需進(jìn)行分詞，因此效率高于基于關(guān)鍵詞向量的方法。

語言是含義和發(fā)音的綜合物。關(guān)鍵詞向量是對含義的統(tǒng)計表達(dá)而不顧及其發(fā)音；本文方法利用了漢語的發(fā)音而不顧及其含義。定性地考慮，前者相當(dāng)于人通過默讀區(qū)分文檔，后者相當(dāng)于不識字的人通過辨音區(qū)分文檔。兩者都是可行的，但必定有各有特點(diǎn)?；谝粑坏姆椒▋?yōu)點(diǎn)是不需分詞，可以以較快速度實(shí)現(xiàn)一定精確率的過濾。它可以單獨(dú)使用，也可與其他方法聯(lián)合。在必要的場合，音位向量也可通過SimHash產(chǎn)生指紋以加快檢索。未來還需要深入的研究以拓展其應(yīng)用。

[1]Korde V,Mahender CN.Text Classification and Classifiers:A Survey[J].International Journal of Artificial Intelligence&Applications,2012,3(2):45-52

[2]Wang XH,Cao J,Liu Y,et al.Text Clustering Based on the Improved TF-IDF by the Iterative Algorithm[J].IEEE Symposium on Electrical&Electronics Engineering,2012,34(7):140-143

[3]李鎮(zhèn)君,周竹榮.基于Document Triage的TF-IDF算法的改進(jìn)[J].計算機(jī)應(yīng)用,2015,35(12):3506-3510

[4]宋 蘭,孫茂松.中文文本全文查重的實(shí)驗研究[C]//宋蘭.全國第八屆計算語言學(xué)聯(lián)合學(xué)術(shù)會議(JSCL-2005),2005:147-157

[5]劉小軍,趙 棟,姚衛(wèi)東.一種用于中文文本查重的雙因子相似度算法[J].計算機(jī)仿真,2007,24(12):312-314

[6]韋永壯,袁春風(fēng),黃宜華.CCDet:一種高效的大規(guī)模中文重復(fù)網(wǎng)頁檢測方法[J].計算機(jī)研究與發(fā)展,2013,50(S2):140-152

[7]華秀麗,朱巧明,李培峰.語義分析與詞頻統(tǒng)計相結(jié)合的中文文本相似度量方法研究[J].計算機(jī)應(yīng)用研究,2012,29(3):833-836

[8]張佩云,陳傳明,黃 波.基于子樹匹配的文本相似度算法[J].模式識別與人工智能,2014,27(3):226-234

[9]黃昌寧,趙 海.中文分詞十年回顧[J].中文信息學(xué)報,2007,21(3):8-19

[10]韓冬煦,常寶寶.中文分詞模型的領(lǐng)域適應(yīng)性方法[J].計算機(jī)學(xué)報,2015,38(2):272-281

[11]來斯惟,徐立恒,陳玉博,等.基于表示學(xué)習(xí)的中文分詞算法探索[J].中文信息學(xué)報,2013,27(5):8-14

[12]馮志偉.語言與數(shù)學(xué)[M].北京:世界圖書出版社,2011:360

Method for Checking Duplicate Text of Network Piracy Based on Phoneme

JIN Zhe-fan,YU Ding-guo,LIN Sheng-you,ZHOU Zhong-cheng
Zhejiang University of Media and Communications,Hangzhou 310018,China

The traditional method checking repetition takes a text as a participle to establish some key vectors,however the piratical cost may not be reasonable or necessary for the discovery of the online copyright violation in some special APP. Therefore this paper proposed a method checking repetition with Chinese phonology.A text was represented by three vectors in spaces of Chinese initial,final and tone and cosine distance was used as a measurement of similarity.Two decision models were proposed.One assumed the three vectors were independent each other,while the other took a linear combination of the three,which needed to calculate the factors using information entropies that could be evaluated by large-corpus counting. Training corpus was generated with the old term-vector/SimHash method being used as a standard and threshold values were calculated.Test results showed the proposed method had a good precision and a very good recall ratio,and computational cost was lowed comparing to traditional methods based on term vectors to be suitable for filtering out a large amount of TN documents.

Phonology;piratical text;checking repetition

TP391

:A

:1000-2324(2017)03-0467-05

2016-08 03

:2016-08-23

浙江省公益技術(shù)應(yīng)用研究項目(2016C33196);浙江省公益性技術(shù)應(yīng)用研究項目(2017C33105)

金哲凡(1974-),男,副教授,博士.主要研究方向為并行計算，信息處理，圖形學(xué).E-mail:jinzf@zjicm.edu.cn