維吾爾語(yǔ)形容詞構(gòu)形詞綴有限狀態(tài)自動(dòng)機(jī)

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

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

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在圖1中，給每個(gè)狀態(tài)編了個(gè)號(hào)碼，在以后的幾個(gè)步驟中這些狀態(tài)用這些編號(hào)表示。終止?fàn)顟B(tài)用0編號(hào)，起始狀態(tài)的編號(hào)為1。符號(hào)“ε”表示空邊。當(dāng)用這個(gè)自動(dòng)機(jī)分析單詞■ (從稍微瘦一點(diǎn))，首先找到詞干■ (瘦)，然后對(duì)其剩下部分進(jìn)行切分分析，從候選路徑中找到比較級(jí)詞綴■后把當(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)過(guò)ε到達(dá)狀態(tài)0。

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

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

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

3.3 NFA轉(zhuǎn)換成DFA

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

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

通過(guò)計(jì)算可得到確定自動(dòng)機(jī)的新?tīng)顟B(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。確定自動(dòng)機(jī)的新?tīng)顟B(tài)等于非確定自動(dòng)機(jī)的幾個(gè)狀態(tài)。比如，D={1，2，3，4，12，13，20， 28}。

4 結(jié)論

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

本文對(duì)形容詞的構(gòu)詞詞綴進(jìn)行了研究，在此基礎(chǔ)上構(gòu)造出了從右向左的非確定自動(dòng)機(jī)。該自動(dòng)機(jī)描述的是形容詞連接詞綴的情況，為得到能夠用于詞干提取的有限自動(dòng)機(jī)，仍需要對(duì)該非確定自動(dòng)機(jī)進(jìn)行翻轉(zhuǎn)操作和DFA轉(zhuǎn)換操作。本文較詳細(xì)地講解了以上所有步驟，本文的研究成果可以用于其它黏著語(yǔ)言的詞干提取算法研究和開(kāi)發(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)代維吾爾語(yǔ)語(yǔ)法[M].北京：民族出版社，1987.

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

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

[11] 阿依克孜·卡德?tīng)枺?開(kāi)沙爾·卡德?tīng)枺?吐?tīng)柛ひ啦祭? 面向自然語(yǔ)言信息處理的維吾爾語(yǔ)名詞形態(tài)分析研究[J].中文信息學(xué)報(bào)，2006，(3):43-48.