蒙古語固定短語識別算法的設(shè)計與實現(xiàn)

斯·勞格勞

(內(nèi)蒙古大學(xué) 蒙古學(xué)學(xué)院，內(nèi)蒙古 呼和浩特 010021)

蒙古語固定短語識別算法的設(shè)計與實現(xiàn)

斯·勞格勞

(內(nèi)蒙古大學(xué) 蒙古學(xué)學(xué)院，內(nèi)蒙古 呼和浩特 010021)

固定短語的自動識別和標(biāo)注是進(jìn)行蒙古語文本處理的基礎(chǔ)和前提條件。詞類標(biāo)注、短語標(biāo)注、句法分析、語義分類及語義角色標(biāo)注等基礎(chǔ)研究和機(jī)器翻譯、文本校對等應(yīng)用系統(tǒng)的開發(fā)均以正確標(biāo)注固定短語的文本為處理對象。該文在“蒙古語固定短語語法信息詞典”的基礎(chǔ)上采用基于有限狀態(tài)自動機(jī)和規(guī)則的方法設(shè)計實現(xiàn)了固定短語識別和標(biāo)注算法。經(jīng)實驗，其識別率已達(dá)到90%以上，在處理中，詞均用時與基于字符串匹配的算法相比提高較多，達(dá)到0.005 0ms。

蒙古語；固定短語識別；有限狀態(tài)自動機(jī)

1 引言

固定短語的自動識別和標(biāo)注是蒙古語詞法分析、句法分析和語義分析等基礎(chǔ)研究的前提，并且在機(jī)器翻譯、文本校對等應(yīng)用系統(tǒng)的開發(fā)中起著重要作用。

在蒙古語傳統(tǒng)語法研究中，對“固定短語”的研究非常少，只有大致分類而鮮有深入細(xì)致的研究，尤其是對各類“固定短語”的語法特點(diǎn)很少涉及。

在蒙古語信息處理研究中，內(nèi)蒙古師范大學(xué)青格樂圖老師科研團(tuán)隊通過兩次國家社科基金項目“蒙古語固定短語語法屬性庫框架設(shè)計”(2002—2003)和“蒙古語固定短語語法信息詞典的建立及調(diào)試”(2005—2007)，完成了各類固定短語語法屬性的設(shè)置和詞語收集工作，詞典條目已達(dá)到28 000多條。

固定短語的識別應(yīng)屬于詞法分析的詞切分問題，類型標(biāo)注應(yīng)屬于詞類標(biāo)注領(lǐng)域。蒙古語屬于拼音文字，詞切分不像漢語那么復(fù)雜，主要依據(jù)詞間的空格來切分，但這樣的切分只能切分為單詞，無法識別固定短語。在以往的蒙古語詞法分析研究中幾乎沒有涉及固定短語的識別和標(biāo)注問題。例如，目前在蒙古文信息處理領(lǐng)域被廣泛應(yīng)用的詞語識別及詞類標(biāo)注軟件MgLex[1]沒有處理固定短語的切分和標(biāo)注問題。還有文獻(xiàn)[2-4]等詞法分析或詞類標(biāo)注研究均沒有涉及固定短語的切分和類型標(biāo)注問題。文獻(xiàn)[5]中雖然涉及固定短語識別問題，但只局限在命名實體的研究。

現(xiàn)階段蒙古語詞法分析或詞類標(biāo)注系統(tǒng)基本都采用基于統(tǒng)計的方法，而基準(zhǔn)語料的缺乏(目前只有100萬詞詞類標(biāo)注語料)使這些方法在性能和效率上沒有大的改進(jìn)。為了克服基準(zhǔn)語料不足的局限性，本文在已有資源——“現(xiàn)代蒙古語固定短語語法信息詞典”的基礎(chǔ)上采用基于詞典和規(guī)則的方法實現(xiàn)了蒙古語固定短語識別及標(biāo)注系統(tǒng)。在效率方面，為了提高查找速度，采用基于有限狀態(tài)自動機(jī)的方法構(gòu)造了蒙古語固定短語識別算法，最終詞典查找速度比基于字符串查找的方法提高較多。經(jīng)在100萬詞現(xiàn)代蒙古語語料庫上的測試，固定短語召回率達(dá)到90%以上，類型標(biāo)注準(zhǔn)確率達(dá)到了99%以上。

需要說明的是，名詞術(shù)語也屬于固定短語，但其識別與標(biāo)注屬于人名識別、地名識別和機(jī)構(gòu)名識別等命名實體的識別研究，因此本文所指的固定短語識別沒有包含“名詞術(shù)語”的識別。

