嚴(yán)燦勛

(解放軍外國語學(xué)院 語言工程系，河南 洛陽 471003)

二分圖頂點配對模型下的英漢句子對齊研究

嚴(yán)燦勛

(解放軍外國語學(xué)院 語言工程系，河南 洛陽 471003)

英漢平行文本句子對齊可以視為一個二分圖頂點配對模型。利用完全基于英漢詞典的雙語句子相關(guān)性評價函數(shù)，能夠?qū)Χ謭D的“頂點對”進(jìn)行加權(quán)。該文提出的頂點配對句子對齊方法首先獲取二分圖全局最大權(quán)重頂點配對作為臨時錨點；在此基礎(chǔ)上，根據(jù)句子先后順序，局部最大權(quán)重頂點配對和英漢句長比的值域范圍，糾正臨時錨點中的錯誤，補(bǔ)充錨點序列未覆蓋的合法頂點對，同時劃分句對，實現(xiàn)句子對齊處理。在對比實驗中該句子對齊方法優(yōu)于Champollion句子對齊系統(tǒng)。從實驗對比結(jié)果和實踐效果看，該句子對齊方法可行。

句子對齊；雙語詞典；平行文本；二分圖；頂點配對；頂點對

1 引言

英漢漢英句子對齊平行語料庫在英譯漢和漢譯英翻譯訓(xùn)練、英語教學(xué)、英漢漢英詞典編纂、英漢漢英計算機(jī)輔助翻譯，以及圍繞英漢漢英進(jìn)行的各項自然語言處理工作中有著廣泛的應(yīng)用[1-2]。在進(jìn)行短語、詞匯對齊前一般也需要首先實現(xiàn)句子對齊。句子對齊平行語料是效用最大的平行語料[3]。

常見的句子對齊方法有三種： (1)基于句長的方法，有根據(jù)單詞個數(shù)計算句長的[4]，也有根據(jù)字符長度計算的[5]； (2)基于雙語詞匯互譯信息的方法，詞匯互譯信息的獲取有基于語料的[6-8]，也有基于雙語詞典的[3]； (3)句長和雙語詞匯互譯信息混合的方法[9-11]。當(dāng)前雙語句子對齊研究仍然基于上述三種方法[12-14]。

本文提出一個以二分圖頂點配對為數(shù)學(xué)模型的、基于英漢詞典的英漢平行語料句子對齊方法，簡稱頂點配對句子對齊方法。初衷是為解決各軍事子領(lǐng)域平行語料規(guī)模小，用基于統(tǒng)計的句子對齊方法處理正確率低的問題。該句子對齊方法適用于各領(lǐng)域、各種規(guī)模英漢平行語料的句子對齊處理。下文第二節(jié)分析二分圖模型和句子對齊的關(guān)系；第三節(jié)介紹二分圖模型下句子對齊的相關(guān)研究；第四節(jié)詳細(xì)闡述二分圖頂點配對句子對齊方法；第五節(jié)介紹頂點配對句子對齊方法與Champollion句子對齊方法的對比實驗；第六節(jié)總結(jié)全文并展望下一步工作。

2 二分圖模型和句子對齊

2.1 句子對齊的二分圖模型

句子對齊是一個以給定的雙語對譯平行文本為二分圖，為原語和譯語實現(xiàn)“最小對譯句組”匹配的問題[15]?！白钚ψg句組”也稱為句對或者句珠[4]。二分圖又稱二部圖。設(shè)G=是一個無向圖，如果頂點集V可分為兩個互不相交的子集，E為邊集，并且圖中的每條邊e=(vi,vj)所關(guān)聯(lián)的兩個頂點vi和vj分別屬于兩個子集(viin VA,vjin VB)，則稱圖G為一個二分圖。例如，圖1“句子對齊的二分圖模型”的英語句子集中有頂點En1，En2，……，En8，漢語句子集中有頂點Ch1，Ch2，……，Ch10。頂點子集和互不相交。它們之間的句子對齊出現(xiàn)如圖1中的邊所示的多個句對，即： En1:Ch1；En2:(Ch2,Ch3)； (En3,En4):Ch4； (En5,En6):(Ch5,Ch6)；En7:(Ch7,Ch8,Ch9)；En8:Ch10。

2.2 二分圖頂點配對與句子對齊的關(guān)系

