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

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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

3 句子對(duì)齊的特征選擇

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

3.1 雙語人名地名特征

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

3.1.1 漢字到維文的直譯方法

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

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

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

最終構(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]從維文到漢族人名的翻譯方法存在不確定性，一個(gè)人名拼音對(duì)應(yīng)的多個(gè)中文人名只能通過概率計(jì)算，得到最可能的中文名。作者基于中文人名的漢字拼音，按照確定的規(guī)則獲取維文人名，避免了概率計(jì)算可能帶來的錯(cuò)誤。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

3.3.2 詞典詞匹配方法

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

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

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

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

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

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

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

simT(Us,Cs)=

(2)

3.4 雙語句子長度特征

考慮到維文詞典中存在大量的短語，切分出的詞長懸殊較大，因而詞個(gè)數(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是每個(gè)中文字對(duì)應(yīng)維文字符數(shù)的期望值，通過計(jì)算維中句子長度比值的平均值得到；之后根據(jù)c計(jì)算(len(Us)-c*len(Cs))2/len(Cs)的均值，得到統(tǒng)計(jì)方差σ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)

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

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

(5)

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

(6)

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

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

4.1 多特征融合的雙語句對(duì)相似度計(jì)算

維文句子U和中文句子C的內(nèi)容相似度sim0可以用式(7)計(jì)算，其中詞義匹配度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配對(duì)，那么len(Us)-c*len(Cs)≈0，δ≈0；從而simL(Us，Cs)也較大，以句子長度衡量匹配度較大。但是反過來，兩個(gè)句子的長度即使?jié)M足δ=0，也不能說兩個(gè)句子就是配對(duì)的(因?yàn)閮?nèi)容可能完全不同)?？梢娋渥娱L度匹配度simL只是一個(gè)必要非充分條件。這樣的條件一般用于懲罰原相似度sim0。為此作者修正句子相似度為式(8)。

(8)

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

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

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

4.2 二部圖構(gòu)建

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

定義： 二部圖最佳匹配

帶權(quán)二部圖G=(V，W)的每條邊都有一個(gè)非負(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 平行句對(duì)挖掘算法

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

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

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

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

圖1 雙語句子相似度的計(jì)算流程圖

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

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

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

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

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

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

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

4.4 實(shí)驗(yàn)結(jié)果

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

4.4.1 特征有效性檢驗(yàn)

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

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

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

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

4.4.2 算法比較

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

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

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

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

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

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

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

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

4.4.4 包含一對(duì)多對(duì)齊情形的雙語句子

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

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

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

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

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

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

經(jīng)統(tǒng)計(jì)每個(gè)維文句子中平均有五個(gè)單詞需要進(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] 田生偉，吐爾根·伊布拉音，禹龍，等.與策略漢維句子對(duì)齊[J].計(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)二部圖的漢日詞對(duì)齊[J]，中文信息學(xué)報(bào)，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] 李佳正，劉凱，麥熱哈巴·艾力，等. 維吾爾語中漢族人名的識(shí)別及翻譯[J]，中文信息學(xué)報(bào)，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òng)對(duì)齊研究[D]. 中國科學(xué)院計(jì)算技術(shù)研究所博士學(xué)位論文，2000.

[11] 塞麥提·麥麥提敏，亞森·伊明. 基于轉(zhuǎn)換規(guī)則的漢文-維文專有名詞自動(dòng)翻譯研究[C].第七屆中文信息處理國際會(huì)議，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)域?yàn)樽匀徽Z言處理、數(shù)據(jù)挖掘等。E-mail:niyaoqun@126.com許洪波(1975—),博士,副研究員,主要研究領(lǐng)域?yàn)榛ヂ?lián)網(wǎng)搜索與挖掘、大數(shù)據(jù)分析與計(jì)算、自然語言處理等。E-mail:hbxu@ict.ac.cn程學(xué)旗(1971—),博士,研究員,主要研究領(lǐng)域?yàn)榛ヂ?lián)網(wǎng)搜索與挖掘、網(wǎng)絡(luò)科學(xué)與社會(huì)計(jì)算、網(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)；國家科技支撐計(jì)劃(2012BAH46B04)

TP391

A