2 蒙古語固定短語的定義及分類體系

2．1 蒙古語固定短語的定義

蒙古語固定短語，又叫固定詞組，是指基本上由兩個或兩個以上的詞組合而成的在形式和語義上結(jié)合緊密，表達(dá)一個詞匯概念，構(gòu)成一個詞匯單位，充當(dāng)一個句子成分或某一種附帶成分的組合[6]。這個定義包含以下幾方面的內(nèi)容。

(1) 固定短語基本上由兩個或兩個以上的詞組成。組成成分可以是實詞，也可以是虛詞，或者是附加成分，但其中一個成分必須是實詞。

(2) 固定短語在結(jié)構(gòu)形式或語義上結(jié)合緊密，一般固定成一個語法單位，像一個詞。有些固定短語在語義上固定的，有些在形式上是固定的。

(3) 固定短語作為一個詞匯單位，表示一個一般概念。

(4) 固定短語在句子中充當(dāng)一個句子成分或輔助成分。

2.2 蒙古語固定短語分類體系

蒙古語固定短語分為復(fù)合詞、習(xí)用語、成語、固定詞和名詞術(shù)語五大類[7-8]。固定短語的詞類代碼用一個大寫英文字母表示，小寫英文字母表示子類代碼，這與“信息技術(shù) 信息處理用蒙古語詞語標(biāo)記集”一致，如表1所示。

表1 蒙古語固定短語分類體系

在不包含名詞術(shù)語的情況下，蒙古語固定短語中復(fù)合詞的比例占到95%以上，其中復(fù)合名詞的比例最高，占到80%以上。因此，蒙古語固定短語識別的重點(diǎn)在復(fù)合詞的識別上。

3 蒙古語固定短語識別及標(biāo)注算法

基于詞典的蒙古語單詞識別常用文本-詞典的匹配算法，即首先以空格、標(biāo)點(diǎn)、非蒙文字符等作為邊界標(biāo)示從文本中截取一個字符串，然后在詞典中查找，如果找到，則識別成功。但固定短語由兩個或兩個以上單詞構(gòu)成，并且其長度是變化不定的，用該方法無法實現(xiàn)識別任務(wù)。即便使用像中文分詞常用的最大正向匹配或最大逆向匹配算法能夠?qū)崿F(xiàn)，但其效率也不高。如果采用詞典-文本的匹配算法，可以解決已登錄固定短語的識別，即依次讀取詞典中的詞條，然后在文本中進(jìn)行匹配。但這種算法也存在問題： 首先是識別速度非常慢，其次是對于固定短語的形態(tài)變化無法有效識別。

鑒于上述問題，我們在“蒙古語固定短語語法信息詞典”和“變形附加成分詞典”的基礎(chǔ)上采用有限狀態(tài)自動機(jī)的方法構(gòu)造了固定短語識別器[9-14]。識別器由固定短語自動機(jī)(fixed phrase automata,FPA)和構(gòu)形附加成分自動機(jī)(formation suffix automata,FSA)兩部分構(gòu)成。蒙古語具有豐富的形態(tài)變化，尤其是動詞的形態(tài)變化非常多，有些詞的形態(tài)變化甚至能達(dá)到幾百種。因此，詞典中一般只包含詞干形式，形態(tài)變化的識別需要相應(yīng)的附加成分詞典。在識別字符串的過程中，如果詞根自動機(jī)中沒有狀態(tài)轉(zhuǎn)移，則回溯到最近的詞根狀態(tài)，并轉(zhuǎn)移到附加成分自動機(jī)，繼續(xù)進(jìn)行識別。由于存在詞根回溯的問題，F(xiàn)PA和FSA是一種不確定有限狀態(tài)自動機(jī)。但詞根回溯只在識別已登錄固定短語形態(tài)變化形式時出現(xiàn)，因此可以認(rèn)為該自動機(jī)是一種帶詞根回溯的確定有限狀態(tài)自動機(jī)。

3.1 固定短語識別器的構(gòu)造

在構(gòu)造上，F(xiàn)PA和FSA完全一樣，均為9元組， 形式如下：

FPA = FSA = (S,∑,δ,suffix,recall，stack，s0,U,F)，

