倪耀群，許洪波，程學(xué)旗

(1. 中國科學(xué)院 計算技術(shù)研究所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實驗室，北京 100190；2. 中國科學(xué)院大學(xué)，北京 100049；3. 洛陽外國語學(xué)院 語言工程系，河南 洛陽 471003)

基于多特征融合和圖匹配的維漢句子對齊

倪耀群1,2,3，許洪波1，程學(xué)旗1

(1. 中國科學(xué)院 計算技術(shù)研究所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實驗室，北京 100190；2. 中國科學(xué)院大學(xué)，北京 100049；3. 洛陽外國語學(xué)院 語言工程系，河南 洛陽 471003)

維吾爾語新聞網(wǎng)頁與對應(yīng)的中文翻譯網(wǎng)頁在內(nèi)容上往往并非完全可比，主要表現(xiàn)為雙語句子序列的錯位甚至部分句子缺失，這給維漢句子對齊造成了困難。此外，作為新聞要素的人名地名很多是未登錄詞，這進(jìn)一步增加了維漢句子對齊的難度。為了提高維漢詞匯的匹配概率，作者自動提取中文人名、地名并翻譯為維吾爾譯名，構(gòu)造雙語名稱映射表并加入維漢雙語詞典。然后用維文句中詞典詞對應(yīng)的中文譯詞在中文句中進(jìn)行串匹配，以避免中文分詞錯誤，累計所有匹配詞對得到雙語句對的詞匯互譯率。最后融合數(shù)字、標(biāo)點(diǎn)、長度特征計算雙語句對的相似度。在所有雙語句子相似度構(gòu)成的矩陣上，使用圖匹配算法尋找維漢平行句對，在900個句對上最高達(dá)到95.67%的維漢對齊準(zhǔn)確率。

句子對齊；人名、地名翻譯；多特征融合；二部圖最佳匹配

1 引言

隨著互聯(lián)網(wǎng)的發(fā)展，多民族網(wǎng)絡(luò)交流日益頻繁和深入，迫切需要機(jī)器翻譯和跨語言檢索等工具的支持。雙語語料是統(tǒng)計機(jī)器翻譯、跨語言檢索、雙語詞典構(gòu)建等研究領(lǐng)域的重要基礎(chǔ)資源。而平行句對挖掘則是構(gòu)建雙語語料的關(guān)鍵技術(shù)，因而具有重要的研究價值。

互聯(lián)網(wǎng)維漢雙語新聞的出現(xiàn)為平行語料庫的構(gòu)建提供了穩(wěn)定的來源。目前天山網(wǎng)、人民網(wǎng)(維文版)和新疆自治區(qū)政府網(wǎng)站會登載、轉(zhuǎn)發(fā)維漢雙語新聞，但是從中挖掘平行句對存在一些困難，主要表現(xiàn)在：

(1) 維文與中文的差異大

中國維吾爾族使用的維吾爾文是一種拼音文字，有老維文和拉丁維文兩種等價的書寫體系(本文以拉丁維文為標(biāo)準(zhǔn)進(jìn)行敘述，后同)，在詞匯形態(tài)構(gòu)成上屬于黏著語，變化復(fù)雜，在語法上常常動詞后置(SOV結(jié)構(gòu))。而中文是一種象形文字，在詞匯構(gòu)成上屬于分析語，詞匯之間沒有自然邊界，在語法上一般使用主謂賓(SVO)結(jié)構(gòu)。

(2) 網(wǎng)頁雙語文本存在較大噪音

維漢雙語網(wǎng)頁新聞的特點(diǎn)是更新快，用語準(zhǔn)確度低和摘要式翻譯，從中提取的篇章對齊文本稱為準(zhǔn)可比語料(quasi-comparable corpus)[1]。摘要翻譯往往會省略中文(或者維文)的若干段落，或段落中的某些句子，導(dǎo)致雙語句子不能一一對應(yīng)，雙語句子標(biāo)號不一定呈現(xiàn)線性關(guān)系。因此，雙語新聞中在內(nèi)容上只是部分對應(yīng)，這是一類噪音。此外，網(wǎng)頁轉(zhuǎn)載時，新聞網(wǎng)頁的元信息(如記者、新聞機(jī)構(gòu)名、發(fā)布時間等)一般會發(fā)生變化，新聞中常常出現(xiàn)一些新的名稱(人名、地名、新詞等)，這些不斷變化的非詞典詞是另一類噪音。

(3) 句子對齊模式復(fù)雜

雙語句子對齊的基本單位稱為句珠(sentence bead)，一個句珠含有若干原文句子和對應(yīng)的若干譯文句子。具體到維漢雙語，假設(shè)維文句子數(shù)目和中文句子數(shù)目分別m個和n個，稱該句珠為m： n的句子對齊模式。據(jù)文獻(xiàn)[2]統(tǒng)計，維漢篇章語料庫中有93.2%是雙語句子1∶1對齊模式，還有5.3%是1∶2或者2∶1的對齊模式。句珠的對齊模式還存有1∶0模式、0∶1模式、2∶2模式、1∶3模式等多種可能，這些復(fù)雜多樣的對齊模式增大了句子對齊的難度。

