摘要：維吾爾語單詞的構(gòu)形詞綴按照一定的規(guī)則連接到詞干。維吾爾語的黏著語特點和構(gòu)形詞綴連接規(guī)則使得可以構(gòu)造維吾爾語構(gòu)形詞綴的有限狀態(tài)自動機。該文將詳細(xì)介紹維吾爾語形容詞構(gòu)形詞綴有限自動機的構(gòu)造步驟。

關(guān)鍵詞：維吾爾語；黏著語；構(gòu)形詞綴；有限自動機；語音和諧；詞干提取

中圖分類號：TP391文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2009)04-0939-03

Uyghur Adjective Inflectional Suffix FSM

Zaokere·Kadeer， Tuergen·Yibulayin

(College of Information Science Engineering， Xinjiang University， Urumqi 830046， China)

Abstract: In Uyghur， the suffixes are affixed to the stem according to definite ordering rules. The agglutinative and rule-based nature of word formations in Uyghur allows modelling of the morphological structure of language in Finite State Machines(FSMs). This paper describes the steps of forming the reverse ordered Uyghur language Adjective suffix FSM.

Key words: uyghur; agglutinative; inflectional suffix; finite State machine; vowel harmony; stemming

1 引言

在黏著語言詞干提取算法與中文分詞一樣很重要，幾乎所有的自然語言處理系統(tǒng)都需要進(jìn)行詞干提取。例如，電子詞典，機器翻譯系統(tǒng)，搜索引擎等等。詞干提取算法的設(shè)計與實現(xiàn)要求掌握語言的形態(tài)變化規(guī)則和理解應(yīng)用系統(tǒng)的需求。因為不同的系統(tǒng)對詞干提取的要求有所不同，機器翻譯或校對系統(tǒng)等具有詞庫的應(yīng)用系統(tǒng)要求準(zhǔn)確提取詞庫存在的單詞的詞干，而搜索引擎則要求正確提取所有單詞的詞干。目前很多語種已經(jīng)實現(xiàn)了可用的詞干提取。比如，有Malay [1]， Latin [2]， Indonesian[3]， Swedish[4]， German[5] and Turkish[6]等。

詞干提取(stemming)又叫單詞形態(tài)還原，即分開詞干和構(gòu)形詞綴。例如，對單詞■進(jìn)行詞干提取后，詞干為■ 。詞干提取算法只對構(gòu)形詞綴進(jìn)行切分，不去分析構(gòu)詞詞綴。因為機器翻譯，搜索系統(tǒng)等只需要提取單詞的意義，而不需要提取這個單詞來源的詞義。

詞干提取是長時間以來一直被研究的課題。詞干提取算法有Porter算法[7]，詞典查詢方法，有限自動機，基于HMM的方法等。然而，詞干提取具有強烈的語言相關(guān)性。維吾爾語是黏著語，而且構(gòu)形詞綴的連接也具有的一定的規(guī)則。因此，在本文主要對有限自動機進(jìn)行了研究并構(gòu)造出了維吾爾語的形容詞形態(tài)有限自動機。

2 維吾爾語形容詞與形態(tài)

表示人或事物的形狀、性質(zhì)、特征或者動作、行為、變化的狀態(tài)的詞叫形容詞。形容詞最主要的語法功能是修飾、限定名詞、動詞、形容詞等，做定語、謂語或狀語[8]。在維吾爾語中的形容詞按其結(jié)構(gòu)可分為單純形容詞，即由單獨一個主語素構(gòu)成的形容詞，如，■“紅”、 ■“壞”等和合成形容詞兩種，即由兩個主語素或者一個主語素和一個附加語素來構(gòu)成的形容詞，如，■“草綠的”， ■“好哭啼的”等。在維吾爾語中形容詞按其意義和語法特征又可以分為三大類，一是性質(zhì)形容詞，即直接表示人或事物的性質(zhì)或特征的一類形容詞，如，■“大”、 ■ “多”等；二是關(guān)系形容詞，即用來表示事物與時間、空間等概念關(guān)系的形容詞。他通過某一事物與另一事物的關(guān)系拉力說明事物特征，如，■ “城市的”、 ■ “現(xiàn)在的”等；三是特殊形容詞，即能支配名詞格的形容詞，如，■ “有”、 ■“需要的”、 ■“可能”等。

維吾爾語中的形容詞三種類型當(dāng)中只有性質(zhì)形容詞具有級的語法范疇。該語法范疇包括以下幾種形式：

1）原級：沒有形態(tài)變化的形容詞的原體形式。原級是構(gòu)成其他級的基礎(chǔ)形式。如：■“高尚”、■“偉大”、 ■“干凈”、 ■“美麗”等等。

