藏語句子相似度算法的研究

安見才讓

(青海民族大學 計算機學院，青海 西寧 810007)

0 引言

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

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

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

1 相關研究工作

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

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

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

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

2 句子相似模型

2.1 關鍵詞抽取

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

2.2 有關定義和計算

圖1 字符串關系

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

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

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

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

WordSim(s1,s2)

(1)

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

3 算法描述

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

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

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

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

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

圖2 散列單詞倒排索引

粗選算法的具體過程是：

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

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

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

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

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

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

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

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

其中：λ1+λ2=1，且λ1>λ2>0，λ1和λ2是經驗值。

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

4 實驗結果與分析

4.1 實驗設計和結果

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

衡量指標選用了準確率P、查全率R和平均調和值F三個指標:

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

表1 實驗結果

4.2 實驗結果分析

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

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

T(s)=s×m×n

(8)

(9)

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

公式(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時，T(s)>T(k)。

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

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

5 結論和下一步工作

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

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

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

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

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

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

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

[6] 蔡東風，白宇,于水,等.一種基于語境的詞語相似度計算方法 [J].中文信息學報，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] 侯宏旭，劉群,那順烏日圖.基于實例的漢蒙機器翻譯[J].中文信息學報，2007，21(4)： 65-72.

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

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

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

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

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