針對以上問題，作者提取了雙語句子的多種特征計算雙語句對的互譯程度(相似度)。先使用規(guī)則構(gòu)造了中文人名地名與維文譯名的映射，解決了大部分未登錄詞的互譯匹配問題；同時為避免中文分詞錯誤，在計算詞匯互譯率時，用詞典中文詞直接在中文句子中進(jìn)行串匹配。同時融合了句子中的數(shù)字、標(biāo)點(diǎn)等特征，使得雙語句子的相似度計算具有較高的可靠性。在此基礎(chǔ)上，將雙語句子作為二部圖的頂點(diǎn)，句子相似度作為連邊的權(quán)值，使用圖匹配的方法求得最佳匹配。圖匹配方法避免了動態(tài)規(guī)劃算法中最優(yōu)子結(jié)構(gòu)和重疊子結(jié)構(gòu)的限制(原語句子無法與譯文中位置相差較大的句子對齊)，使句子匹配的范圍更大，甚至在顛倒句子順序時也可以正常匹配。需要說明的是，本文主要針對占比最大的1∶1模式的句珠(即平行句對)的自動生成展開研究。

本文的組織結(jié)構(gòu)如下： 第二部分介紹了句子對齊的相關(guān)工作，總結(jié)了存在的問題；第三部分介紹了維漢句子特征選取和雙語特征的匹配，分為人地名轉(zhuǎn)寫、數(shù)字特征、詞典詞匯匹配與句子長度因素特征；第四部分基于融合的特征計算雙語句子相似度，在900對雙語句子生成的相似度矩陣上，使用貪婪匹配和二部圖最大權(quán)匹配(KM算法)進(jìn)行句子對齊，比較了各種算法的準(zhǔn)確率；分析實際數(shù)據(jù)后得出三種算法的適用范圍；第五部分是總結(jié)和未來工作方向。

2 句子對齊的相關(guān)工作

句子對齊主要有基于長度的方法和基于詞匯的方法，以及目前研究較多的兩者融合的方法。

基于長度的方法有兩個前提條件，第一個條件是表達(dá)同一語義的雙語文本，在長度上是正相關(guān)的；另一個條件是原文句子的序號(句子位置)與譯文句子序號差值不大。文獻(xiàn)[3]在英德法語料庫中，按照字符長度構(gòu)造了一個表征譯文長度對應(yīng)原文長度的標(biāo)準(zhǔn)化變量δ，該隨機(jī)變量服從標(biāo)準(zhǔn)正態(tài)分布，使用δ估計句子的相似度,如式(1)所示。

(1)

其中，l2為譯文句長，l1為原文句長。在Gale的方法中計算原文句子和譯文句子的六種對齊模式(1∶1)，(1∶0)，(1∶2)，(0∶1)，(2∶1)，(2∶2)。盡管1∶0的對齊關(guān)系的句子完全判斷錯誤，但由于該類問題所占比例非常小，總體句子對齊達(dá)到96%的準(zhǔn)確率。

文獻(xiàn)[4]首次將該方法引入英漢句子對齊。在得到的438個1∶1句珠中，有377個(86.1%)是正確的。另外結(jié)合詞匯信息后，準(zhǔn)確率提升到92.1%。Wu[4]分析純粹基于長度的方法易受長度伸縮性大的文本影響，尤其在中文這種高度精煉的非拼音文字中，句子長度沒有印歐語系拼音文字那么強(qiáng)的相關(guān)性。結(jié)合詞匯信息能獲得更高的句子對齊準(zhǔn)確率。

基于詞匯的方法根據(jù)雙語句子互譯詞的個數(shù)來計算互譯率，互譯詞要么來源于雙語詞典，要么根據(jù)事先統(tǒng)計的雙語詞匯共現(xiàn)概率。語言專家編輯的雙語詞典包含了雙語最基本的詞匯映射關(guān)系，是單詞匹配的基礎(chǔ)。但是未登錄詞問題和譯文的靈活翻譯問題限制了雙語詞典的匹配效果[5]。

香港學(xué)者[1]在英漢準(zhǔn)可比語料上利用詞典和詞匯互信息，在篇章集合、句子和詞匯三個級別反復(fù)迭代，用多級自舉(multi-level bootstrapping)和閾值篩選的方法生成平行句對。英漢雙語文本的普遍性使得在雙語文檔集合內(nèi)，詞匯共現(xiàn)的次數(shù)足夠豐富，不需要進(jìn)行稀疏詞匯共現(xiàn)的T檢驗。

文獻(xiàn)[6]在維漢語料庫中先確定錨點(diǎn)，即可信度較高的1： 1對齊的句對；在錨點(diǎn)之間根據(jù)句子長度使用動態(tài)規(guī)劃方法對齊句子。錨點(diǎn)句的評價使用三個指標(biāo)： ①句長對應(yīng)關(guān)系②關(guān)鍵詞詞典及標(biāo)點(diǎn)匹配程度③位圖斜率(Bitext map slope)和最小二乘斜率(least squares line)夾角。其中關(guān)鍵詞由2 000個雙語常見詞和高頻技術(shù)術(shù)語構(gòu)成；錨點(diǎn)的中維句子標(biāo)號形成了文本圖中的一個點(diǎn)的縱橫坐標(biāo)，若干錨點(diǎn)的擬合斜率與所有句子的位圖斜率夾角反映了錨點(diǎn)斜率與整體句子標(biāo)號斜率的偏離程度；Samat對維漢句子長度的衡量標(biāo)準(zhǔn)進(jìn)行了研究，表明維文以詞為單位，中文以字符為單位計算，得到的方差最小，而且相關(guān)系數(shù)最大(0.977)。在十篇文本中評價達(dá)到94.6%的準(zhǔn)確率和94.8%的召回率。