其中：S為有限的狀態(tài)集合，∑為有限的輸入字符集合，δ為狀態(tài)轉(zhuǎn)移函數(shù)，suffix為從固定短語詞根自動機(jī)到附加成分自動機(jī)的狀態(tài)轉(zhuǎn)移函數(shù)，recall為詞根回溯函數(shù)，stack為詞根棧，s0為初始狀態(tài)，U為詞根狀態(tài)集合，F(xiàn)為終結(jié)狀態(tài)集合。FPA和FSA均為不確定有限狀態(tài)自動機(jī)，但除詞根回溯，狀態(tài)轉(zhuǎn)移都是確定的。

(1)S= {s0,s1,s2,…，sn-1,sn}，包括初始狀態(tài)s0、詞根狀態(tài)U、終結(jié)狀態(tài)F。

(3)δ(si, ch)=sj(si∈S，sj∈S，ch∈∑)，當(dāng)sj∈U時，Push(sj，stack)。

(4) suffix(ci)=s0(ci∈U，s0∈FSA)

(5) recall (si)=sj(si∈S，si∈U，sj= Pop(stack))。

(6) stack為詞根棧。保存每次固定短語識別過程中遇到的詞根狀態(tài)。

(7)s0∈S。

(9)F?S。

自動機(jī)的構(gòu)造如圖1、圖2所示。

說明1圖1中，s0、s1、s2、s3、si、si+1、si+2、sj、sj+1、sj+2、sk、sk+1、sk+2、sl、sl+1、sl+2、sm、sm+1、sm+2、sn、sn+1、sn+2表示狀態(tài)，其中，s0為初始狀態(tài)，縱向箭頭表示指向孩子節(jié)點(diǎn)的指針，橫向箭頭表示指向兄弟節(jié)點(diǎn)的指針，“…”表示未畫出的孩子節(jié)點(diǎn)和兄弟節(jié)點(diǎn)。每個節(jié)點(diǎn)可以有有限多個孩子節(jié)點(diǎn)，但為了構(gòu)造上的方便，只設(shè)了一個Child指針，其余孩子節(jié)點(diǎn)作為第一個孩子節(jié)點(diǎn)的兄弟節(jié)點(diǎn)通過NextBrother與之相連。如果一個節(jié)點(diǎn)有n個孩子節(jié)點(diǎn)，那么構(gòu)造自動機(jī)時，設(shè)n個Child指針和設(shè)一個Child指針、n-1個NextBrother指針在識別效率上是等價的。

說明2圖2中，Char表示狀態(tài)字符，Type表示詞根節(jié)點(diǎn)中存放的固定短語類型代碼，Stem表示詞根字符串(固定短語)，Child表示指向孩子節(jié)點(diǎn)的指針，NextBrother表示指向兄弟節(jié)點(diǎn)的指針。由于除詞根回溯之外，F(xiàn)PA或FSA中狀態(tài)轉(zhuǎn)移是確定的，因此在節(jié)點(diǎn)結(jié)構(gòu)中沒有設(shè)Parent和PrevBrother指針。

3.2 固定短語識別算法

算法描述如下：

圖1 FPA和FSA的狀態(tài)轉(zhuǎn)移圖

圖2 狀態(tài)節(jié)點(diǎn)結(jié)構(gòu)

step1將文本輸入給FPA(FSA)進(jìn)行識別，如果在狀態(tài)轉(zhuǎn)移過程中遇到詞根狀態(tài)，則壓入詞根棧。

step2如果無法進(jìn)行狀態(tài)轉(zhuǎn)移，則查看當(dāng)前輸入字符是否為“空格”，如果“是”，則轉(zhuǎn)到step3,否則轉(zhuǎn)到step4；

step3如果當(dāng)前狀態(tài)為詞根狀態(tài)，則找到固定短語，并進(jìn)行標(biāo)注，然后將當(dāng)前狀態(tài)設(shè)為FPAs0，并轉(zhuǎn)到step1；否則直接將當(dāng)前狀態(tài)設(shè)為FPAs0，并轉(zhuǎn)到step1；

step4如果詞根棧不為空，則彈出并回溯到棧頂狀態(tài)，然后通過Suffix函數(shù)轉(zhuǎn)移到狀態(tài)FSAs0，轉(zhuǎn)到step1；否則轉(zhuǎn)到step5；

step5將輸入字符移到下一個空格，當(dāng)前狀態(tài)設(shè)為FPAs0，并轉(zhuǎn)到step1；

具體實現(xiàn)過程如算法1所示。

3.3 固定短語識別實例

圖3 固定短語識別過程狀態(tài)轉(zhuǎn)移圖

