蔣仁龍，蔣子龍

（1.黔南民族師范學院外語系，貴州都勻558000；2.武漢理工大學計算機科學與技術學院，湖北武漢430070）

基于q-gram層次空間的機器翻譯中句子相似度計算探析

蔣仁龍1，蔣子龍2

（1.黔南民族師范學院外語系，貴州都勻558000；2.武漢理工大學計算機科學與技術學院，湖北武漢430070）

機器翻譯由于其簡易性和速度快而成為一個熱門的研究對象，然而其翻譯質量低也是一個不爭的事實。利用q-gram層次空間和Porter Stemming算法，設計了一種計算句子匹配率的方法，并利用算例進行了詳細的闡釋，從而給機器翻譯及英文文本比較提供了一種思路。實驗結果表明，該方法在目前基于規(guī)則與實例結合的句子相似度計算方法中是可行的。

Porter Stemming Algorithm；q-gram層次空間；相似度

1 引言

機器翻譯系統(tǒng)[1]通?？稍试S針對特定領域加以客制化，以改進翻譯的結果。如在政府公文或法律文件中，這類型的句子通常比較正式和制式化，使用機器翻譯的結果較為方便。進一步，對于待翻譯的句子，通常會從歷史庫中找與之相似的已完成句子，將翻譯提示給使用系統(tǒng)的譯員，以提高翻譯速度與質量。而快速的從相關歷史譯文中找到相似的原文，并取得譯文參考，這就涉及到比較英文句子的匹配率。本文以比較典型的英文中的簡單句、復合句和復雜句的句子相似度為例，筆者測試過100組這樣的句子，證實該方法在目前基于規(guī)則[2]與實例結合的句子相似度計算方法的效度較高。

2 設計步驟和算法

對于兩個待比較的英文句子，我們首先要去除其中沒有實際意義的輔助性詞匯，如虛詞，介詞等。其次是對每一個有實際意義的詞匯，從它的名詞單復數(shù)，-ed,-ing等形式中找出最能代表其意義的詞干部分，這樣才能得出最有比較價值的部分。

相似的英文句子中詞項的度量方式通常使用兩種：一種為編輯距離(edit distance)[3,4]；另一種為q-gram相似度[5,6]。本文選取Tri-gram(3-gram)相似性度量作為統(tǒng)一的相似性標準。分三個步驟計算其相似度去除停用詞提取詞干構建q-gram層次空間；IV進行相似性計算。

2.1 排除停用詞

停用詞[7]（STOPWORDS）是指在一篇文檔中只起到組成句子結構的作用，出現(xiàn)頻率較高，卻不具備實際意義的詞匯。關鍵詞（KEYWORDS）才是句意核心的所在，因此去掉停用詞有利于提高匹配的精確度。我們選取數(shù)據(jù)堂英文停用詞表[8]進行實驗。

2.2 抽取詞干

對一篇英文文檔，經過排除停用詞后，剩下的即是相對信息含量較高的詞匯。而在英文中，形容詞和副詞有比較級和最高級形式，動詞有現(xiàn)在時、過去時、完成時、將來時、動名詞形式，名詞有復數(shù)形式。這些詞雖然形式不同，本質的含義卻是相同的，如果不加分析，就會影響句子匹配的精確度。我們采用ThePorterStemmingAlgorithm進行詞干抽取。算法設計思想[9,10]如下：

如果一個單詞的元音-輔音分別由V，C表示，長度大于0的VVV…序列用V表示，長度大于0的CCC…序列是用C表示，任意一個單詞或某單詞的一部分，都能表示為如下四種形式，CVCV…C；CVCV…V；VCVC…C；VCVC…V；也可以表示為一種總的單一形式[C]VCVC…[V]，方括號表示其中內容任意出現(xiàn)，使用(VC){m}來表示VC重復m次，總的單一形式又能表示為[C](VC){m}[V]。m被稱為任意單詞或單詞部分在這種形式中的度量。示例如下：