圖1“句子對齊的二分圖模型”中任意一條邊e=(Eni,Chj)所關(guān)聯(lián)的兩個頂點Eni和Chj分別屬于兩個不同的頂點子集(Eniin EN, Chjin CH)。邊e=(Eni,Chj)也稱為頂點對，找出合法的頂點對的過程叫頂點配對。理論上，頂點子集中的任一頂點都可能與頂點子集中的任一頂點配對，反之亦然。但是在句子對齊中，頂點配對應(yīng)該在一定條件下按句子順序從頭向尾依次實現(xiàn)，并且頂點對組合成句對分多種類型。參看圖1,1∶1類型的句對(En1∶Ch1和En8∶Ch10)對應(yīng)二分圖中的一條邊，或者說與其他邊無公共端對；其他1∶n、n∶1和m∶n(m>1，n>1)類型的句對在二分圖中對應(yīng)多條依次關(guān)聯(lián)的邊，1∶n和n∶1類型的句對中n條邊共享一個公共端點，m∶n類型的句對中頂點對最多可以出現(xiàn)(m+n-2)個公共端點，最少有兩個公共端點。二分圖頂點配對模型下，句子對齊可以視為一項根據(jù)二分圖頂點配對結(jié)果完成“最小對譯句組”劃分的任務(wù)。

圖1 句子對齊的二分圖頂點配對模型

2.3 二分圖匹配與句子對齊的關(guān)系

二分圖匹配不同于二分圖頂點配對。二分圖匹配指: 如果二分圖G中有邊集M?E，且在M中任意兩條邊都沒有公共端點，稱邊集M為二分圖G的一個匹配。最大權(quán)重匹配就是按一定要求給E中各條邊加權(quán)，存在一個M，M中的所有邊的權(quán)重之和最大，這個M就是最大權(quán)重匹配[16]。句子對齊中，簡單的二分圖匹配提供的是1∶1類型的句對，不符合句子對齊實情，需要修正。

3 二分圖模型下句子對齊相關(guān)研究

3.1 基于1∶1型句對二分圖匹配的段落重組

李維剛等[17]在研究雙語語料庫段落重組對齊方法時利用二分圖及匹配的概念對段落對齊進(jìn)行了形式化描述。他們將段落重組對齊模型定義為一個二分圖的“最優(yōu)對齊匹配”。在尋找段落重組對齊時，句對的選取首先是根據(jù)一個基于長度的評價函數(shù)，從頭向尾依次選取待對齊句子中最可能成立的1∶1型句對，選取條件是該句對的權(quán)值小于某一指定閾值；然后，再利用一個基于詞典的評價函數(shù)對這樣的1∶1型句對進(jìn)行校驗，符合詞典校驗的句對則成為段落重組對齊的錨點，或定位點；根據(jù)錨點實現(xiàn)段落重組對齊。

根據(jù)李維剛等對段落重組對齊的二分圖“最優(yōu)對齊匹配”模型的描述，匹配中的句對不存在一對多或交叉對應(yīng)的情況，既滿足二分圖匹配要求，也符合段落重組對齊錨點的實際情況。以二分圖匹配為模型的段落重組對齊方法在理論上和實踐中均可行。

3.2 二分圖最大權(quán)重匹配模型下的句子對齊

陳相、林鴻飛[18]提出以二分圖最大權(quán)重匹配為模型進(jìn)行句子對齊。其解決方法是： (1)以雙語句子之間的相關(guān)性分值為二分圖頂點之間的邊加權(quán)；

(2)在基于長度的句子對齊方法基礎(chǔ)上，利用雙語中共現(xiàn)英語詞匯、數(shù)學(xué)符號、數(shù)字及格式化表達(dá)等作為錨點，同時考慮句子在對齊文本中的位置信息，計算相關(guān)性分值； (3)根據(jù)二分圖最大權(quán)重匹配獲得最終對齊結(jié)果。

句子對齊與段落重組對齊不一樣。句子對齊結(jié)果并非都是1∶1型的句對，對齊結(jié)果經(jīng)常類似圖1，有各種句對類型。陳相等考慮的句對類型僅包括傳統(tǒng)的1∶0，0∶1，1∶1，1∶2，2∶1，2∶2六種類型。實驗總體正確率92.4%, 69.8%的錯誤發(fā)生在非1∶1型的句對及其附近。這個統(tǒng)計結(jié)果在一定程度上證明，二分圖最大權(quán)重匹配結(jié)果不能直接作為最終句子對齊結(jié)果，需進(jìn)一步對非1∶1型句對進(jìn)行甄別。