文獻(xiàn)[2]的方法與Samat的步驟基本類似，不同點(diǎn)有二： 一是用雙語詞匯共現(xiàn)概率(用五萬個平行句對統(tǒng)計)計算詞匯互譯率；二是用中文句相對編號和維文句相對編號的差代替Samat的斜率夾角，兩人的做法其實都反映了錨點(diǎn)句子在整個句子序列中的位置偏差。在四篇人工對齊的語料中，平均達(dá)到97.6%的準(zhǔn)確率和98.2%的召回率。

雙語新聞中人名地名是重要的新聞要素，但是人名和地名一般屬未登錄詞，無法直接匹配。

詞匯共現(xiàn)概率需要在大規(guī)模雙語句對中統(tǒng)計，在新的規(guī)模較小的可比語料庫中，用語變化及數(shù)據(jù)稀疏問題導(dǎo)致詞匯共現(xiàn)信息很難得到。

3 句子對齊的特征選擇

句子特征可以分為外部特征和內(nèi)部特征。外部特征在本文中指句子的整體特征(包含句子長度、句子編號)；句子的內(nèi)部特征指該句子內(nèi)部的局部特征(如詞匯、數(shù)字、標(biāo)點(diǎn)等)。在打亂句子編號的情況下，維文句子u和中文句子c的對齊主要依賴句子內(nèi)容的互譯程度和句子長度的匹配程度。本文使用的句子內(nèi)部特征有人名地名、數(shù)字、詞典詞和標(biāo)點(diǎn)。

3.1 雙語人名地名特征

人名地名構(gòu)成了新聞的主要因素，是雙語句子對齊的重要特征。但是人名地名多為未登錄詞，無法用雙語詞典互譯匹配。經(jīng)分析，維漢雙語新聞中出現(xiàn)的人名地名大多為漢族維族人名和中國地名，小部分為外國人名地名。作者借助ICTCLAS抽取中文專名(“/nr”為人名，“/ns”為地名)，使用改進(jìn)的轉(zhuǎn)寫翻譯方法獲得維文譯名，建立人名地名的映射關(guān)系并合并到雙語詞典，間接實現(xiàn)了人名和地名的互譯匹配。

3.1.1 漢字到維文的直譯方法

文獻(xiàn)[6]提出了一種將中文專名自動翻譯為維文的方法。主要基于漢語拼音聲母韻母與維文音節(jié)的映射規(guī)則。文獻(xiàn)[7]翻譯維文中的漢族人名也是基于這樣的映射規(guī)則。經(jīng)過對比實驗，發(fā)現(xiàn)李佳正使用的聲母韻母與維文音節(jié)映射表中，存在非法分解(如chuang被錯誤分解為ch uan g)和多樣轉(zhuǎn)寫(如漢語的u對應(yīng)維文u或者ü等)問題，對現(xiàn)有數(shù)據(jù)的統(tǒng)計結(jié)果表明，僅僅u字母的1對2映射就造成了51個拼音的混亂。

為此，作者將全部27 803個漢字歸結(jié)為402個普通話標(biāo)準(zhǔn)音(姓氏漢字中的多音字不計聲調(diào)變化共有39個，按姓氏規(guī)范確定其正確讀音)，將漢字標(biāo)準(zhǔn)音映射為維文，避免非法分解轉(zhuǎn)寫造成的錯誤，提高維文人名地名識別的準(zhǔn)確率。

對于音節(jié)的多個合法轉(zhuǎn)寫造成的多樣性，在402個標(biāo)準(zhǔn)音的基礎(chǔ)上請維語專家人工審定，剔除那些音節(jié)合法但是整字組合后非法的轉(zhuǎn)寫，在后續(xù)處理的時候枚舉所有合法多樣拼寫，提高召回率(查全率)。

最終構(gòu)建的漢字整字標(biāo)準(zhǔn)音與拉丁維文映射表去除了很多非標(biāo)準(zhǔn)音biang，chua，并增補(bǔ)一些漢字的兼容拼音如nve(虐nue)等，共402行，表1給出了表格的一部分。

表1 漢字拼音轉(zhuǎn)寫拉丁維文的映射表

3.1.2 漢族人名的直譯轉(zhuǎn)寫

文獻(xiàn)[7]從維文到漢族人名的翻譯方法存在不確定性，一個人名拼音對應(yīng)的多個中文人名只能通過概率計算，得到最可能的中文名。作者基于中文人名的漢字拼音，按照確定的規(guī)則獲取維文人名，避免了概率計算可能帶來的錯誤。

例如，中文人名“俞正聲”轉(zhuǎn)換為唯一的漢語拼音形式“yu zheng sheng”，按規(guī)則翻譯為兩個合法維文譯名“yü j?ngshen”及“yü j?ngsheng”。人名字典添加及兩個條目。

中文人名要在篇章范圍構(gòu)建，這樣可以避免同一個人名在不同句子中ICTCLAS分詞結(jié)果不一致的情況。例如：

例句1 “上海市委/nt書記/n 俞/nr1 正/d 聲/ng接受/v 新華社/nt記者/n 的/ude1 專訪/vn。/wj”

例句2 “俞正聲/nr 表示/v …”

在例句1中的人名“俞正聲”被錯誤切分為“俞/nr1 正/d 聲/ng”，例句2切分正確“俞正聲/nr”。在篇章范圍內(nèi)可正確抽取“俞正聲”(根據(jù)“/nr”標(biāo)記)并獲得兩個合法維文譯名“yü j?ngshen”和“yü j?ngsheng”。