移除后綴的規(guī)則以下面的形式給出(condition) S1-〉S2，意思是如果一個單詞以后綴S1結尾，且S1之前的詞滿足給定的條件，用S2替換S1。條件通常根據(jù)m給出，例如：(m〉1)EMENT-〉，此例中S1是“EMENT”，S2是“null”。它將會映射“REPLACEMENT”到“REPLAC”，因為“REPLAC”是m=2的單詞部分。

條件部分也可能包含如下：

條件部分可能也包含用and，or，not連接的表達式，因此(m〉1 and(*S or*T))表示一個m〉1且以S or T結尾的詞，而(*d and not(*L or*S or*Z))表示一個除了L,SorZ外的雙輔音結尾的詞。像這樣的詳細條件很少被要求。

對下面寫出的一套規(guī)則集，只有一個服從，這個規(guī)則就是對于給出的單詞能夠最長匹配S1的規(guī)則。例如，

（此處假設所有的條件都為空），CARESSES映射為CARESS，因為SSES是S1最長的匹配。同樣地CARESS映射為CARESS(S1=’SS’)，CARES映射為CARE(S1=’S’)。在下面的規(guī)則中，其應用的例子，成功或失敗，以小寫字母在右邊給出。算法現(xiàn)在遵守：

映射到單個字符的規(guī)則導致了雙字符對的移除。-E被放回為-AT,-BL and-IZ,因此-ATE,-BLE和–IZE隨后能被識別。E能被移除在step4。

字符串 S1能通過程序轉換單詞的倒數(shù)第二字母來實現(xiàn)。這給了字符串 S1的可能值相當大的突破。事實上step 2中的S1-字符串以它們倒數(shù)第二字母的字母順序出現(xiàn)在這里。相似技巧也應用在其他步驟。

當詞太短時，此算法并不會移除后綴，詞的長度被它的度量m給出。這個方法沒有語言學基礎。它僅僅被觀察到 m能被相當高效地用來幫助決定是否是明智的對于脫離后綴。例如，如下兩個列表：

-ATE被從listB中移除出去，但是沒有從listB中移除。這意味著詞對DERIVATE/DERIVE,ACTIVATE/ACTIVE,DEMONSTRATE/DEMONS-TRABLE,NECESSITATE/NECESSITOUS,將會合并在一起。事實是沒有是被前綴的嘗試被做來使結果看起來稍微不一致。因而PRELATE沒有丟失-ATE,而是ARCHPRELATE變成ARCHPREL.實際上因為前綴的出現(xiàn)減少了錯誤沖突的可能性。

經過抽取詞干后，詞匯最終以最本質的構詞部分呈現(xiàn)。

2.3 構建q-gram層次空間及進行相似性計算

經過處理后的句子由各個詞項(Term)構成，可將各個詞項當作字符串來處理。關系R的字段數(shù)表示為dom(R)，項j的所有字符串集合記為R[j]，一個句子記為r，r的第j個項值記為r［j］。定義一個qgram是一個由長度為q的連續(xù)字符組成的字符串，故一個總長度為l(l≥q)的字符共有l(wèi)-q+1個qgram。字符構成上相同的 q-gram在不同的詞項中應區(qū)別看待，為此，用一個二元組〈j,l1l2…lq〉表示第j個項中出現(xiàn)的一個字符構成上為j,l1l2…lq的q-gram。Gq(r)表示句子r的所有詞項的q-gram組成的集合(在計算中q常取1，2，3)。

表1 示例數(shù)據(jù)

本文中用freqj(l1l2…lq)表示〈j,l1l2…lq〉這個屬性在關系的所有記錄中的最大出現(xiàn)頻率，既freqj(l1l2…lq)=max{〈j,l1l2…lq〉在Gq（r）中的重復數(shù)|r∈R}。用F1reqj(l1l2…lq)表示〈j,l1l2…lq〉這個屬性在關系的r1記錄中的出現(xiàn)頻率，用F2reqj(l1l2…lq)表示〈j,l1l2…lq〉這個屬性在關系的r2記錄中的出現(xiàn)頻率。

