一種文本文檔相似性計算的方法

黃淑芹，徐 勇，常 郝

(安徽財經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院,安徽 蚌埠 233030)

0 引言

隨著計算機(jī)技術(shù)和網(wǎng)絡(luò)的飛速發(fā)展，數(shù)據(jù)資源在急速增加，其中很大一部分?jǐn)?shù)據(jù)屬于文本數(shù)據(jù)，所以對文本數(shù)據(jù)的處理是信息處理領(lǐng)域的重要組成部分．其中，文本文檔的相似度計算又是文本處理技術(shù)中一項重要的基礎(chǔ)技術(shù)，在自動文摘、文本分類、知識挖掘、機(jī)器翻譯、自動問答系統(tǒng)、文檔復(fù)制檢測及信息檢索等領(lǐng)域發(fā)揮著基礎(chǔ)性的作用[1]．文本文檔相似度計算是否合理直接影響到文檔聚類、文檔分類、信息檢索、查詢處理、數(shù)據(jù)挖掘的性能效果．

1 相關(guān)工作

文本文檔相似度計算的重要性引起了很多學(xué)者對其研究．像張煥炯提出了基于漢明距離的文本相似性計算[2]，該方法將歐式空間相似度計算中的大量乘法運算轉(zhuǎn)換成模2加運算，計算簡單方便，但建立文本與碼字之間的1-1關(guān)系卻要花費大量工作．曹恬等將詞共現(xiàn)的概念引入到傳統(tǒng)VSM中，提出基于詞共現(xiàn)的文本相似度計算方法[3]，該方法能表達(dá)一定的語義信息．但對于短文本，由于其信息量少，那么抽取的能代表主題的詞共現(xiàn)信息也少，所以該方法不適合短文本．基于屬性論的文本相似性計算能較全面地體現(xiàn)文本的內(nèi)容，所以在相似度計算上比較精確[4]．上述這些方法都是基于向量空間提出的，把文檔轉(zhuǎn)化成某一向量，再結(jié)合相似度計算公式來計算相似度．但基于向量空間的方法要求特征元素之間不存在任何的語義關(guān)系，其實這是不現(xiàn)實的．另外，這類方法往往適合于大粒度的文檔，因為文檔如果過小，抽取的特征詞就少，不能很好地體現(xiàn)文檔主題．還有基于語義理解的相似度計算，像基于WordNet[5]、同義詞詞林[6]、知網(wǎng)語義結(jié)構(gòu)[7]進(jìn)行相似度計算．這類方法往往依賴于語義庫，計算效率不高，并且現(xiàn)在研究大都局限于詞語、句子和段落范圍．還有基于字符串匹配的相似度計算方法，這類方法的主流思想是基于編輯距離[8]的方法，即字符串A通過插入、刪除、替換變成另外一個字符串B所需的操作的次數(shù)，用此來表示兩個字符串的差異．該方法的計算主要消耗在由A變成B所需的操作次數(shù)上．文獻(xiàn)[9]提出了基于編輯距離的相似度計算．

由于字符串匹配方式簡單方便，不需要額外的語料庫數(shù)據(jù)，所以被廣泛應(yīng)用在信息檢索、機(jī)器翻譯、計算生物學(xué)和信號處理等方面[10]．本文也是基于字符串匹配的思想，不是通過編輯距離，而是對不同長度的公共序列賦予不同的權(quán)值，構(gòu)造相似度計算公式．

2 文本文檔相似度的計算

2.1 相關(guān)定義

公共序列：設(shè)有序列A=(a1a2…am),B=(b1b2…bn),若A中(ai…aj)是B的子串，且(ai…ajaj+1)不是B的子串，則稱(ai…aj)是序列A和B的長度為(j-i+1)的公共序列．

2.2 統(tǒng)計公共序列頻度的算法

