安見才讓

(青海民族大學(xué) 計(jì)算機(jī)學(xué)院，青海 西寧 810007)

0 引言

在自然語言處理領(lǐng)域，尤其在中文信息處理中，句子相似度的計(jì)算是一項(xiàng)基礎(chǔ)而核心的研究課題。長期以來一直是人們研究的一個(gè)熱點(diǎn)和難點(diǎn)，在自然語言處理的各個(gè)領(lǐng)域都有著非常重要的作用。如在基于實(shí)例的機(jī)器翻譯、基于語料庫的漢語教學(xué)系統(tǒng)、文檔自動(dòng)文摘系統(tǒng)[1]、基于常見問題集(FAQ)的機(jī)器問答系統(tǒng)[2]、語言的對比和信息檢索、信息過濾等研究中，句子相似度的計(jì)算都是其中關(guān)鍵的技術(shù)之一。

隨著語料庫語言學(xué)的興起，基于雙語語料庫的漢語教學(xué)得到越來越多學(xué)者的研究。基于漢藏語料庫的漢語教學(xué)系統(tǒng)以漢藏雙語對照的實(shí)例庫為主要的知識(shí)源，其基本原理是： 當(dāng)輸入一個(gè)待查詢的藏語句子時(shí)，系統(tǒng)便從雙語實(shí)例庫中搜索得到最相似的句子，再以該句子為查詢對象，找出與之相對應(yīng)的漢語句子。在基于漢藏語料庫的漢語教學(xué)系統(tǒng)和基于實(shí)例機(jī)器翻譯(EBMT)中，句子相似度的衡量是一個(gè)非常關(guān)鍵的步驟[3]，其直接影響檢索的質(zhì)量，最終影響檢索和翻譯的正確性。

如何快速從雙語實(shí)例庫中找出與輸入句子最相似的句子，是基于漢藏語料庫的漢語教學(xué)系統(tǒng)需解決的關(guān)鍵問題之一。

1 相關(guān)研究工作

按照對語句分析的深度，相似度計(jì)算方法主要有兩種： 基于向量空間模型的方法和基于語義的方法?；谙蛄靠臻g模型的方法把句子看成詞的線性序列，計(jì)算句子相似度只利用組成句子的詞的詞頻、詞性等信息[4]。由于不加任何結(jié)構(gòu)分析，該方法在計(jì)算句子之間的相似度時(shí)不能考慮句子整體結(jié)構(gòu)的相似性[5]。基于語義的方法，對句子進(jìn)行完全的句法與語義分析，對作比較的兩個(gè)句子進(jìn)行深層的句法分析，找出語義依存關(guān)系，并在依存分析結(jié)果的基礎(chǔ)上進(jìn)行相似度的計(jì)算[6]，這是一種深層結(jié)構(gòu)分析法。

在文獻(xiàn)[7]中, 提出了一種英語句子相似度的計(jì)算方法，作者通過定義一個(gè)距離函數(shù),計(jì)算從一個(gè)句子的詞序列變換到另一個(gè)句子的詞序列所進(jìn)行插入、刪除和替換單個(gè)單詞項(xiàng)的編輯次數(shù),以體現(xiàn)兩個(gè)句子間距離的大小，用兩個(gè)句子的最小距離作為衡量兩個(gè)句子的距離,該方法適用于英語及與英語同屬于一個(gè)語系的語言。

基于實(shí)例的機(jī)器翻譯系統(tǒng)中計(jì)算句子相似度，有人提出將句子劃分成幾個(gè)片段,用片段的長度和匹配值計(jì)算相似度。但是，利用的句子片段越小，片段的邊界越難以確定，歧義情況就越多，從而導(dǎo)致翻譯質(zhì)量的下降。為此，要建立一套相似度準(zhǔn)則[8-9]。郭銳等人利用句子長度、漢字字形、標(biāo)點(diǎn)符號(hào)三因素和遺傳算法、動(dòng)態(tài)規(guī)劃算法，通過實(shí)現(xiàn)古今漢語自動(dòng)句對齊，定義句子的相似關(guān)系[10]。也有人通過比較兩個(gè)句子的詞類信息串,進(jìn)行最優(yōu)匹配,得到一個(gè)結(jié)構(gòu)相似性的值[11]。文獻(xiàn)[12]中,作者提出了一種基于骨架依存分析的方法,該方法首先識(shí)別漢語句子的謂語中心詞,其次判斷兩個(gè)句子的謂語中心詞是否相似和它們的支配成分之間是否一一對應(yīng),如果是,則把謂語中心詞之間和支配成分之間的相似度之和作為兩個(gè)句子的相似度值。這種方法需要消耗大量的時(shí)間和人力。