其中m是q-gram空間[11]的維數(shù)。

定義2.曼哈坦距離[12,13]：對于兩個點x1={x1,1，x1,2，x1,3，…x1,m}和x2={x2,1，x2,2，x2,3，…x2,m}，兩點間的距離有：

滿足：①d(x1,x2)≥0，距離是一個非負數(shù)值；②d (x1,x2)=0，點與自身的距離為0；③d(x1,x2)=d(x2, x1)，距離函數(shù)具有對稱性；④d(x1,x2)≤d(x1,h)+d(h, x2)，從點x1到x2的直接距離不會大于途經任何其他點h的距離。

兩個記錄r1，r2在對應的q-gram空間的相似性可表達為式（1）：

則上例關系R所對應的1-gram空間、2-gram空間、3-gram空間如下：

（1）1-gram空間。由于freq1(a)=1，freq1(b)=2，freq1(c)=2，freq1(d)=1，freq1(e)=1，freq1(f)=1，freq2(w)=1，freq2(x)=1，freq2(y)=1，freq2(z)=1，則所形成的1-gram空間是一個以各不同的1-gram作為維度的10維空間：1×2×2×1×1×1×1×1×1×1。

表2 1-gram的10維空間Tab.2 10-dimensional space of 1-gram

r1在1-gram空間的點坐標為(1,2,2,1,1,0,0,1,1,1)，r2在1-gram空間的點坐標為(1,1,1,1,0,1,1,0,1,1)，Sim1(r1,r2)=0.5。

（2）2-gram空間。由于freq1(ab)=1，freq1(bc)=2，freq1(cd)=2，freq1(de)=1，freq1(df)=1，freq1(eb)=1，freq2(xy)=1，freq2(yz)=1，freq2(zw)=1，因此2-gram空間是一個以各不同的2-gram作為維度的9維空間：1×2 ×2×1×1×1×1×1×1。

表3 2-gram的9維空間Tab.3 9-dimensional space of 2-gram

可知r1在2-gram空間的點坐標為(1,2,1,1,0,1,1, 1,0)，r2在2-gram空間的點坐標為(1,1,1,0,1,0,0,1,1)，Sim2(r1,r2)=0.4。

（3）3-gram空間。由于freq1(abc)=1，freq1(bcd)=1，freq1(cde)=1，freq1(deb)=1，freq2(ebc)=1，freq2(cdf)=1，freq2(xyz)=1，freq1(yzw)=1，因此3-gram空間是一個以各不同的3-gram作為維度的8維空間：1×1×1× 1×1×1×1×1。

表4 3-gram的8維空間Tab.4 8-dimensional space of 3-gram

可知r1在3-gram空間的點坐標為(1,1,1,1,1,0,1,0)，r2在3-gram空間的點坐標為(1,1,0,0,0,1,0,1)，Sim3(r1,r2)=0.25。

根據(jù)實驗統(tǒng)計，當q取1，2，3時，得出的q-gram空間和曼哈坦距離對相似度計算影響最大，我們根據(jù)重要程度和經驗分別對其賦予不同的權重：k1=0.2；k2=0.4；k3=0.4。

最后，兩條記錄的相似度可由公式（2）得出：

計算出上例中兩句子的匹配率SIM(r1,r2)=0.36。

3 實驗結果與分析

隨意抽取四組比較句子，得出它們的相似度(見表5）。

表5 相似度比較結果Tab.5 The comparison results of similarity

通過以上表格可以發(fā)現(xiàn)該方法在計算兩個句子相似度上，充分考慮了關鍵詞對整個句子的影響，并能夠用有效的方法提取出關鍵詞中具有實際意義的主干部分，在此基礎上運用基于q-gram層次空間的方法對關鍵詞詞干的相似性進行了科學精確的計算，得出的總體結果在目前的基于規(guī)則的計算方法中效果是很好的。

4 結束語

句子相似度匹配是機器翻譯的一個重要環(huán)節(jié)，計算方法的優(yōu)劣直接影響到翻譯的最終效果。機器翻譯誕生50多年以來，因為該領域的復雜性，即使現(xiàn)在基于語義的智能方法[14,15,16]逐漸應用到其中來，發(fā)展也一直較為緩慢?；谝?guī)則的比較方法因其快速、高效仍然占有重要的地位，探討更有效的基于規(guī)則的句子比較方法將是本文下一步的工作。