4 二分圖頂點配對句子對齊方法

4.1 二分圖頂點配對句子對齊方法流程

二分圖頂點配對句子對齊方法整體流程如圖2所示。

圖2 二分圖頂點配對句子對齊方法流程

頂點配對句子對齊方法流程中的主要步驟依次是： (1)英漢文本拆分和段落對齊； (2)英、漢句子切分； (3)英語單詞形態(tài)還原； (4)根據(jù)雙語詞典和候選英語句子的盲譯譯文完成對候選漢語句子的分詞； (5)利用英漢句子相關(guān)性評價函數(shù)，根據(jù)(4)的結(jié)果計算候選句對的相關(guān)性分值，為對應(yīng)的二分圖頂點對加權(quán)； (6)根據(jù)二分圖全局范圍的最大權(quán)重頂點配對結(jié)果預(yù)估臨時錨點，在此基礎(chǔ)上從系統(tǒng)默認(rèn)的段首句對開始，結(jié)合句子順序、英漢句長比范圍和當(dāng)前處理句對，重新從前向后依次評估修正每一個臨時錨點，劃分句對，得到最終句子對齊結(jié)果。

4.2 英漢句子相關(guān)性評價函數(shù)

本研究中英漢句子相關(guān)性評價函數(shù)僅考慮詞匯互譯信息。方法步驟如下： (1)將英語句子形態(tài)還原，根據(jù)詞典，羅列該句每個英語單詞及其原形的全部漢語詞義，構(gòu)成該句的盲譯譯文； (2)利用盲譯譯文中的兩字和多字詞語構(gòu)建臨時漢語分詞詞典，同時將盲譯譯文中的單個字符存入一個哈希表，再利用該漢語分詞詞典對候選漢語句子進(jìn)行分詞； (3)根據(jù)該漢語句子分詞結(jié)果，結(jié)合盲譯譯文的單個字符哈希表，根據(jù)評價函數(shù)，計算相關(guān)性分值。

評價函數(shù)如式(1)所示。

說明：

(1) S代表候選英語句子，實際計算時先根據(jù)S得到英語句子盲譯譯文S′，再將S與S′合起來構(gòu)成S″。T表示候選漢語句子，實際計算時T先被從S′創(chuàng)建的臨時分詞詞典切分，得到T′，再參加計算，Value(S,T)是指T轉(zhuǎn)換成T′后，T′中的三種類型的子字符串按一定規(guī)則與從S轉(zhuǎn)換成的S″相比較所得到的相關(guān)性分值。

(2) Len(X)表示字符串X的長度。

(3) MMCh表示T′在S″中所匹配的多字漢語詞語。由于T′由S″中盲譯譯文生成的臨時分詞詞典進(jìn)行詞語切分，因此，T′中含有漢字的無空格多字符字符串(例如，“1月”)都屬于MMCh多字漢語詞語，分值是該字符串的長度。

(4) MSCh表示T′在S″中所匹配的單字漢語詞語。單字漢語詞語的識別: 先將S″的盲譯譯文中的單字漢語詞義放到哈希表HashTemp中。比較T′與S″時，設(shè)T′中的單字漢語字符串為strTemp，如果strTemp在哈希表HashTemp中，則將其視為一個MSCh字符串，計1分，否則不計分。

(5) MCha表示T′在S″中所匹配的非漢字字符。非漢字字符對尋找正確配對貢獻(xiàn)更大，加倍計算分值。非漢字字符通常在英語和漢語中以同一形式出現(xiàn)，例如，數(shù)字。正因為這個原因， S″中既有英語句子，又有其盲譯譯文。非漢字字符的分值計算優(yōu)先。例如，對任何一個已經(jīng)在S″中找到匹配的單字字符，程序先判斷其是否是漢字，如果不是漢字，則計2分，如果是漢字，繼續(xù)(4)中的比較。

4.3 根據(jù)頂點配對獲取句子對齊結(jié)果

句子對齊結(jié)果的獲取先要根據(jù)二分圖全局范圍內(nèi)的最大權(quán)重頂點配對結(jié)果預(yù)估臨時錨點，在此基礎(chǔ)上根據(jù)多方面信息修正每一個臨時錨點，劃分句對，得到最終的句子對齊結(jié)果。