本文提出的句子相似模型的算法在充分考慮句子的關(guān)鍵詞、同義詞和近義詞等因素的基礎(chǔ)上，用藏語句子關(guān)鍵詞的詞形相似度、句長相似度和連續(xù)單詞序列的相似度衡量兩個(gè)藏語句子的相似程度。采用的基于散列單詞倒排索引的方法能夠有效提高算法的查找速度。

2 句子相似模型

2.1 關(guān)鍵詞抽取

由藏語語言學(xué)知識(shí)可知，任何句子都是由關(guān)鍵成分(主、謂、賓)、修飾成分(定、狀、補(bǔ))和語法成分(格助詞、虛詞)構(gòu)成[13]。詞語的表達(dá)能力不僅與詞性相關(guān)，而且與句子結(jié)構(gòu)、句子長度、詞語的語法作用等因素也有關(guān)。例如謂語和修飾語對于句意表達(dá)的重要程度就是不同的。理想情況下，應(yīng)該分析出詞語的語法作用，據(jù)此計(jì)算出詞語的權(quán)重。但是在現(xiàn)階段，對句子的完全句法分析、詞語語法角色的完全識(shí)別是不可能的。另一方面詞語的詞性與詞語在句子中的語法角色是有一定對應(yīng)關(guān)系的： 名詞和代詞一般作主語和賓語，動(dòng)詞一般作謂語，形容詞、數(shù)詞和量詞一般作定語。主語、謂語和賓語對句子起主導(dǎo)作用，定語、狀語等成分對句子起輔助作用。因此，可以將一個(gè)句子中的所有名詞、代詞、動(dòng)詞和形容詞作為關(guān)鍵詞(下文所述關(guān)鍵詞也是此含義)看待。

2.2 有關(guān)定義和計(jì)算

圖1 字符串關(guān)系

兩個(gè)字符串間的相異度=(|r|+|s|)/(|q|+|r|+|s|)，相似度=|q|/(|q|+|r|+|s|)。

由此，可以得到句子的詞形相似度。句子的相似度除了與關(guān)鍵詞有關(guān)外，還與句子長度、句子中連續(xù)單詞序列的距離有關(guān)，下面給出具體的定義。

定義1： 詞形相似度WordSim(S1，S2)

從句子形態(tài)及詞形上來標(biāo)注句子的相似性，詞形相似度計(jì)算如下:

WordSim(s1,s2)

(1)

其中，SameWord(S1，S2)表示S1與S2中相同關(guān)鍵詞個(gè)數(shù)，Word(Si)表示Si中的關(guān)鍵詞個(gè)數(shù)，i=1，2。

由于名詞和動(dòng)詞(除助動(dòng)詞)在句子中起著非常重要的作用，而且動(dòng)詞比名詞承載著更多的信息量。所以在計(jì)算Word(Si)和SameWord(S1，S2)的時(shí)候也特意加大了相同關(guān)鍵詞中動(dòng)詞和名詞的重要程度。這一特性用詞性權(quán)重W表示，這樣，在此處計(jì)算相同關(guān)鍵詞的個(gè)數(shù)時(shí)，若兩個(gè)關(guān)鍵詞相同并且都是動(dòng)詞或名詞時(shí)，SameWord(S1，S2)和Word(Si)的一個(gè)動(dòng)詞權(quán)重計(jì)為W1，一個(gè)名詞權(quán)重計(jì)為W2，其他詞性權(quán)重均計(jì)為W3，即計(jì)算關(guān)鍵詞個(gè)數(shù)時(shí)增加相應(yīng)詞的詞性權(quán)重。

