基于語義相似性的中文文本檢索算法研究

基于語義相似性的中文文本檢索算法研究

1基于文本特征串的方法通過文本搜索，不僅可以保護(hù)知識產(chǎn)權(quán)，而且可以提高搜索效率。其核心內(nèi)容就是判斷兩篇文本內(nèi)容中是否存在雷同成分,并給出一個數(shù)值評估,這個值可以稱為相似度。在計算相似度值前,需要提取文本特征。根據(jù)提取文本特征的方式可以將目前的研究方法分為兩類,一類是采用基于字符串比較的方法,也稱為基于語法的方法,如sif,COPS,shingling,YAP3,MDR;另外一種采用基于詞頻統(tǒng)計的方法,也稱為基于語義的方法,如SCAM,CHECK,CDSDG。國內(nèi)方面,哈爾濱工業(yè)大學(xué)信息檢索試驗(yàn)室提出了用特征碼的方法進(jìn)行網(wǎng)頁查重。清華大學(xué)也研究了類似的方法:采用“自然語句分隔標(biāo)志”將文本切成若干“句子”,從句子中提取若干字符和漢字作為特征碼,然后按照“句子”在文本的順序連接形成特征串。還有LCS算法,即計算最長的公共子序列,根據(jù)其長度與文本長度的比值來判斷文本內(nèi)容是否重復(fù),但是算法的時間復(fù)雜度和空間復(fù)雜度較高。本文根據(jù)漢語語言學(xué)的研究成果以及對中文動詞使用頻率的統(tǒng)計,提出了一種獲取文本特征串的新方法,結(jié)合字符串比較算法,計算出中文文本的語法相似性;利用詞頻統(tǒng)計的方法計算出中文文本的語義相似性,根據(jù)改進(jìn)的計算公式,可以得到兩篇中文的相似度,從而進(jìn)行中文的重稿檢測。2算法理論基礎(chǔ)兩篇文章間的相似性可以從語法相似性和語義相似性兩個方面進(jìn)行度量。2.1擴(kuò)展動詞序列呂叔湘在其代表著《中國文法要略》中構(gòu)建了動詞為中心的句法模型。在分析句子時,認(rèn)為句子中心是表示動作的動詞,而表示動作之所由起,所終止,以及所關(guān)涉的各個方面的名詞,都是對這個動詞的補(bǔ)充,因而統(tǒng)統(tǒng)可稱為“補(bǔ)詞”。于是,句子中除動詞這個中心以外,就有了“起詞”,“止詞”,“受詞”,“關(guān)切補(bǔ)詞”,“交與補(bǔ)詞”,“憑借補(bǔ)詞”等各種“補(bǔ)詞”。也就是說,句子表達(dá)的意思體現(xiàn)在句中的中心動詞上,因此段落中所有句子的中心動詞組成的序列就體現(xiàn)了段落的中心意思,同理,文章中所有句子的中心動詞組成的序列可以概括全文的中心意思。這樣,動詞序列不僅反映了文章中發(fā)生的動作,而且描述了動作的發(fā)生順序,因此可以用動詞序列作為文章的特征串。兩篇文章間特征串的相似性反映了文章間的相似性。目前,基于這個假設(shè),一些研究機(jī)構(gòu)提出了關(guān)于提取句中主干動詞的算法,以及用“句子骨架依存樹”的概念來計算句子間的相似度。在本文中,通過擴(kuò)展動詞序列,即將文中所有動詞組成的序列作為研究對象,來降低算法的復(fù)雜性。同時,為了降低動詞序列的長度,從而降低算法的空間復(fù)雜度,排除了動詞序列中所有的停用動詞。停用動詞是對信息檢索領(lǐng)域中停用詞的擴(kuò)展。在信息檢索中,集合文獻(xiàn)中出現(xiàn)頻率高于80%單詞是沒有用的,這些詞常稱為“停用詞”,需要過濾掉。一般認(rèn)為停用詞包括冠詞,介詞,連詞和語氣詞,還可以包括這些詞之外的其他詞,例如一些動詞、副詞和形容詞。通過統(tǒng)計動詞的使用頻率,發(fā)現(xiàn)一批動詞在文本中普遍存在。可以將這類詞歸為停用詞,在這里稱為停用動詞。表一是從2378篇文本,共20.8M字節(jié)數(shù)據(jù)得到的動詞使用頻率的統(tǒng)計表。如表1所示:由表1可以看出,如“應(yīng)”,“為”,“到”,“會”,“可以”等均可以視為停用動詞。在排除停用動詞后,可以降低動詞序列的長度,即降低特征串的維數(shù)。2.2計算相似度的計算度量語義相似性可以參考信息檢索中的向量模型。向量空間模型的基本思想是以向量來表示文本:(w1,w2,w3,….,wn),其中wi為第i個特征項的權(quán)重?？梢赃x擇字、詞或者詞組作為特征項,一般認(rèn)為選取詞作為特征項要優(yōu)于用字和詞組作為特征項,同時用詞的相對詞頻表示向量的分量。最常用的權(quán)重計算方法是TF-IDF加權(quán)法:Wi,j=fi,j×logNni(1)fi,j=freqi,jmaxl(freql,j)(2)idfi=logNni(3)Wi,j=fi,j×logΝni(1)fi,j=freqi,jmaxl(freql,j)(2)idfi=logΝni(3)其中N為系統(tǒng)中文本總數(shù),ni表示含有詞ki的文本數(shù)目,fi,j表示詞ki在文本dj中初始頻率,在這里指在文本中出現(xiàn)的次數(shù)。則文本dj中詞ki的標(biāo)準(zhǔn)化頻率為fi,j,最大值是通過計算文本dj中所有詞來獲得的。idfi為詞ki的逆文獻(xiàn)頻率,Wi,j為詞ki在文本dj中的權(quán)重。在獲得文章的特征向量后,就可以計算文章間的相似度。設(shè)文檔di的特征向量為(w1i,w2i,w3i…,wni),文檔dj的特征向量為(w1j,w2j,w3j…,wnj),其相似度一般以計算余弦角為基礎(chǔ)。例如:Dice系數(shù):Sim(Di,Dj)=2*∑k=1nwkiwkj∑k=1nw2ki+∑k=1nw2kj(4)Sim(Di,Dj)=2*∑k=1nwkiwkj∑k=1nwki2+∑k=1nwkj2(4)3算法流程3.1計算相似度假定兩篇中文分別為A,B,算法流程描述如圖1所示。在分別獲得兩篇文章的動詞序列后,可以將動詞序列看作一個字符串,因此兩個動詞序列的相似性可以通過計算兩個字符串的公共子串的個數(shù)來獲得。假設(shè)文章A的動詞序列為V1,V2,V3,V2,V4;文章B的動詞序列為V1,V3,V2,V4。則A→B公共子串的個數(shù)由圖2可示,B→A公共子串的個數(shù)由圖3可示。則A→B公共子串的個數(shù)為3,B→A公共子串的個數(shù)為4。則取二篇文章間最大公共子串個數(shù)作為實(shí)際公共子串個數(shù)。在獲取到最大公共子串個數(shù)后,采用類似Dice系數(shù)來計算相似度。計算式為:f1=2×ca+b(5)f1=2×ca+b(5)c為公共子串的個數(shù),a為文章A的動詞序列中動詞的個數(shù),b為文章B的動詞序列中動詞的個數(shù)。根據(jù)此計算式,則上述兩篇文章的語法相似度為88.89%。3.2交叉集的情形算法步驟為:1)中文分詞;2)計算各詞的權(quán)重;3)獲得前N個權(quán)重最大的詞作為特征串;4)計算兩篇文章的特征串的交叉集;5)計算相似度。在第2)步,利用TF-IDF計算詞的權(quán)重。在第3)步中需要排除停用詞,還包括所有的動詞。在第4)步中引用了交叉集的概念,設(shè)文章Di的特征串為(s1i,s2i…,sni),文章Dj的特征串為(s1j,s2j…,snj)。則交叉集C(Di,Dj)為:C(Di,Dj)=(s1i,s2i…,sni)∩(s1j,s2j…,snj)交叉集C(Di,Dj)包含文章Di,Dj中均存在的特征詞。在第5)步中采用以下計算式得到文章間的相似度:f2=∑k=1mmin(wki,wkj)max(wki,wkj)N(6)f2=∑k=1mmin(wki,wkj)max(wki,wkj)Ν(6)其中m為交叉集中元素的個數(shù),wki為文章Di特征串中第k個詞的權(quán)重,wkj為文章Dj特征串中第k個詞的權(quán)重。N為文章特征串中元素的個數(shù)。計算公式中考慮到相同的特征在兩篇文章間可能有不同權(quán)重的情況。通過權(quán)重的相除,可以量化相同特征分量在兩篇文章中的不同作用。3.3計算相似性度量在獲得了兩篇中文的語義和語法相似性度量值之后,需要計算總的相似度,可以采用下述計算式來計算文章間的相似性:f=α*f1+β*f2(α>0,β>0,α+β=1)(7)f1為語法相似性度量值,f2為語義相似性度量值。α,β為加權(quán)系數(shù),其值可以根據(jù)試驗(yàn)過程中語法結(jié)構(gòu)、語義結(jié)構(gòu)在度量文章相似性的權(quán)重確定,初始值可以設(shè)為0.5,0.5。4算法測試4.1文件的翻譯從http://./part1.html中下載了150對文件,共447K,每對是對同一個英文文件的不同翻譯版本,既包括成品,也有半成品。還有來自于復(fù)旦大學(xué)提供的語料庫中的部分文本,共3042個純文本文件,共47.5M字節(jié),這些文件被用來作為干擾語料。4.2測試結(jié)果(表2)5計算對比算法綜合考慮兩篇中文的語法相似性和語義相似性,識別正確率以及查全率均超過了95%。