(1) 預(yù)估臨時錨點

臨時錨點的作用是通過詞匯互譯信息預(yù)估句子對齊二分圖模型中最可能出現(xiàn)在句對中的邊。平行文本中每對平行段落都是一個以該段落對中英語句子集和漢語句子集為頂點集的二分圖，它的頂點對的權(quán)重值等于根據(jù)英漢詞典計算出來的英、漢語句子之間的詞匯互譯信息值，即上述英漢句子相關(guān)性評價函數(shù)值。預(yù)估錨點時可以按漢語句子順序，也可以按英語句子順序，通過貪心算法，從第一個漢語句子或者第一個英語句子開始，依次求得頂點集的一個子集中的每個頂點與另一個子集中全部頂點之間的最大權(quán)重頂點對，作為臨時錨點。實際操作中，本研究先將每副頂點對的權(quán)重值保存到一個二維數(shù)組中，然后再調(diào)用，避免后面再次計算。

本研究按漢語句子順序預(yù)估臨時錨點。方法如下： 假設(shè)頂點對(Eni,Chj)權(quán)重為Value(Eni,Chj)，針對頂點子集中一個漢語句子Chj，有頂點子集中的英語句子En0，En1，……，Enm與之配對，尋找出英語句子中與Chj的最大權(quán)重配對Maximum(Value(En0, Chj), Value(En1, Chj), …, Value(Enm, Chj))，這樣得到的頂點對就是漢語句子Chj在頂點子集中的最大權(quán)重配對。又因為這是Chj從整個頂點子集中得到的最大權(quán)重配對，所以也稱為全局最大權(quán)重頂點配對。如果用“En?Ch?”代表一個錨點，其中En代表英語句子，后跟索引號，Ch代表漢語句子，后跟索引號，則根據(jù)圖1中的句對，圖1中二分圖的最佳臨時錨點序列如下：

En1Ch1 En2Ch2 En2Ch3 En(3|4)Ch4
En5Ch5 En6Ch6 En7Ch7 En7Ch8 En7Ch9 En8Ch10

其中En(3|4)Ch4表示En3或者En4都可能與Ch4配對，原因是圖1中與其對應(yīng)的原始句對是(En3,En4):Ch4。實際預(yù)估臨時錨點時，哪一個頂點與Ch4配對，要視Ch4在頂點子集中的最大權(quán)重結(jié)果而定。圖1的句子對齊二分圖頂點配對模型中全部句對的總邊數(shù)Sume是12；最佳臨時錨點序列中的錨點數(shù)Suma是10，與每組對齊段落中的漢語句子數(shù)目一致；總句對數(shù)Sumb是6。Sume≥Suma≥Sumb。這個關(guān)系告訴我們，錨點序列不一定能夠覆蓋所有邊，經(jīng)常需要在已知錨點基礎(chǔ)上確定遺漏的邊，即為不在錨點序列的英語句子找到配對的漢語句子；另外，通常會有多條邊合在一起組成一個句對。由于語言的復(fù)雜性，臨時錨點序列中可能有小部分的頂點配對結(jié)果與正確結(jié)果不吻合，需要根據(jù)句子順序和其他條件校正。因此，全局最大權(quán)重頂點配對只是臨時錨點。

(2) 修正臨時錨點和劃分句對

得到臨時錨點序列后，接著完成下列操作： 修正臨時錨點，找回未覆蓋到的頂點對，劃分句對。這項工作依據(jù)三條要求完成： ①句子先后順序不能顛倒； ②預(yù)設(shè)的英漢句長比值域一般不允許逾越； ③局部最大權(quán)重頂點配對優(yōu)于全局最大權(quán)重頂點配對。所謂局部最大權(quán)重頂點配對，是指為修正臨時錨點或為找回未覆蓋到的頂點對而在幾個受限的相鄰句子中獲取的最大權(quán)重頂點配對。前后錨點句子順序不對則一定有錨點錯誤，這時需要通過局部最大權(quán)重頂點配對重新選擇最佳配對。找回未覆蓋到的頂點對時，先根據(jù)句子順序判斷錨點之間是否有漏句，再根據(jù)局部最大權(quán)重頂點配對為漏句選擇當(dāng)前最佳配對。