[1]郭永輝.英漢機器翻譯系統(tǒng)關鍵技術研究[D].鄭州：解放軍信息工程大學,2006.

[2]馬建軍.基于規(guī)則和統(tǒng)計的機器翻譯方法歧義問題比較分析[J].大連理工大學學報(社會科學版),2010,31(3):114-119.

[3]薛曄偉,沈鈞毅,張云.一種編輯距離算法及其在網頁搜索中的應用[J].西安交通大學學報,2008,42(12):27-28.

[4]楊志豪,林鴻飛,李彥鵬.基于編輯距離和多種后處理的生物實體名識別[J].計算機工程,2008,34(17):11-14.

[5]Esko Ukkonen.Approximate string-matching with q-grams and maximal matches[J].Theoretical Computer Science, 1992,92(1):191-192.

[6]孫德才.基于q-gram過濾的近似串匹配技術研究[D].長沙:湖南大學,2012.

[7]江兆中.基于語境和停用詞驅動的中文自動分詞研究[D].合肥:合肥工業(yè)大學,2010.

[8]英文停用詞表[EB/OL].http://www.datatang.com/data/ 13603.2015-1-7.

[9]M.F.Porter.An algorithm for suffix stripping[J].Program, 1980，(3):130-137.

[10]The Porter Stemming Algorithm[EB/OL].http://snowball. tartarus.org/algorithms/porter/stemmer.html.2014-12-18.

[11]Esko Ukkonen.Approximate string-matching with q-grams and maximal matches[J].Theoretical Computer Science, 1992,92(1):191-192.

[12]Karenkukich.Techniquesforautomaticallycorrectingwords in text[J].ACM Computing Surveys,1992,24(4):377-439.

[13]Robit Ananthak Rishna,Surajit Chaudhuri,Venkatesh Canti.Eliminating fuzzy duplicates in data warehouses[M].San Francisco:Morgan Kaufmann,2002:586-597.

[14]韓習武.機器翻譯中語義因素的理論分析[D].哈爾濱：黑龍江大學,2001.

[15]李丹,許霄羽,楊悅.基于語義網技術的網絡機器翻譯研究[J].現(xiàn)代電子技術,2011,34(4):107-112.

[16]關曉薇.基于語義語言的機器翻譯系統(tǒng)中若干關鍵問題研究[D].大連：大連理工大學,2009.

（責任編輯：魏登云）

An Exploration and Analysis of Sentence Similarity Computing in Machine Translation Based on the“q-gram”Hierarchical Space

JIANG Ren-long1，JIANG Zi-long2
(1.Department of Foreign Language and Literature,Qiannan Normal College for Nationalities,Duyun 558000,China;2.School of Computer Science and Technology,Wuhan University of Technology,Wuhan 430070,China)

Machine translation,with the features of simplicity and fast-speed,becomes a hot research object.However,it is the truth that its qualities are relatively low.Using the algorithm of q-gram hierarchical space and Porter Stemming,this paper designs a kind of method to calculate the matching ratio of sentences and makes detailed explanation with examples,which provides an idea for comparing the machine translation with English text.The result demonstrates that this kind of algorithm is suitable for calculating the sentence similarity basis on rules and instances.

Porter Stemming Algorithm;q-gram hierarchical space;similarity

TP3-0

A

1009-3583（2015）-0089-05

2015-07-12

教育部人文社科基金資助（13YJCZH028）

蔣仁龍，男，湖北天門人，黔南民族師范學院外語系碩士。研究方向：語言學、計算語言學、認知詩學。蔣子龍，男，湖北天門人，武漢理工大學計算機科學與技術學院在讀博士。研究方向：機器學習。