隨后的匹配過程(詳見3.3節(jié))維文切分采用正向最大匹配的方式，可以找到“yü j?ngshen”或者“yü j?ngsheng”，查找詞典后得到“俞正聲”。然后用“俞正聲”作為模式串在未分詞的中文原句中進(jìn)行串匹配，在中文句子1的原句中可匹配到正確結(jié)果“俞正聲”。

也就是說，中文名字只要有一次是正確標(biāo)注的，詞典中就加入了正確的條目，隨后進(jìn)行的中文串匹配對所有中文句進(jìn)行，從而可排除錯誤的切分。

3.1.3 中國內(nèi)地地名的轉(zhuǎn)寫

在地名轉(zhuǎn)寫時需要剝離地名單位(省市縣區(qū)路等)，再查看抽取的地名是否為新地名。具體可以分三種情形。

(1) 中文地名和維文譯名都是未登錄詞，添加詞典條目。如“蘇州路”抽出“蘇州”，維文譯名“suju”都是未登錄詞，直接將加入地名詞典。

(2) 中文地名和維文譯名都是已登錄詞，忽略該地名。如“山東省”抽出“山東”后發(fā)現(xiàn)中文詞“山東”已經(jīng)存在于雙語詞典，見“shendung山東”。

(3) 中文地名是未登錄詞，但維文譯名已登錄，將中文地名添加為詞典已登錄維文詞的中文義項。如中文地名“河北”是未登錄詞，但是轉(zhuǎn)寫的維文譯名"x?b?y"已經(jīng)在詞典里(中文義項為“北洋”)，現(xiàn)在，需在詞典中"x?b?y"條目的中文釋義中添加“河北”，變更為“x?b?y北洋；河北”。

獲得漢族人名和中國內(nèi)地地名的維文中映射關(guān)系后，加上雙語詞典本身就涵蓋的8 227個維吾爾人名和943個新疆地名，可以解決大部分未登錄詞的雙語匹配問題。外國人名和地名由于出現(xiàn)概率極小，并且構(gòu)造雙語譯名時錯誤率偏高，作者未做專門處理。

經(jīng)過對449個中文人名地名及其維文譯名的人工檢驗，正確翻譯為442個，錯誤的情形包括中文人名識別錯誤(如： 陳壯/nr 為/p 同志/n)及翻譯錯誤(如大西溝翻譯為da shigow，真實譯名為dashi gu)。正確率達(dá)到了98.4%。實際上不計重復(fù)出現(xiàn)的雙語人名地名數(shù)量為482，一些漢族人名被識別為外國人名(如馬伊磊/nrf 同志)而未納入詞典。因此，構(gòu)造的人名地名詞典的覆蓋度為93.1%。

3.2 數(shù)字特征的抽取與匹配

數(shù)字是一種明顯的特征，雙語句子出現(xiàn)的數(shù)字序列，相對順序基本上一致，可以認(rèn)為是兩個向量，在句子匹配中區(qū)分作用明顯。

維漢數(shù)字特征的抽取要注意如下問題。

(1) 復(fù)合數(shù)字，如維文數(shù)字“13milyon 600ming 800”對應(yīng)中文的一千三百六十萬零八百，分別轉(zhuǎn)寫為136000800。

(2) 非阿拉伯形式的數(shù)字存在歧義，如bir，在bir milyon 470ming(一百四十七萬)中是數(shù)字，在bir gewdileshtürüsh是一體化。作者簡單認(rèn)為四個數(shù)量詞tirliyon(萬億)、milyard(十億)、milyon(百萬)、ming(千)前出現(xiàn)的維文數(shù)字為真實數(shù)字。

(3) 時間寫法，19∶20與晚上7∶20統(tǒng)一成一種寫法。

計算數(shù)字特征的相似度時，為防止數(shù)字抽取錯誤引起的數(shù)字缺失和順序錯亂，沒有按照向量的余弦距離或者相關(guān)系數(shù)計算，而是采用式(1)。其中δ為克羅內(nèi)克符號，#cnNum表示中文句子的數(shù)字總個數(shù)，#uyNum為維文句子的數(shù)字總個數(shù)。

(1)

3.3 雙語詞匯特征及匹配方法

本文中詞匯泛指單詞和短語。作者使用的雙語詞典Anatilim Uyghur Chinese dictionary (Uyghur Latin Writing Edition)有385 486條目，其中兩萬個不連續(xù)短語直接丟棄，如“meyli … bolsun也好；也罷”。剩余363 037條目，其中57 274個是維文單詞，305 763個是短語(以空格隔開的兩個以上的單詞)。

為充分利用長詞的區(qū)分能力，作者將維文短語、單詞、標(biāo)點(diǎn)以及前面得到的維文譯名一起作為維文句子切分的“廣義詞表”，對維文句子進(jìn)行正向最大匹配切分。去除后綴得到維文詞匯特征，然后查詢雙語詞典后得到中文詞匯，用中文詞匯在中文句子中進(jìn)行串匹配。

3.3.1 維文短語切分和單詞形態(tài)還原