英漢句長比值域用于輔助劃分句對。句對劃分方法： 默認(rèn)每個對齊段落段首和段末的英、漢語句子分別屬于該對齊段落中的第一句對和最后一個句對；句對劃分從段首英、漢句子開始，一句一句依次向后，通過動態(tài)規(guī)劃算法，一個句對一個句對向后劃分，直到段末。根據(jù)相關(guān)統(tǒng)計數(shù)據(jù)，設(shè)英漢句長比的最大值是7.5，最小值是0.83。句長比值域在劃分句對中的作用是： 待確定句對的句長比大于7.5則增加下一句漢語繼續(xù)分析；小于0.83則增加下一句英語繼續(xù)分析。

具體的句對劃分主要有三種情況： ①根據(jù)對超過5 000句對的多領(lǐng)域英漢平行語料句子對齊結(jié)果的統(tǒng)計，在當(dāng)前待確定句對的句長比合適，下一錨點正好是當(dāng)前最大英、漢語句子序號各加1時，待確定句對是正確句對的正確率達(dá)99.853%。這個現(xiàn)象被作為劃分句對的一條重要依據(jù)，待確定句對符合這個條件即被承認(rèn)為合法句對；②在當(dāng)前句對句長比合適，該句對與下一錨點間未覆蓋的英語句子根據(jù)局部最大權(quán)重頂點配對應(yīng)該與下一錨點的漢語句子配對時，則承認(rèn)當(dāng)前句對合法；③個別情況允許打破句長比值域范圍： 當(dāng)前待確定句對后面接連出現(xiàn)兩個序號緊密相連的作為錨點的頂點對時，值域不再起約束作用。例如，在錨點序列片斷En3Ch2 En4Ch3 En5Ch4中，如果待確定句對是En3Ch2，即使En3與Ch2的句長比超出值域，也認(rèn)可En3Ch2是合法句對。這種情況在古詩英譯時可能出現(xiàn)。

4.4 頂點配對句子對齊方法特點

頂點配對句子對齊方法有如下特點： (1)充分利用基于詞匯互譯信息的最大權(quán)重頂點配對結(jié)果，分兩步走，實現(xiàn)句子對齊； (2)不限制句對類型，實踐中曾以很高的正確率召回1∶5，1∶6，1∶7，1∶8，2∶2，……，2∶6，5∶2等類型的句對； (3)段落是重要的語言單位[21]，該方法保留了段落標(biāo)記； (4)利用英漢雙語詞典對漢語句子進(jìn)行分詞。

5 實驗及結(jié)果

本實驗利用公開語料對比頂點配對句子對齊方法與Champollion-1.2句子對齊系統(tǒng)。選擇Champollion進(jìn)行對比的原因是： (1)Champollion也是基于英漢詞典的句子對齊方法； (2)Champollion 是當(dāng)前基于英漢詞典的開源句子對齊工具中較好的系統(tǒng)[19-20]，得到了廣泛認(rèn)可。

5.1 語料選取

選取的語料是2009年奧巴馬就職演說的全文及翻譯，以及從百度文庫下載的“全新版大學(xué)英語綜合教程3課文原文及翻譯.doc”中選取的三篇完整的課文及翻譯，它們分別是第一單元的A篇、第三單元的B篇和第六單元的B篇。根據(jù)統(tǒng)計，后兩篇是上述教材在基于大詞典的頂點配對方法下出現(xiàn)句子對齊錯誤最多的課文。

5.2 語料預(yù)處理

頂點配對句子對齊方法中，英語句子以英語的句號、問號、感嘆號和冒號為界，漢語句子以漢語的句號、問號、感嘆號、冒號和分號為界。句子切分在段落對齊后、在預(yù)估臨時錨點前自動實現(xiàn)。英語形態(tài)還原、漢語分詞均在預(yù)估臨時錨點過程中自動處理。

Champollion對語料預(yù)處理有不同的要求。Champollion中語料需要事先處理成一句占一行的格式，中間不能有空行。本實驗中，Champollion的語料完全按頂點配對句子對齊方法的句子邊界識別方法對英、漢文本進(jìn)行句子邊界識別，這樣保證了本實驗兩種句子對齊方法中的平行語料的句子切分結(jié)果完全一致，最后的對齊結(jié)果不受句子切分結(jié)果影響。其他方面，Champollion內(nèi)嵌有自己的形態(tài)還原方法，自帶了第三方的漢語分詞插件，在對齊過程中自動實現(xiàn)形態(tài)還原和漢語分詞。

5.3 英漢詞典的準(zhǔn)備