設(shè)有兩組文本A、B，用數(shù)組count[n](n=1，2，…，min，min=min(len(A)，len(B))存放連續(xù)長度為n的公共序列數(shù)．則統(tǒng)計A、B公共序列頻度count[n]的算法如下：

(1)去掉文本中虛詞和重復(fù)詞；

(2)初始化數(shù)組count[n]=0

(3)start=1,n=1 //start為子序列的起始位置

(4)while (n<= min)

(5){ substr=substring(A,start,n)

//從A的第start個字符開始取n個長度的子串

(6)判斷substr在B中是否存在

(7)if存在,則

{count[n]++；

If (n>1),則count[n-1]--；

n=n+1 //連續(xù)長度n增1}

else

{If (n>1)

{start=start+n-1;//起始位置回溯

n=1;}

else

start++；//起始位置后移}}

2.3 相似度計算公式

由于同一個字與不同的其它字組成詞組表達(dá)不同的意思，并且詞組長度越長，一般表示的含義越完整．所以公共序列的長度越長，則認(rèn)為相似度越大，相應(yīng)的權(quán)值系數(shù)要大些．公共序列的的權(quán)值系數(shù)按照下面給出的公式計算：記max=max(len(A),len(B)),min=min(len(A),len(B)),則長度為n的公共序列的權(quán)重為

3 相似度計算公式的合理性分析

3.1 對稱性分析，即SIM(A,B)=SIM(B,A)

由于我們事先進(jìn)行了重復(fù)詞處理，很明顯，如果A中的子串在B中存在，那么B中的該子串一定也在A中存在，所以必然SIM(A,B)=SIM(B,A).

3.2 相似度取值范圍的證明即SIM(A，B)≤1

首先根據(jù)前面公式的構(gòu)造過程，可以知道一定滿足：

(1)

且滿足

(2)

顯然，SIM(A，B)≥0，下面證明

SIM(A，B)<1

(1) 當(dāng)兩個文本序列完全不同時，即沒有任何字符相同，可知，

count[n]=0(n=1,…，min)，則

SIM(A，B)=0

(2) 當(dāng)兩個文本序列完全相同時，則count[max]=1,其余count[n]=0(n=1,…，max-1),此時Ωmax=1，則SIM(A,B)=1

(3) 當(dāng)兩個文本序列有部分相同時，

根據(jù)(2)和(3)式可以得出

命題得證．即我們構(gòu)造的相似度計算函數(shù)值介于[0,1]之間，是合理的．

4 實驗分析

為了進(jìn)一步說明該算法的有效性，我們構(gòu)造了5組數(shù)據(jù)．該算法已在WinXP操作系統(tǒng)，1.95 G內(nèi)存，300 GB硬盤環(huán)境，用VC6.0編程實現(xiàn)．

4.1 實驗數(shù)據(jù)比較

為了說明實驗效果，和單純通過統(tǒng)計相同字符個數(shù)來計算相似度的方法(表1中稱方法0)進(jìn)行比較．單純通過統(tǒng)計相同字符個數(shù)計算相似度公式：

其中Same為文本序列d1,d2相同字符的個數(shù)，nd1,nd2分別為文本序列d1、d2的字符個數(shù)．實驗數(shù)據(jù)和實驗結(jié)果見表1．

表1 實驗結(jié)果數(shù)據(jù)

為了使比較結(jié)果更直觀，我們通過直方圖來顯示效果(圖1)．橫坐標(biāo)為數(shù)據(jù)組序號，縱坐標(biāo)為相似度大?。?/p>

圖1 實驗結(jié)果柱形圖

從表中數(shù)值可以看出，明顯地本文相似度的計算更符合實際，更加合理．像第五組數(shù)據(jù)，不完全相同的兩組數(shù)據(jù)，我們沒有理由說它們的相似度為1．

4.2 實驗數(shù)據(jù)分析

從上面的實驗數(shù)據(jù)可以看出，本文得出的數(shù)值是符合正常邏輯的，且保證了SIM(A,B)=SIM(B,A)，是有效的．在公共序列頻度相同的情況下，連續(xù)公共序列長的文本要比連續(xù)公共序列短的文本間的相似度要大．比如“數(shù)據(jù)庫概論”與“數(shù)據(jù)庫原理”的連續(xù)公共序列長度要比“算法與設(shè)計”與“程序設(shè)計”間的連續(xù)公共序列長度要長，所以前一組的數(shù)據(jù)比后一組數(shù)據(jù)的相似度要大．

5 結(jié)論

文本相似性計算是一基礎(chǔ)而又重要的工作．本文提出的算法，適合所有的文本文檔．算法中考慮了序列順序，對于中文來講，順序很重要．所以從連續(xù)序列比對的角度進(jìn)行相似度計算，要比單純的計算相同字符個數(shù)更合理．算法中考慮了最大連續(xù)公共序列，并且序列長的賦予較大的權(quán)值系數(shù)，也符合“一般詞語越長，表達(dá)的意思越完整”的邏輯．但由于漢語的復(fù)雜性，相似度計算精確度問題還需從語義上進(jìn)行考慮，所以如何把語義和該方法結(jié)合起來將是我們下一步研究的方向．

[1]秦春秀,趙捧未,劉懷亮.詞語相似度計算研究[J].情報理論與實踐,2007,30(1):105～108．

[2]張煥炯,王國勝，鐘義信.基于漢明距離的文本相似度計算[J].計算機(jī)工程與應(yīng)用，2001,(19):21～22．

[3]曹 恬，周 麗，張國煊.一種基于詞共現(xiàn)的文本相似度計算[J].計算機(jī)工程與科學(xué)，2007,29(3):52～53,73．

[4]潘謙紅，王 炬，史忠植.基于屬性論的文本相似度計算[J].計算機(jī)學(xué)報，1999,22(6):651～655．

[5]E.Agirre,G.Rigau.A proposal for word sense disambiguation using conceptual distance[C].International Conference on Recent Advances in Natural Language Processing，1995，258～264．

[6]車萬翔,劉 挺,秦 兵,等.面向雙語句對檢索的漢語句子相似度計算[C].全國第七屆計算語言學(xué)聯(lián)合學(xué)術(shù)會議.北京:清華大學(xué)出版社,2003，520～526．

[7]F.S.Hu,Y．Guo.An Improved Algorithm of Word Similarity Computation Based on HowNet.In:Proc of the 2th International Conference on Computer Science and Automation Engineering，2012，5:372～376．

[8]V.L.Levenshtein.Binary codes capable of correcting deletions,insertions and reversals[J].Doklady Akademii Nauk SSSR,1966,163(4):707～710.

[9]刁興春，譚明超，曹建軍.一種融合多種編輯距離的字符串相似度計算方法[J].計算機(jī)應(yīng)用研究，2010,27(12)：4523～4525．

[10]孫德才，孫星明，張 偉，等.基于匹配區(qū)域特征的相似字符串匹配過濾算法[J].計算機(jī)研究與發(fā)展，2010,47(4)：663～670．