在語料庫中兩個(gè)相似句子長度(句子包含的單詞個(gè)數(shù))的比較實(shí)驗(yàn)中發(fā)現(xiàn)： 如果兩句子的長度差變大時(shí)，相似度會(huì)降低。兩個(gè)句子的長度越是接近，則兩個(gè)句子越相似。所以，兩個(gè)相似句子在長度上有一定的相似性。

定義2： 句長相似度LenSim(S1，S2)

(2)

其中Len(Si)表示Si中詞(包括格助詞和虛詞)的個(gè)數(shù)，i=1，2。

定義3： 句子連續(xù)單詞序列相似度

兩個(gè)句子，同時(shí)出現(xiàn)的連續(xù)單詞序列越長，其越相似。因?yàn)檫B續(xù)單詞序列包含的上下文信息比較多，其語法、語義也比較確定，相對單詞來講，連續(xù)單詞序列對自然語言的區(qū)分能力更強(qiáng)。

設(shè)兩個(gè)句子S1、S2被連續(xù)單詞分成k個(gè)連續(xù)塊， 則句子S1、S2的連續(xù)單詞序列相似度：

其中，M=max (Len(S1),Len(S2)),Ni為第i連續(xù)塊中總單詞數(shù)，wi,j為第i連續(xù)單詞塊中第j個(gè)單詞的詞性權(quán)值,wm為最長句子中第m個(gè)詞的詞性權(quán)值。

定義4： 在句子S1和S2中計(jì)算相同詞和連續(xù)單詞序列單詞個(gè)數(shù)的方法：

給定兩個(gè)句子S1、S2，構(gòu)造連續(xù)單詞序列矩陣simmatrix(m,n)。

其中，m，n分別是句子S1和S2的句長，boolij的取值：

在比較句子S1的第i個(gè)單詞與句子S2的第j個(gè)單詞時(shí)，如果第i個(gè)單詞與第j個(gè)單詞不相同，則在同義詞和近義詞知識(shí)庫中尋找第j個(gè)單詞的同義詞或近義詞是否與第i個(gè)單詞相同。

從矩陣可以發(fā)現(xiàn)： 連續(xù)單詞序列有1個(gè)，相鄰詞的個(gè)數(shù)為5，其中，動(dòng)詞有1個(gè)(值為5的元素)，名詞有2個(gè)(值為3的元素)，所以，

在計(jì)算連續(xù)單詞序列中的單詞個(gè)數(shù)時(shí)，如果當(dāng)前的兩個(gè)句子中沒有連續(xù)單詞序列，但句子中兩個(gè)相鄰的詞是名詞或形容詞且兩詞之間含有藏語語法成分時(shí)，可以考慮將兩個(gè)詞的前后順序交換后，看是否有連續(xù)的單詞序列。

3 算法描述

句子相似算法分為粗選算法和精選算法。粗選算法是從海量雙語實(shí)例庫中找出與輸入句子比較相似的候選句子集合，做為精選算法的基礎(chǔ)。

3.1 基于倒排索引和長度的多策略粗選算法

粗選算法的目標(biāo)是從海量雙語實(shí)例庫中篩選出一定數(shù)量的句子作為候選集合，集合中包含了與輸入句子基本相似的句子。

快速檢索是粗選算法的關(guān)鍵技術(shù)之一。為了提高檢索速度，粗選算法應(yīng)該計(jì)算簡單，不能過多考慮上下文。在此，提出一種簡單的計(jì)算方法： 如果兩個(gè)句子的長度相似度大于閾值k，則兩個(gè)句子趨于相似。

為了進(jìn)一步提高檢索速度，對語料庫中的句子建立散列單詞倒排索引。首先建立語料庫中句子的各詞散列表，然后將每個(gè)單詞所出現(xiàn)的多個(gè)句子編號(hào)SID構(gòu)建一個(gè)單鏈表，其中SID是句子編號(hào)，如圖2所示。

