維吾爾語形容詞構形詞綴有限狀態自動機

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

關鍵詞：維吾爾語；黏著語；構形詞綴；有限自動機；語音和諧；詞干提取

中圖分類號：TP391文獻標識碼：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 引言

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

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

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

2 維吾爾語形容詞與形態

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

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

1）原級：沒有形態變化的形容詞的原體形式。原級是構成其他級的基礎形式。如：■“高尚”、■“偉大”、 ■“干凈”、 ■“美麗”等等。

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

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

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

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

3 維吾爾語形容構形詞綴優先自動機的構造

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

有限自動機的基本思想是它由有限狀態集合和具有一定屬性的弧組成，各狀態用有向弧線連接。每個弧線都有自己的方向和輸入符號串。這些狀態和有向弧線結合構成一個網絡，既有限狀態自動機[9]。

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

3.1 構造從右向左的非確定自動機

詞綴按照一定規則進行互相連接。首先，收集了所有連接規則，然后在這個規則庫的基礎上構造了從右向左的有限狀態自動機。 這個FSM所描述從詞干派生單詞變形的過程。

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

3.2 給詞綴編號和翻轉從右向左的有限狀態自動機

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

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

3.3 NFA轉換成DFA

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

從非確定自動機選擇狀態0和通過空符號可到達的所有狀態歸于為確定自動機的起始狀態 A。把輸入詞綴按從A出發可到達的目標狀態的不同進行組合，這些組合能產生的不同的狀態集合歸于為新的狀態。

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

4 結論

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

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

參考文獻：

[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] 哈密提·鐵木爾.現代維吾爾語語法[M].北京：民族出版社，1987.

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

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

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