將維文句子切分后，如果切分單位內(nèi)含有空格，表明該單元是短語，可以直接作為維文短語特征，丟棄其后的詞綴。因為短語已經(jīng)含有空格，作者將所有切分單元用{}括起來。如 {xelq sariyi}{da}，其中的“xelq sariyi”意思為“人民大會堂”，“da”是表示時空的“位格”。反之，如果切分單位內(nèi)無空格，說明該切分單位是某個單詞的詞現(xiàn)(token)，需要進(jìn)行詞干還原。如維文原token“mesililer”被切成“{mes}{ili}{ler}”，就要將后綴＂ler＂去掉，處理變音后還原為“mesile”(“mesile”意思是“問題”，“mes”意為“商”)。

詞干還原涉及復(fù)雜的變音(增減變)，尤其是動詞的末尾可能有3～4個字母與詞干不同。詞的前綴共有六個，后綴532個[8]。

作者基于詞干表stemWordList(57 274項)和詞綴表suffixList(429項)，采用規(guī)則方法進(jìn)行名詞的詞干還原。

3.3.2 詞典詞匹配方法

維文雙語詞典中的中文詞，與中文句子分詞得到的中文詞差別很大。無論是機(jī)械分詞方法(詞表為雙語詞典中的所有中文詞)還是統(tǒng)計分詞方法都有問題，主要表現(xiàn)為：

(1) 詞表分詞的過切分問題

如中文“市政協(xié)副主席”切分為{市政}{協(xié)}{副主席}，不管文本分詞方向是正向還是逆向，匹配原則是最小匹配還是最大匹配還是全切分匹配，機(jī)械分詞方法都很難避免這樣的越界問題。

(2) ICTCLAS分詞與雙語詞典的中文詞不一致問題

中文機(jī)構(gòu)團(tuán)體被ICTCLAS標(biāo)記為(/nt)，從中文角度看比較合理，但是與詞典詞相比粒度有些過大。例如，“任命/v 趙宇澄/nr 同志/n 為/p 烏魯木齊市文化局/nt…”，其中“烏魯木齊市文化局”無法在詞典中進(jìn)行匹配。

為避免分詞方法造成的錯誤，提高互譯詞的匹配成功率，作者把中文句子作為模式匹配的主串，把維文詞的中文譯詞作為模式串，進(jìn)行串匹配操作。

維文詞uyTerm在雙語詞典中查詢的結(jié)果可能是一個中文詞(單義項，記作cnSense)，也可能是多個中文詞(多義項)。多個義項依次在中文句中掃描，一旦匹配，后面義項就忽略，認(rèn)為該義項與維文詞匯uyTerm配對。句子中所有的匹配詞匯按照公式(2)計算廣義詞義匹配度。其中l(wèi)en(uyTermi)與len(cnSensei)為互譯的維文詞長度和中文詞長度。

simT(Us,Cs)=

(2)

3.4 雙語句子長度特征

考慮到維文詞典中存在大量的短語，切分出的詞長懸殊較大，因而詞個數(shù)也不一致，作者統(tǒng)一采用unicode字符作為句子的長度單位。參考Gale[3]和文獻(xiàn)[2]中雙語句子長度關(guān)系的分析，作者定義δ如式(3)所示。其中l(wèi)en(Us)為維文句子長度，len(Cs)為中文句子長度。

(3)

δ為關(guān)于雙語句子長度的標(biāo)準(zhǔn)化變量，c是每個中文字對應(yīng)維文字符數(shù)的期望值，通過計算維中句子長度比值的平均值得到；之后根據(jù)c計算(len(Us)-c*len(Cs))2/len(Cs)的均值，得到統(tǒng)計方差σ2。本文取c=4.541 337 144 858 13，σ2=26.667 909 114 906 5。

正態(tài)分布是連續(xù)變量的理論分布，δ=δi的概率只能通過累積某一區(qū)間內(nèi)的概率密度得到。約定累積分布函數(shù)如式(4)所示。

(4)

對給定的維漢句子u和c，變量δ取定值δi，句子長度的匹配概率simL(u,c)有兩種計算方法。Gale在[-∞,-|δi|]和[|δi|，+∞]區(qū)間內(nèi)累積δ的概率，即

Pr(|δ|>δi)=2(1-F(|δi|))，王斌[10]在[δi-Δ, δi+Δ]區(qū)間內(nèi)累積概率，如式(5)所示。

(5)

作者通過實驗表明，王斌的方法比Gale的方法在匹配正確率稍高(約1.3%)，因此，采用了式(5)計算句子長度匹配度simL，即

(6)

4 基于二部圖匹配的維漢平行句對挖掘

提取了維文句子和中文句子的各種特征后，可以通過多特征融合的方式計算維漢句對的相似度。多個維文句子與多個中文句子兩兩之間的相似度構(gòu)成一個矩陣，基于相似度矩陣可以采用二部圖匹配的方法挖掘平行句對。

4.1 多特征融合的雙語句對相似度計算

維文句子U和中文句子C的內(nèi)容相似度sim0可以用式(7)計算，其中詞義匹配度simT(泛指人名地名、標(biāo)點(diǎn)和詞匯匹配度)與數(shù)字特征匹配度simD分別在式(1)、公式(2)中定義。作者在區(qū)間[0.05,0.95]內(nèi)以0.05的間隔試探λ，將其確定為0.85。

sim0(us,cs)=λ·simT(us,cs)+

(7)