圖2 散列單詞倒排索引

粗選算法的具體過程是：

(1) 對輸入的藏文句子進(jìn)行分詞和詞性標(biāo)注，獲得單詞鏈表;

(2) 從散列單詞倒排索引中獲得單詞鏈表中各單詞的句子編號(hào)鏈表，并獲得相應(yīng)的候選句子集合p1;

(3) 用句長相似度對集合p1的候選句子進(jìn)行計(jì)算，選擇句長相似的P個(gè)句子作為新的候選句子集合p2；

(4) 對集合p2按句長的相似度作降序處理。

最后對獲得相似度取值最大的P個(gè)句子作為粗選集合。

3.2 基于詞形相似度和連續(xù)單詞序列相似度的多策略精選算法

經(jīng)過粗選之后，獲得粗選集合的句子數(shù)量已經(jīng)縮小到P個(gè)(如200)。因此可以對這些數(shù)量較少的句子進(jìn)行更復(fù)雜的計(jì)算，來精確地找出與輸入句子最為相似的句子。提出一種基于詞形相似度和連續(xù)單詞序列相似度的方法。

記兩個(gè)作比較的句子為S1和S2，S1與S2的相似度記為Sim(S1,S2)，則:

其中：λ1+λ2=1，且λ1>λ2>0，λ1和λ2是經(jīng)驗(yàn)值。

該算法中的關(guān)鍵詞抽取部分涉及分詞與詞性標(biāo)注(其他算法大部分僅涉及分詞)，在計(jì)算相似度時(shí)還需要借助藏語同義詞和近義詞知識(shí)詞庫,對同義詞或近義詞進(jìn)行替換,以提高相似度。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果

因?yàn)闆]有可用于藏文句子相似度測試的標(biāo)準(zhǔn)測試語料,我們選用九年義務(wù)教育六年制和三年制小學(xué)及初級中學(xué)18本《漢語》教科書(藏族地區(qū)使用)的翻譯內(nèi)容作為實(shí)驗(yàn)語料。語料含有8 006個(gè)語句，從中手工獲取166個(gè)藏語句子構(gòu)成標(biāo)準(zhǔn)集, 把標(biāo)準(zhǔn)集中的句子依據(jù)相似程度分為8類,每類有19～21個(gè)句子,這樣就保證了在標(biāo)準(zhǔn)集中每個(gè)句子都有17～21個(gè)相似句子，其余的7 840個(gè)語句作為噪音句子構(gòu)成噪音集。另外，我們建設(shè)了一個(gè)藏語同義詞和近義詞知識(shí)庫，其中含有652個(gè)詞條，用于計(jì)算藏文句子相似度時(shí)，可以對同義詞或近義詞進(jìn)行替換。

衡量指標(biāo)選用了準(zhǔn)確率P、查全率R和平均調(diào)和值F三個(gè)指標(biāo):

實(shí)驗(yàn)結(jié)果如表1。方法1代表詞形相似度算法，方法2代表本文提出的相似度算法公式(4)，其中選取參數(shù)λ1=0.81、λ2=0.19。

表1 實(shí)驗(yàn)結(jié)果

4.2 實(shí)驗(yàn)結(jié)果分析

1) 從計(jì)算的結(jié)果可以看出，采用方法2所得查全率比方法2的查全率高，雖然區(qū)別不大，但準(zhǔn)確率明顯提高。由于方法2中采用了連續(xù)單詞序列相似度因素，使方法2對自然語言的區(qū)分能力增強(qiáng)。

2) 方法1和方法2的時(shí)間復(fù)雜度: 設(shè)句子S1、S2的句長分別為m、n，語料庫中的句子總數(shù)為s，同義詞和近義詞詞庫中詞條總數(shù)為w，散列倒排索引中的一個(gè)單鏈表的長為k,則方法1和方法2的時(shí)間耗費(fèi)如公式(8)和(9)：

T(s)=s×m×n

(8)

(9)

其中，100為方法2中經(jīng)粗選算法計(jì)算后所得集合元素之總和。