(1) 大詞典： 由多部電子詞典合成，英語單詞236 374個，漢語詞義678 167個。含大量專業(yè)術(shù)語。

(2) 小詞典： Champollion原型系統(tǒng)的詞典，同時轉(zhuǎn)換成頂點配對句子對齊方法所要求的雙語詞典格式。詞典中英語單詞4 885個，漢語詞義41 814個。含大量常用單詞及詞義。

5.4 句子對齊結(jié)果

表1是本實驗中的語料分別以Champollion系統(tǒng)和基于大詞典、基于小詞典的頂點配對方法實現(xiàn)句子對齊后的正確率、召回率和F值。相關(guān)公式如式(2)～式(4)所示。

從表1數(shù)據(jù)來看Champollion和頂點配對句子對齊方法的對齊結(jié)果： 基于大詞典的頂點配對句子對齊方法的正確率、召回率和F值最高，后期需要的人工校對工作量最少；基于小詞典時，頂點配對句子對齊方法比Champollion句子對齊方法略好，不過沒有顯著差異。但是，頂點配對句子對齊方法保留了原來的段落結(jié)構(gòu)，對齊后的語料適用范圍更廣。

表1 Champollion和頂點配對句子對齊方法對齊結(jié)果比較

注： 語料1是2009年01月21日奧巴馬就職演說全文；語料2、3和4分別是全新版大學(xué)英語綜合教程3第一單元A篇、第三單元B篇和第六單元B篇的課文原文及翻譯。

我們還在實踐中利用基于大詞典的頂點配對句子對齊方法處理了大量非公開語料。對其中一份長語料的統(tǒng)計是： 英語單詞115 497個，句子5 257句；漢字200 108個，句子5 069句；句對4 696對；句子對齊結(jié)果中1: 1類型句對的正確率99.8%，總體正確率99.2%。

6 結(jié)論

基于雙語詞典的句子對齊算法有很多種。本研究以二分圖頂點配對為模型，首先基于英漢詞典，利用完全基于詞匯互譯信息的英漢句子相關(guān)性評價函數(shù)為頂點對加權(quán)，獲得全局最大權(quán)重頂點配對信息，然后根據(jù)句子順序、局部最大權(quán)重頂點配對信息和英漢句長比值域，獲得英漢平行語料的句子對齊處理。從實驗對比結(jié)果來看，該句子對齊方法在大容量英漢詞典支持下明顯優(yōu)于Champollion原型系統(tǒng)；在詞典規(guī)模與Champollion原型系統(tǒng)完全一致時，該句子對齊方法略優(yōu)，無顯著差異。該句子對齊方法是可行的。本研究在利用詞匯互譯信息時，僅考慮了單個英語單詞對應(yīng)的漢語譯文信息，下一步可以針對英語詞組和短語，建設(shè)英漢短語詞典，研究如何在句子對齊處理中利用短語互譯信息，進(jìn)一步改進(jìn)句子對齊算法。

[1] 孫樂, 金友兵, 杜林, 等. 平行語料庫中雙語術(shù)語詞典的自動抽取[J], 中文信息學(xué)報, 2000, 14(6): 33-39.

[2] 李莉, 劉知遠(yuǎn), 孫茂松. 基于中英平行專利語料的短語復(fù)述自動抽取研究[J], 中文信息學(xué)報, 2013, 27(6): 151-157.

[3] Ma, Xiaoyi. Champollion: A robust parallel text sentence aligner[C]//Proceedings of the LREC 2006: Fifth International Conference on Language Resources and Evaluation.2006: 489-492.

[4] Brown P F, Jennifer C Lai, Robert L. Mercer. Aligning Sentences in Parallel Corpora[C]//Proceedings of the 29th Annual Meeting of the Association for Computational Linguistics， Berkeley, California, 1991: 169-176.

[5] Gale W A, Church K W. A program for Aligning Sentences in Bilingual Corpora[C]//Proceedings of the 29th Annual Meeting of the Association for Computational Linguistics, Berkeley, California, 1991: 177-184.

[6] Kay M, M Roscheisen. Text-Translation Alignment[J].Computational Linguistics, 1993, 19(1): 121-142.

[7] Chen S F Aligning Sentence in Bilingual Corpora Using Lexical Information[C]//Proceedings of the 31st Annual Meeting of the Association for computational Linguistics (ACL '93)，Columbus, Ohio, USA, 1993: 9-16.