2）比較級：表示一種事物的性質(zhì)、特征與另一事物的性質(zhì)、特征在程度上進(jìn)行比較的形容詞構(gòu)形形式。比較級是在形容詞原級后綴接■詞尾構(gòu)成。如表1所示。

3）加強級：用來加深某一事物彩色特征或特征程度的形容詞構(gòu)型形式。在維吾爾語，有一部分形容詞可通過重復(fù)第一音節(jié)（若為閉音節(jié)時則重復(fù)到元音處為止）再結(jié)合輔音/■/構(gòu)成加強級。如表2所示。

4）表愛級：用來表示人對事物的喜愛或縮小稱呼的一種形容詞構(gòu)形形式。其形式是，在形容詞原級后綴接詞尾■ 構(gòu)成。如表3所示。

形容詞除了可以接受具有自己特有的一些構(gòu)形詞綴，還可以接受大部分名詞的構(gòu)形詞綴。

3 維吾爾語形容構(gòu)形詞綴優(yōu)先自動機的構(gòu)造

在計算機科學(xué)中自動機用作計算機和計算過程的動態(tài)數(shù)學(xué)模型，用來研究計算機的體系結(jié)構(gòu)、邏輯操作、程序設(shè)計乃至計算復(fù)雜性理論。在語言學(xué)中則把自動機作為語言識別器，用來研究各種形式語言。在有限自動機發(fā)展的初期，因它的描述能力有限而拋棄了這個模型。后來，有限狀態(tài)自動機被證明為構(gòu)造基于規(guī)則的語言模型的強大工具之一。在自然語言處理領(lǐng)域已被應(yīng)用于詞性標(biāo)注，句法分析的研究與開發(fā)工作。

有限自動機的基本思想是它由有限狀態(tài)集合和具有一定屬性的弧組成，各狀態(tài)用有向弧線連接。每個弧線都有自己的方向和輸入符號串。這些狀態(tài)和有向弧線結(jié)合構(gòu)成一個網(wǎng)絡(luò)，既有限狀態(tài)自動機[9]。

確定所有構(gòu)形形容詞詞綴和它們間的連接規(guī)則之后，下一步要從左向右的維吾爾語形容詞構(gòu)形詞綴切分有限自動機。構(gòu)造這個自動需要經(jīng)過以下三個步驟：1）構(gòu)造從右向左的非確定自動機；2）給詞綴編號和翻轉(zhuǎn)非確定自動機；3）NFA轉(zhuǎn)換成DFA。

3.1 構(gòu)造從右向左的非確定自動機

詞綴按照一定規(guī)則進(jìn)行互相連接。首先，收集了所有連接規(guī)則，然后在這個規(guī)則庫的基礎(chǔ)上構(gòu)造了從右向左的有限狀態(tài)自動機。 這個FSM所描述從詞干派生單詞變形的過程。

在圖1中，給每個狀態(tài)編了個號碼，在以后的幾個步驟中這些狀態(tài)用這些編號表示。終止?fàn)顟B(tài)用0編號，起始狀態(tài)的編號為1。符號“ε”表示空邊。當(dāng)用這個自動機分析單詞■ (從稍微瘦一點)，首先找到詞干■ (瘦)，然后對其剩下部分進(jìn)行切分分析，從候選路徑中找到比較級詞綴■后把當(dāng)前狀態(tài)轉(zhuǎn)移到狀態(tài)2，然后復(fù)數(shù)詞綴■ 引起從狀態(tài)2到狀態(tài)3的轉(zhuǎn)移，之后詞綴 ■又產(chǎn)生從狀態(tài)3到狀態(tài)4的轉(zhuǎn)移，找到 ■后到達(dá)狀態(tài)6，最后經(jīng)過ε到達(dá)狀態(tài)0。

3.2 給詞綴編號和翻轉(zhuǎn)從右向左的有限狀態(tài)自動機

在這個步驟給每一個詞綴分配唯一的編號，在以后的步驟中進(jìn)行自動機方向翻轉(zhuǎn)，非確定自動機轉(zhuǎn)換成確定自動機時使用這些標(biāo)號。

這個步驟是整個構(gòu)造過程的第一個里程碑。因為狀態(tài)較多，而且弧上的數(shù)字也較多，所以沒能把所有起始狀態(tài)0合并到一起，其實這些狀態(tài)是一個狀態(tài)。

3.3 NFA轉(zhuǎn)換成DFA