公式(8)中的m、n和公式(9)中的m、n、w分別對T(s)和T(s)的影響比較小，作用相對穩(wěn)定。T(s)是語料庫中句子總數(shù)s的函數(shù)，T(k)是單鏈表長度k的函數(shù)，k<T(k)，如，n=20,k=1 000,w=8 000,s=2 800時(shí)，T(s)>T(k)。

通過對方法1和方法2算法的時(shí)間耗費(fèi)分析可得，方法2在計(jì)算速度上應(yīng)該有所提高，但受到實(shí)驗(yàn)樣本數(shù)的限制，實(shí)驗(yàn)過程中沒有得到體現(xiàn)。

在實(shí)驗(yàn)過程中也發(fā)現(xiàn)一些有待解決的問題： 同義詞、近義詞的詞庫不夠充足，沒有考慮藏語動(dòng)詞形態(tài)還原等一系列問題。

5 結(jié)論和下一步工作

采用基于句長相似度的算法和基于散列單詞倒排索引的粗選方法，快速從語料庫中篩選出了候選句子集合，多策略精選算法采用基于詞形相似度的算法和基于連續(xù)單詞序列相似度的算法衡量兩個(gè)藏語句子的相似程度，能夠有效地從候選句子集合中找出與輸入句子最相似的句子。

下一步工作是繼續(xù)擴(kuò)大語料庫的規(guī)模，并引入藏語動(dòng)詞形態(tài)學(xué)、句法結(jié)構(gòu)知識(shí)和語義知識(shí)，將其融入到本算法中。

[1] 張奇，黃萱菁，吳立德.一種新的句子相似度度量及其在文本自動(dòng)摘要中的應(yīng)用[J].中文信息學(xué)報(bào)，2005，19(2):93-99.

[2] 張亮，馮沖，陳肇雄.基于語句相似度計(jì)算的FAQ自動(dòng)回復(fù)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27(4):720-723.

[3] 王榮波，池哲儒.基于詞類串的漢語句子結(jié)構(gòu)相似度計(jì)算方法[J].中文信息學(xué)報(bào)，2005，19(1):21-29.

[4] 周法國，楊炳儒.句子相似度計(jì)算新方法及在問答系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(1)： 165-178.

[5] 呂學(xué)強(qiáng)，任飛亮，黃志丹,等.句子相似模型和最相似句子查找算法[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2003，24(6)： 531-534.

[6] 蔡?hào)|風(fēng)，白宇,于水,等.一種基于語境的詞語相似度計(jì)算方法 [J].中文信息學(xué)報(bào)，2010，24(3)： 24-28.

[7] Federica Mandreoli, Riccardo Martoglia, and Paolo Tiberio. Searching Similar(Sub) Sentences for Example-Based Machine Translation[C]//Atti del Decimo ConvegnoNazionale su Sistemi Evoluti per Basi di Dati(SEBD 2002),Isolad Elba,Italy,2002.

[8] 侯宏旭，劉群,那順烏日圖.基于實(shí)例的漢蒙機(jī)器翻譯[J].中文信息學(xué)報(bào)，2007，21(4)： 65-72.

[9] 馮志偉.基于語料庫的機(jī)器翻譯系統(tǒng)[J]. 術(shù)語標(biāo)準(zhǔn)化與信息技術(shù),2010,1:28-35.

[10] 郭銳，宋繼華,廖敏.基于自動(dòng)句對齊的相似古文句子檢索[J].中文信息學(xué)報(bào)，2008，22(2)： 87-91.

[11] 王榮波，池哲儒.基于詞類串的漢語句子結(jié)構(gòu)相似度計(jì)算方法[J].中文信息學(xué)報(bào)，2005，19(1)： 21-29.

[12] 穗志方,俞士汶.基于骨架依存樹的語句相似度計(jì)算模型[C]//中文信息處理國際會(huì)議論文集(ICCIP 98).北京:清華大學(xué)出版社,1998,458-465.

[13] 格桑居冕.實(shí)用藏文文法[M].四川民族出版社，1987.