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

蔣仁龍，蔣子龍

（1.黔南民族師范學(xué)院外語(yǔ)系，貴州都勻558000；2.武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢430070）

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

蔣仁龍1，蔣子龍2

（1.黔南民族師范學(xué)院外語(yǔ)系，貴州都勻558000；2.武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢430070）

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

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

1 引言

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

2 設(shè)計(jì)步驟和算法

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

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

2.1 排除停用詞

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

2.2 抽取詞干

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

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

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

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

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

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

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

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

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

當(dāng)詞太短時(shí)，此算法并不會(huì)移除后綴，詞的長(zhǎng)度被它的度量m給出。這個(gè)方法沒(méi)有語(yǔ)言學(xué)基礎(chǔ)。它僅僅被觀察到 m能被相當(dāng)高效地用來(lái)幫助決定是否是明智的對(duì)于脫離后綴。例如，如下兩個(gè)列表：

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

經(jīng)過(guò)抽取詞干后，詞匯最終以最本質(zhì)的構(gòu)詞部分呈現(xiàn)。

2.3 構(gòu)建q-gram層次空間及進(jìn)行相似性計(jì)算

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

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

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

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

定義2.曼哈坦距離[12,13]：對(duì)于兩個(gè)點(diǎn)x1={x1,1，x1,2，x1,3，…x1,m}和x2={x2,1，x2,2，x2,3，…x2,m}，兩點(diǎn)間的距離有：

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

兩個(gè)記錄r1，r2在對(duì)應(yīng)的q-gram空間的相似性可表達(dá)為式（1）：

則上例關(guān)系R所對(duì)應(yīng)的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空間是一個(gè)以各不同的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空間的點(diǎn)坐標(biāo)為(1,2,2,1,1,0,0,1,1,1)，r2在1-gram空間的點(diǎn)坐標(biāo)為(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空間是一個(gè)以各不同的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空間的點(diǎn)坐標(biāo)為(1,2,1,1,0,1,1, 1,0)，r2在2-gram空間的點(diǎn)坐標(biāo)為(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空間是一個(gè)以各不同的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空間的點(diǎn)坐標(biāo)為(1,1,1,1,1,0,1,0)，r2在3-gram空間的點(diǎn)坐標(biāo)為(1,1,0,0,0,1,0,1)，Sim3(r1,r2)=0.25。

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

[3]薛曄偉,沈鈞毅,張?jiān)?一種編輯距離算法及其在網(wǎng)頁(yè)搜索中的應(yīng)用[J].西安交通大學(xué)學(xué)報(bào),2008,42(12):27-28.

[4]楊志豪,林鴻飛,李彥鵬.基于編輯距離和多種后處理的生物實(shí)體名識(shí)別[J].計(jì)算機(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過(guò)濾的近似串匹配技術(shù)研究[D].長(zhǎng)沙:湖南大學(xué),2012.

[7]江兆中.基于語(yǔ)境和停用詞驅(qū)動(dòng)的中文自動(dòng)分詞研究[D].合肥:合肥工業(yè)大學(xué),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]韓習(xí)武.機(jī)器翻譯中語(yǔ)義因素的理論分析[D].哈爾濱：黑龍江大學(xué),2001.

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

[16]關(guān)曉薇.基于語(yǔ)義語(yǔ)言的機(jī)器翻譯系統(tǒng)中若干關(guān)鍵問(wèn)題研究[D].大連：大連理工大學(xué),2009.

（責(zé)任編輯：魏登云）

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）

蔣仁龍，男，湖北天門人，黔南民族師范學(xué)院外語(yǔ)系碩士。研究方向：語(yǔ)言學(xué)、計(jì)算語(yǔ)言學(xué)、認(rèn)知詩(shī)學(xué)。蔣子龍，男，湖北天門人，武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院在讀博士。研究方向：機(jī)器學(xué)習(xí)。