輸入一個符號有多個輸出弧線和空符號轉(zhuǎn)移的話，用計算機程序設(shè)計語言實現(xiàn)起來較困難。因此，非確定自動機應(yīng)該轉(zhuǎn)換成確定自動機，這樣可以確保每個符號只能產(chǎn)生一個狀態(tài)轉(zhuǎn)移，并且可以消除空符號轉(zhuǎn)移。叫做“subset construction” [9]的算法用于解決此類問題。在這個算法當(dāng)中，每個確定自動機的狀態(tài)對應(yīng)幾個非確定自動機的狀態(tài)。這個算法的思想是所有經(jīng)輸入一個符號和空轉(zhuǎn)移可達(dá)到的狀態(tài)歸一個確定自動機狀態(tài)。

從非確定自動機選擇狀態(tài)0和通過空符號可到達(dá)的所有狀態(tài)歸于為確定自動機的起始狀態(tài) A。把輸入詞綴按從A出發(fā)可到達(dá)的目標(biāo)狀態(tài)的不同進(jìn)行組合，這些組合能產(chǎn)生的不同的狀態(tài)集合歸于為新的狀態(tài)。

通過計算可得到確定自動機的新狀態(tài)集合SS，SS={A，B，C，D，E，F(xiàn)，G，H，J，O，K}。終止?fàn)顟B(tài)為E，起始狀態(tài)為 A。確定自動機的新狀態(tài)等于非確定自動機的幾個狀態(tài)。比如，D={1，2，3，4，12，13，20， 28}。

4 結(jié)論

形態(tài)分析在維吾爾語自然語言處理領(lǐng)域中的地位很重要，因為信息檢索系統(tǒng)、機器翻譯系統(tǒng)等都需要對單詞進(jìn)行形態(tài)分析與生成。維吾爾語詞干提取在研究與應(yīng)用領(lǐng)域的作用與中文分詞一樣。詞干提取算法的速度、準(zhǔn)確度都很重要，有限狀態(tài)自動機是規(guī)則的形式化工具，不具備歧義消除功能。

本文對形容詞的構(gòu)詞詞綴進(jìn)行了研究，在此基礎(chǔ)上構(gòu)造出了從右向左的非確定自動機。該自動機描述的是形容詞連接詞綴的情況，為得到能夠用于詞干提取的有限自動機，仍需要對該非確定自動機進(jìn)行翻轉(zhuǎn)操作和DFA轉(zhuǎn)換操作。本文較詳細(xì)地講解了以上所有步驟，本文的研究成果可以用于其它黏著語言的詞干提取算法研究和開發(fā)。

參考文獻(xiàn)：

[1] Tai S Y， Ong C S， Abdullah N A. On designing an automated Malaysian stemmer for the Malay language(poster)[C]//In Proceedings of the fifth international workshop on information retrieval with Asian languages， Hong Kong， 2000: 207-208.

[2] Greengrass M， Robertson A M， Robyn S， et al. Processing morphological variants in searches of Latin text[N]. Information research news， 1996，6(4):2-5.

[3] Berlian V， Vega S N， Bressan S. Indexing the Indonesian web: Language identification and miscellaneous issues[C]//Presented at Tenth International World Wide Web Conference， Hong Kong， 2001.

[4] Carlberger J， Dalianis H， Hassel M， et al. Improving precision in information retrieval for Swedish using stemming[C]//In Proceedings of NODALIDA '01-13th Nordic conference on computational linguistics， Uppsala，Sweden， 2001.

[5] Monz C. de Rijke M. Shallow morphological analysis in monolingual information retrieval for German and Italian[C]//In Cross-language information retrieval and evaluation: Proceedings of the CLEF 2001 workshop， C. Peters， Ed.: Springer Verlag， 2001.

[6] Eryigit G，Adali E.An affix stripping morphological analyzer for Turkish[C]//Proceedings of the Lasted International Conference on Artificial Intelligence and Application，Austria，2004.

[7] M.F.Porter.Snowball:A Language for Stemming Algortihms[EB/OL]. http://www.snowball.tartarus.org/texts/introduction.html.

[8] 哈密提·鐵木爾.現(xiàn)代維吾爾語語法[M].北京：民族出版社，1987.

[9] Aho A V， Sethi R， Ullman J D. 編譯原理技術(shù)與工具[M]. 北京:人民郵電出版社，2002:113-121.

[10] 力提甫·托乎提. 電腦處理維吾爾語語音和諧律的可能性[J].中央民族大學(xué)學(xué)報，2004，(5):108-113.

[11] 阿依克孜·卡德爾， 開沙爾·卡德爾， 吐爾根·依布拉音. 面向自然語言信息處理的維吾爾語名詞形態(tài)分析研究[J].中文信息學(xué)報，2006，(3):43-48.