很明顯，如果維文句子Us和中文句子Cs配對，那么len(Us)-c*len(Cs)≈0，δ≈0；從而simL(Us，Cs)也較大，以句子長度衡量匹配度較大。但是反過來，兩個句子的長度即使?jié)M足δ=0，也不能說兩個句子就是配對的(因為內(nèi)容可能完全不同)。可見句子長度匹配度simL只是一個必要非充分條件。這樣的條件一般用于懲罰原相似度sim0。為此作者修正句子相似度為式(8)。

(8)

式(8)中，sim0為浮點(diǎn)數(shù)，當(dāng)δ=0時，sim0不受懲罰；δ偏離0越遠(yuǎn)，sim0懲罰越大。α取經(jīng)驗值0.3，可以讓δ≠0的句對相似度的懲罰得到適當(dāng)松弛。

維文句子i和中文句子j的相似度計算過程如圖1所示。

m個維文句子和n個中文句子兩兩之間可計算m×n個相似度，每個相似度為[0,1]區(qū)間內(nèi)的浮點(diǎn)數(shù)，所有的相似度構(gòu)成一個m×n的權(quán)值矩陣。

4.2 二部圖構(gòu)建

如果將m個維文句子看作二部圖的一組頂點(diǎn)，將n個中文句子看作二部圖的另一組頂點(diǎn)，將相似度矩陣中不為零的元素看作二部圖的邊，邊的取值范圍是(0,1]。則本文關(guān)注的句子對齊問題(平行句對挖掘)就轉(zhuǎn)化為二部圖的最佳匹配問題，定義如下。

定義： 二部圖最佳匹配

帶權(quán)二部圖G=(V，W)的每條邊都有一個非負(fù)權(quán)值(以鄰接矩陣W表示)，頂點(diǎn)集合V=L∪R，約定|L|≤|R|，要求一種完備匹配方案，使得L中的頂點(diǎn)都被匹配而且匹配邊的權(quán)和最大，記做最大權(quán)匹配(maximum weight matching in bipartite graph)，也稱最優(yōu)完備匹配或者最佳匹配。R中沒有匹配的點(diǎn)，稱為未覆蓋點(diǎn)。

4.3 平行句對挖掘算法

為從雙語句子集合構(gòu)成的二部圖中挖掘平行句對，作者采用了三種圖匹配算法，即頂點(diǎn)優(yōu)先的貪婪算法、權(quán)值優(yōu)先的貪婪算法、二部圖最大權(quán)匹配算法。

(1) 頂點(diǎn)優(yōu)先的貪婪算法

為計算完備匹配，一種策略是從頂點(diǎn)x∈L出發(fā)，在其相鄰的未覆蓋頂點(diǎn)中，挑選邊權(quán)最大的頂點(diǎn)y∈R，加入匹配，L中其他頂點(diǎn)依次處理。

容易理解，維漢句子數(shù)分別為m和n時，算法時間復(fù)雜度為O(m*n)。算法匹配結(jié)果與頂點(diǎn)x的取出順序有關(guān)，經(jīng)過實驗比較，隨機(jī)取x比按照固定順序(從1到m)的匹配準(zhǔn)確率高20%左右。另外該算法做法是貪心的，不能保證權(quán)值之和最大，只能保證完備匹配。

圖1 雙語句子相似度的計算流程圖

(2) 權(quán)值優(yōu)先的貪婪算法

另一種策略是從權(quán)值大的邊開始，如果該邊的兩個頂點(diǎn)都是未配點(diǎn)，則該邊加入匹配，否則丟棄。依次處理直到?jīng)]有可用邊或者沒有可用頂點(diǎn)。

設(shè)圖中有e條邊，該算法的時間復(fù)雜度為O(eloge)，即算法的主要運(yùn)算為邊的排序操作。在完全圖(滿邊)情況下，e=m*n，算法復(fù)雜度退化為O(m*n*log(m*n))。如果在計算邊權(quán)時按照閾值濾除較小的權(quán)值，將邊的數(shù)量減少，會提高算法速度，但是有可能導(dǎo)致不完備匹配。該算法也是貪心的，不能保證匹配邊的權(quán)和最大。

(3) 二部圖最大權(quán)匹配算法(KM算法)

二部圖最佳匹配的KM經(jīng)典算法由Kuhn和Munkras在1957年提出，時間復(fù)雜度為O(n3)，n為頂點(diǎn)個數(shù)。該算法最新的實現(xiàn)[9]在受限條件下的時間復(fù)雜度降低到O(m*sqrt(n)*logN)，條件是權(quán)值只能取區(qū)間[1，N]內(nèi)的整數(shù)。

因為作者構(gòu)建的二部圖中邊的權(quán)值是浮點(diǎn)數(shù)，所以使用了原始KM算法的一個實現(xiàn)型，時間復(fù)雜度為O(m2*n)，m，n分別為左右兩部分頂點(diǎn)的個數(shù)。

與前面的貪婪算法相比，KM算法在按照確定的順序，不斷擴(kuò)展相等子圖中的匹配邊，達(dá)到完備匹配時就能保證總體權(quán)和最大。

4.4 實驗結(jié)果

目前可共享的維漢對齊語料集幾乎沒有，本文使用的實驗數(shù)據(jù)為維語專家人工對齊的無重復(fù)的900個中文句和900個對應(yīng)維文句(來自不同的互聯(lián)網(wǎng)新聞文章)。

4.4.1 特征有效性檢驗