說明： 圖3中，圓圈表示狀態(tài)，雙線圈表示詞根狀態(tài)，圓圈里的字符表示狀態(tài)字符，橫向箭頭表示一次狀態(tài)轉(zhuǎn)移(調(diào)用step函數(shù))，箭頭上方的字符為輸入字符。

3.4 未登錄固定短語的識別

上述三種復(fù)合詞的一部分已被收錄到詞典里，但不全，對于未登錄的部分根據(jù)其構(gòu)詞規(guī)則歸納總結(jié)了相應(yīng)的識別規(guī)則。在識別順序上先用詞典識別，再對結(jié)果文本進(jìn)行第二次掃描，處理具有規(guī)律性的復(fù)合詞。

3.5 算法的系統(tǒng)實現(xiàn)

我們用Visual C++7.1實現(xiàn)了蒙古語固定短語識別及標(biāo)注算法[15-16]，并將程序模塊添加到了蒙古語多功能編輯處理系統(tǒng)Mongolian Editor 4.0中，軟件界面如圖4所示，圖中用“=”連接的為固定短語。

圖4 蒙古語固定短語識別軟件界面

4 結(jié)論

本算法的一個主要特點(diǎn)是，在固定短語識別中運(yùn)用了有限狀態(tài)自動機(jī)，其目的是為了克服字符串匹配算法中的時間消耗，提高算法的運(yùn)行效率。因此，在試驗中增加了衡量算法運(yùn)行速度的指標(biāo)T。程序運(yùn)行時，算法對輸入文本進(jìn)行全文掃描，如果有固定短語則對其進(jìn)行識別和標(biāo)注。運(yùn)行效率與文本長度和文本所含固定短語個數(shù)有關(guān)，而與固定短語詞典大小無關(guān)，因此計算T時采用了式(2)。

目前，還沒有標(biāo)注固定短語的蒙古語基準(zhǔn)語料，因此，我們先用人工標(biāo)注的方法對測試語料添加了固定短語標(biāo)記。測試時，首先從測試語料副本中去掉固定短語標(biāo)記，然后采用識別和標(biāo)注算法對文本進(jìn)行標(biāo)注。最后通過集成在固定短語標(biāo)注軟件中的評價函數(shù)對人工標(biāo)注和自動標(biāo)注結(jié)果進(jìn)行對比，得到測試結(jié)果。測試結(jié)果如表2所示。

表2 實驗結(jié)果

經(jīng)測試發(fā)現(xiàn)，算法性能和效率已達(dá)到預(yù)期目標(biāo)。但識別率還有待提高，需要通過人工或半自動方式從大規(guī)模文本語料中收集固定短語。我們正在構(gòu)建蒙古語詞語搭配網(wǎng)絡(luò)，在該網(wǎng)絡(luò)上采用無監(jiān)督的機(jī)器學(xué)習(xí)方法可以發(fā)現(xiàn)一部分出現(xiàn)頻率較高的固定短語，但出現(xiàn)頻率較低的固定短語則需要通過人工方式進(jìn)行收集。

顧名思義，固定短語是詞語的一種固定的搭配形式，在蒙古語中，除形態(tài)上的變化外，其數(shù)量是有限的。因此，采用基于詞典的方法進(jìn)行識別和標(biāo)注是最有效的。經(jīng)過長期收集，固定短語詞條數(shù)目目前已達(dá)到3萬余詞，基本上包含了90%以上的蒙古語固定短語，但覆蓋率還不夠高，今后還需要通過人工或半自動方式收集詞條，擴(kuò)充“蒙古與固定短語語法信息詞典”，提高識別算法的召回率。

目前，蒙古語詞法分析研究主要集中在詞根詞綴切分、單詞識別和人名識別等領(lǐng)域，而復(fù)合詞、習(xí)用語、成語、固定詞、地名、機(jī)構(gòu)名等多詞單元的識別標(biāo)注還處于空白狀態(tài)。此外，蒙古語固定短語與單詞一樣具有豐富的形態(tài)變化(包括名詞附加成分和動詞附加成分)，其他語種固定短語識別技術(shù)與蒙古語相應(yīng)技術(shù)具有明顯的差別，因此，在這里尚未做有關(guān)方法的對比分析。

本文介紹的基于不確定有限狀態(tài)自動機(jī)的方法除了對固定短語的識別外，對蒙古語詞根/詞綴的切分、讀音糾錯、詞類標(biāo)注等基于詞典的算法具有廣泛的適應(yīng)性，其主要特點(diǎn)是運(yùn)行效率高，適合實時文本處理。