[8] Moore R C. Fast and Accurate Sentence Alignment of Bilingual Corpora[C]//Proceedings of Machine Translation: From Research to Real Users， Springer, 2002: 135-144.

[9] Wu, Dekai. Aligning a Parallel English-Chinese Corpus Statistically with Lexical Criteria[C]//Proceedings of ACL 31.1994: 80-87.

[10] Tan, Chew Lim and Makoto Nagao. Automatic alignment of Japanese-Chinese bilingual texts[J].IEICE Transactions on Information and Systems, 1995, E78-D(1): 68-76.

[11] 張艷, 柏岡秀紀(jì). 基于長度的擴(kuò)展方法的漢英句子對齊[J]. 中文信息學(xué)報, 2005, 19(5): 31-36.

[12] 張亞軍, 賀琛琛, 香麗蕓. 限定領(lǐng)域的漢語-維吾爾語句子級對齊研究[J]. 軟件, 2014, 35(3): 62-64.

[13] 邵健, 章成志. 從互聯(lián)網(wǎng)上自動獲取領(lǐng)域平行語料[J]. 現(xiàn)代圖書情報技術(shù), 2014, 253(12): 36-42.

[14] 劉穎, 王楠. 古漢語與現(xiàn)代漢語句子對齊研究[J]. 計算機(jī)應(yīng)用與軟件, 2013, 30(11): 127-130.

[15] Braune F， Alexander Fraser. Improved unsupervised sentence alignment for symmetrical and asymmetrical parallel corpora[C]//Proceedings of the COLING 2010: Poster Volume, Beijing, 2010: 81-89.

[16] 魏雪麗. 離散數(shù)學(xué)及其應(yīng)用[M]. 北京: 機(jī)械工業(yè)出版社, 2008，4.

[17] 李維剛, 劉挺, 王震, 李生. 雙語語料庫段落重組對齊方法研究[C], 哈爾濱工業(yè)大學(xué)信息檢索研究室論文集, 2003: 67-73.

[18] 陳相, 林鴻飛. 基于錨信息的生物醫(yī)學(xué)文獻(xiàn)雙語摘要句子對齊[J]. 中文信息學(xué)報, 2009, 23(1): 58-62.

[19] Li Peng, Sun Maosong, Xue Ping. Fast-Champollion: A Fast and Robust Sentence Alignment Algorithm[C]//Proceedings of the 23rd International Conference on Computational Linguistics， Beijing, China, 2010: 710-718.

[20] 熊文新. 英漢環(huán)保領(lǐng)域平行語料的句對齊與再對齊[J]. 現(xiàn)代圖書情報技術(shù), 2013(6): 36-41.

[21] 梁茂成, 許家金. 雙語語料庫建設(shè)中元信息的添加和段落與句子的兩級對齊[J]. 中國外語, 2012, 9(6): 37-42.

Sentence Alignment Under A Bipartite Graph Vertex Pairing Model

YAN Canxun

(Language Engineering Department, PLA Foreign Languages Institute, Luoyang, Henan 471003, China)

Pairing vertices properly in a bipartite graph can be taken as a model for the bilingual sentence alignment. The vertex pairs in the bipartite graph can be weighted with a totally bilingual-dictionary-based evaluation function which evaluates the word correspondences between an English sentence and a Chinese sentence. In our appoach, the globally-maximum-weighted vertex pairs are first chosen as temporary anchors. Then, based on the temporary anchors, the results of the locally-maximum-weighted vertex pairs and the range of the ratio of English and Chinese sentence lengths, the mistakes in the original anchor vertex pairs are corrected and the missing vertex pairs are supplemented. Meanwhile, the sentences in the bipartite graph are simultaneously grouped into minimal groups of corresponding sentences. The comparison experiments show that the vertex-pairing sentence alignment approach works better than the Champollion sentence alignment system.

sentence alignment; bilingual dictionary; parallel text; bipartite graph; vertex pairing; vertex pair

嚴(yán)燦勛(1971—)，博士，副教授，主要研究領(lǐng)域為語言信息處理研究。E?mail：yancanxun@126．com

1003-0077(2016)05-0153-07

2015-02-13 定稿日期： 2015-04-14

中央文獻(xiàn)對外翻譯與傳播協(xié)同創(chuàng)新中心科學(xué)研究項目(2013XT08)

TP391

A