為了檢驗不同特征對平行句對挖掘的作用，首先使用詞典詞作為唯一匹配特征，在900個維文句子和900個中文句子的相似度矩陣中，使用KM算法，得到正確句珠781個(句珠總數(shù)為900個)，正確率為86.78%。在此基礎(chǔ)上逐步增加其他特征，包括人名地名、數(shù)字特征、句子長度等，最后融合所有的句子特征進(jìn)行對齊實驗。結(jié)果如圖2所示。

從圖2可以看出，融合人名地名特征后，正確率上升到87.11%，再融合數(shù)字特征后，正確率有了較大的提升，達(dá)到93.78%。這一點(diǎn)在三種算法的結(jié)果中都得到驗證。最后融合長度特征后，頂點(diǎn)優(yōu)先匹配算法的正確率出現(xiàn)輕微下降(從70.33%到67.78%)，而權(quán)值優(yōu)先匹配算法和KM算法的正確率仍有提高。說明句子長度特征有時會干擾句子對齊，尤其在對齊大規(guī)模無序句子時，不宜將其作為主要特征。

結(jié)果表明，詞典詞、人名地名、數(shù)字和句子長度特征的融合有效增加了句子對齊的正確率。

圖2 特征選擇在平行句對挖掘中的效果

4.4.2 算法比較

為比較三種算法的對齊效果，分別用100對句子，200對直至900對句子進(jìn)行驗證。實驗結(jié)果如圖3所示。

從圖3中可以看出，句子集合的規(guī)模增加后，一個原文句子對應(yīng)的候選句子變多，對齊算法的準(zhǔn)確率有所下降。但是三種算法的表現(xiàn)不同： KM算法對所有句子的配對反復(fù)調(diào)整，進(jìn)行全局優(yōu)化，確實做到了最佳匹配。而權(quán)值優(yōu)先算法只按照句子相似度進(jìn)行貪婪匹配，在句子數(shù)少于300時，準(zhǔn)確率與KM差距很小，句子規(guī)模超過300時，有大約5%的下降。表明句子相似度本身是對齊的基礎(chǔ)因素，而全局的優(yōu)化調(diào)整能進(jìn)一步提高對齊正確率。而頂點(diǎn)優(yōu)先算法的準(zhǔn)確率整體上比較低。在句子規(guī)模超過300后，匹配正確率下降較快，而且曲線不單調(diào)(從88%下降到68.86%再回升到70.44%)。說明該算法不穩(wěn)定，對句子規(guī)模比較敏感。原因是一旦某個頂點(diǎn)(原文句)選擇了錯誤的對應(yīng)頂點(diǎn)(譯文句)，必然要影響其他頂點(diǎn)的匹配，造成錯誤的蔓延。

隨著句子規(guī)模的增大，權(quán)值優(yōu)先匹配算法和KM算法魯棒地保持了較高的準(zhǔn)確率。說明這兩種算法的泛化能力較強(qiáng)。

圖3 三種算法在維中文句子上的匹配準(zhǔn)確率

4.4.3 句子數(shù)量不均衡情形下的雙語句子對齊

真實語料中往往存在無法找到匹配句的情況，因而不是嚴(yán)格意義上的1： 1對齊。為了檢驗這種情況的影響，我們構(gòu)建了不均衡語料。先使用100個維文句與不同數(shù)量的中文句子(從100到900)進(jìn)行對齊測試，結(jié)果如圖4中深色柱狀圖所示；然后用100個中文句與不同數(shù)量的維文句進(jìn)行對齊測試，結(jié)果如圖4中淺色柱狀圖所示。測試結(jié)果的召回率和準(zhǔn)確率相等，分子是正確匹配的句對數(shù)，分母是中文句子數(shù)量和維文句子數(shù)量的較小值。

從圖4中可以看出，隨著雙語句子數(shù)量差異的增大，對齊效果逐漸變差，這表明均衡語料的對齊效果要優(yōu)于偏斜語料。而圖4中每一組深色柱狀圖均高于淺色柱狀圖，即中文句子較多時，對齊的效果好于維文句子較多的情形，這說明維文句子更適合作為對齊的基準(zhǔn)。

圖4 KM算法在維中文句子數(shù)量不均衡時的對齊準(zhǔn)確率

4.4.4 包含一對多對齊情形的雙語句子

真實雙語網(wǎng)頁文本中的句子數(shù)量從幾十句到幾百句不等。其中對齊模式1∶0或者0∶1的孤立句子無法匹配， 對齊模式為1對多的對齊只抽取其中

最大匹配部分，輸出為1∶1模式的假平行句對，剩余部分作為孤立句子丟棄。為考察算法在這種情況下的效果，作者搜集了30篇不同時期的雙語新聞網(wǎng)頁，分段分句后進(jìn)行測試。表2給出了表格的一部分。

表2 句子缺失和部分匹配情形下的對齊準(zhǔn)確率

從表2中看出，所有1∶1模式的句珠幾乎都能正確找到；而1∶2，2∶2和1∶3模式的句珠只能得到部分匹配，這樣匹配結(jié)果并非完全錯誤，而是近似匹配，但是在統(tǒng)計正確率時都認(rèn)為是錯誤的。

5 總結(jié)與下一步工作