[1] 吳金星. 蒙古語詞法標(biāo)注語料庫的構(gòu)建及相關(guān)技術(shù)研究[D].內(nèi)蒙古大學(xué)碩士學(xué)位論文，2011.

[2] 華沙寶.蒙古語語料庫的詞類標(biāo)注系統(tǒng)——AYIMAG[J].內(nèi)蒙古大學(xué)學(xué)報(人文社會科學(xué)版)，1999，31(5)：31-35.

[3] 張貫虹,斯·勞格勞,烏達(dá)巴拉. 融合形態(tài)特征的最大熵蒙古文詞性標(biāo)注模型[J].計算機(jī)研究與發(fā)展，2011,48(12)： 2385-2390.

[4] 王斯日古楞. 蒙古語單詞詞性自動識別研究[J].內(nèi)蒙古師范大學(xué)學(xué)報(自然科學(xué)漢文版)，2007,36(3)：319-321.

[5] 吳金星. 蒙古語語料庫加工集成平臺的構(gòu)建[D]，內(nèi)蒙古大學(xué)博士學(xué)位論文，2015.

[6] 德·青格樂圖. 現(xiàn)代蒙古語固定短語語法信息詞典詳解[M]. 呼和浩特: 內(nèi)蒙古教育出版社，2005.

[7] 德·青格樂圖. 面向信息處理的蒙古語固定詞組研究[M].呼和浩特: 內(nèi)蒙古教育出版社，2001.

[8] 德·青格樂圖. 面向信息處理的蒙古語固定詞組分類[J].內(nèi)蒙古師范大學(xué)學(xué)報(哲學(xué)社會科學(xué)蒙文版)，2000(3)： 120-128.

[9] 斯·勞格勞. 基于不確定有限自動機(jī)的蒙古文校對算法[J].中文信息學(xué)報，2009，23(6)： 110-115.

[10] 姜文斌,吳金星,烏日力嘎,等. 蒙古語有向圖形態(tài)分析器的判別式詞干詞綴切分[J].中文信息學(xué)報， 2011，25(4)： 30-34.

[11] Yael Cohen-Sygal. Finite-state registered automata for non-concatenative morphology[C]//Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics. Australia: Association for Computational Linguistics, 2006, 681-688.

[12] Yona S, Shuly Wintner. A fnite-state morphological grammar of Hebrew[J]. Natural Language Engineering, 2008,14(2): 173-190.

[13] Koskenniemi K. Two-level morphology: a general computational model for word-form recognition and production. The Department of General Linguistics, University of Helsinki, PUBLICATION, 1983(11).

[14] Kay M. Non-concatenative fnite-state morphology[C]//Proceedings of the Third Conference of the European Chapter of the Association for Computational Linguistics, Cpenhagen, Denmark, 1987: 2-10.

[15] Zoltán Juhász,dám Sipos , Implementation of anite state machine with active libraries in C++[C]//Proceedings of the 7th International Conference on Applied Informatics Eger, Hungary, 2007(2): 247-255.

[16] 阿孜古麗·夏力甫,早克熱·卡德爾,吐爾根·依布拉音. 維吾爾語動詞體范疇的有限狀態(tài)自動機(jī)的構(gòu)建[J]. 中文信息學(xué)報， 2012，26(4)： 61-65.

斯·勞格勞(1972—)，博士，副教授，主要研究領(lǐng)域為蒙古文信息處理。

E-mail： sloglo@sina.com

DesignandImplementationofMongolianFixedPhraseRecognitionAlgorithm

S Loglo

(College of Mongolian Studies, Inner Mongolia University, Hohhot，Inner Mongolia 010021，China )

Automatic identification and annotation of fixed phrases are esseential to the Mongolian text processing. On the basis of “Mongolian Fixed Phrase Grammatical Information Dictionary”, this paper designs and implements an algorithm for Mongolian fixed phrase recognition and labeling based on finite state automata and rules. Experiments reavel an recognition rate of more than 90%, and an average processing speed of 0.005 millisecond per word.

Mongolian language; fixed phrase recognition; finite state automata

1003-0077(2017)05-0085-07

TP391

A

2016-03-16定稿日期2017-04-26

國家自然科學(xué)基金(61662050);國家自然科學(xué)基金(61262046)；國家社科基金(10CYY022)；內(nèi)蒙古大學(xué)高層次人才引進(jìn)項目