本文提出了一種基于多特征融合的雙語句子相似度計算方法，在此基礎(chǔ)上利用二部圖匹配算法實現(xiàn)非連續(xù)雙語文本的平行句對挖掘。先在篇章層面利用ICTCLAS獲得中文人名地名，然后按規(guī)則轉(zhuǎn)寫對應(yīng)的維文譯名，解決了大部分未登錄詞的互譯匹配，又在句子層面用串匹配方法避免了中文分詞的歧義問題。然后在句對相似度矩陣上，使用二部圖的最佳匹配(KM算法)得到句珠，在900個句對的測試中，達(dá)到95.67%的準(zhǔn)確率。在實驗中發(fā)現(xiàn)，維漢法律文件和政府工作報告等正式文本的句子對齊正確率接近100%。而多處省略了大段中文句子的雙語新聞句子對齊正確率稍低(86.36%)，該情形并不適合采用動態(tài)規(guī)劃算法處理。

經(jīng)統(tǒng)計每個維文句子中平均有五個單詞需要進(jìn)行詞干還原。作者僅僅根據(jù)規(guī)則進(jìn)行詞干還原，發(fā)現(xiàn)正確率幾乎沒有變化(從95.33%提高到95.67%)，說明詞干還原的方法需要深入研究。

[1] Pascale Fung， Percy Cheung. Multi-level Bootstrapping for Extracting Parallel Sentences from a Quasi-Comparable Corpus[C]//Proceedings of the 20th international conference on Computational,2004.

[2] 田生偉，吐爾根·伊布拉音，禹龍，等.與策略漢維句子對齊[J].計算機(jī)科學(xué)，2010，37(4)：215-218.

[3] William A Gale，Kenneth W Church. A program for aligning sentences in bilingual corpora[C]//Proceedings of the ACL-91.

[4] Dekai Wu. Aligning a parallel English-Chinese corpus statistically with lexical criteria[C]//Proceedings of the 32nd annual meeting of the association for computational linguistics, Las cruces, New Mexico.

[5] 吳宏林，劉紹明，于戈.基于加權(quán)二部圖的漢日詞對齊[J]，中文信息學(xué)報，2011，21(5)： 101-106.

[6] Samat mamitimin, Min Hou. Chinese-Uyghur Sentence Alignment: An approach Based on Anchor Sentences[C]//Proceedings of the 2ndWorkshop on Building and Using Comparable Corpora, ACL-IJCNLP 2009.

[7] 李佳正，劉凱，麥熱哈巴·艾力，等. 維吾爾語中漢族人名的識別及翻譯[J]，中文信息學(xué)報，2011，25(4)： 82-87.

[8] Batuer Aisha, Maosong Sun. A Statistical Method for Uyghur Tokenization[C]//Proceedings of the Natural Language Processing and Knowledge Engineering, 2009.

[9] Ran Duan, Hsin-Hao Su. A Scaling Algorithm for Maximum Weight Matching inBipartite Graphs[C]//Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms，2012.

[10] 王斌. 漢英雙語語料庫自動對齊研究[D]. 中國科學(xué)院計算技術(shù)研究所博士學(xué)位論文，2000.

[11] 塞麥提·麥麥提敏，亞森·伊明. 基于轉(zhuǎn)換規(guī)則的漢文-維文專有名詞自動翻譯研究[C].第七屆中文信息處理國際會議，2007.

Uyghur Chinese Sentence Alignment Based on Multi Features and Optimal Matching

Ni Yaoqun1,2,3, Xu Hongbo1, Cheng Xueqi1

(1. CAS Key Laboratory of Network Data Science & Technology, Institute of Computing Technology,Chinese Academy of Sciences, Beijing 100190， China；2. Department of Language Engineering, University of Chinese Academy of Sciences，Beijing 100049， China；3. Department of Language Engineering, University of Foreign Languages, Luoyang, Henan 471003, China)

The content of Uyghur webpage news is usually partial comparable with the content of the Chinese counterpart. Uyghur sentence sequences may be shuffled or even partially missing in Chinese text, which cause some difficulties in mining parallel sentences (i.e. sentence bead) from bilingual news. Fist, to improve the word matching rate of this kind, person and location names in Chinese are extracted and translated into Uyghur to enhance bilingual mapping. Then we scan the Chinese sentences with translation of Uighur words and calculate the translation rate via string matching to avoid mistakes in Chinese word segmentation. The final similarity of a sentence pair is calculated by combining the word translation rate with the numbers, punctuations and length of sentences as features. Similarities of all the bilingual sentence pairs constructed a weight matrix. We used greedy algorithm and maximum weight matching algorithm in bipartite graph to find the parallel sentence pairs with highest probability. Our method achieves an accuracy of 95.67% in sentence alignment.

sentence alignment; translation of human name and location name; multiple features blending; maximum weight matching in bipartite graph

倪耀群(1974—),博士,講師,主要研究領(lǐng)域為自然語言處理、數(shù)據(jù)挖掘等。E-mail:niyaoqun@126.com許洪波(1975—),博士,副研究員,主要研究領(lǐng)域為互聯(lián)網(wǎng)搜索與挖掘、大數(shù)據(jù)分析與計算、自然語言處理等。E-mail:hbxu@ict.ac.cn程學(xué)旗(1971—),博士,研究員,主要研究領(lǐng)域為互聯(lián)網(wǎng)搜索與挖掘、網(wǎng)絡(luò)科學(xué)與社會計算、網(wǎng)絡(luò)與信息安全等。E-mail:cxq@ict.ac.cn

1003-0077(2016)04-0124-10

2014-10-09 定稿日期： 2015-03-15

國家自然科學(xué)基金(61232010，61303156)；國家973課題(2012CB316303)；國家863課題(2012AA011003)；國家科技支撐計劃(2012BAH46B04)

TP391

A