孫 萌，華卻才讓，才智杰，姜文斌，呂雅娟，劉 群

(1. 中國科學(xué)院計算技術(shù)研究所 中國科學(xué)院智能信息處理重點實驗室,北京 100190; 2. 中國科學(xué)院大學(xué)，北京，100049; 3. 青海師范大學(xué) 藏文信息研究中心,青海 西寧 810008)

1 前言

藏文分詞是藏文信息處理的基礎(chǔ)。在藏文中，詞與詞之間缺乏間隔標記，和漢語類似都是字符或字的序列，因此藏文信息處理面臨和漢語同樣的問題，即如何將字符序列切分成合理的詞語序列。而現(xiàn)有的藏文分詞技術(shù)切分的準確率和實用性還有較大提升空間。這一方面是因為藏文編碼方案較多并且藏文研究起步較晚，另一方面更是由于藏文本身構(gòu)詞規(guī)律的復(fù)雜性。

研究者在藏文分詞方面提出了很多有效的算法，這些方案大體可以分為兩類。第一類是基于藏文特有的語言學(xué)知識的規(guī)則方法。陳玉忠[1-2]從藏文的字切分特征、詞切分特征和句切分特征三個方面深入研究藏文特有的語法接續(xù)規(guī)則，提出了基于格助詞和接續(xù)特征的藏文分詞方法。祈坤鈺[3]分別用格切分、邊界符判定和模式匹配算法實現(xiàn)對藏文的三級切分。才智杰[4-5]首先識別格助詞，然后將其作為分隔符對句子進行切分，采用最大匹配的算法依次對切分之后的塊分詞。孫媛[6]在格助詞分塊的基礎(chǔ)上，引入詞頻信息改進分詞質(zhì)量。劉匯丹[7]提出臨界詞識別方法和詞頻消歧方法有效地提高分詞正確率?；谝?guī)則的藏文分詞算法通常需要一個規(guī)模足夠大的詞典，采用最大匹配算法，即以在詞典中查到的最長的詞條作為句子的切分，算法實現(xiàn)簡單，效率較高。這種方法不能很好的處理切分歧義問題，另外對于未登錄詞的識別能力不強。第二類是基于統(tǒng)計的機器學(xué)習(xí)方法，用到的統(tǒng)計模型主要是隱馬爾科夫模型[8-9]，然而相對復(fù)雜的藏文構(gòu)詞現(xiàn)象，隱馬模型仍然略顯簡單。而其他統(tǒng)計模型的研究，如最大熵、感知機和條件隨機場等模型的應(yīng)用已經(jīng)成為漢語分詞的主流方向，目前此類模型應(yīng)用于藏文分詞的研究較少，一方面因為藏文分詞標注語料庫的規(guī)模限制，另一方面由于藏文不僅具有與漢語類似的字符順次拼接的構(gòu)詞方式，在時態(tài)上還具有曲折變化，是一種具有邏輯格語法體系的拼音文字。

在漢語分詞領(lǐng)域，Xue[10]提出了基于最大熵的漢語分詞方法，將分詞過程看作對每個字的分類，從而將分詞轉(zhuǎn)換成序列標注問題，即對每個字的判別式分類的過程。Collins[11]采用基于感知機的方法進行詞性標注，也獲得了較高的測試效果。采用基于字標注方法的優(yōu)勢在于： (1)可以融入任何特征以改善分詞效果；(2)識別未登錄詞的能力較強。在基于統(tǒng)計的藏文分詞領(lǐng)域，Liu[12]根據(jù)藏文構(gòu)詞特點，提出基于條件隨機場的藏文分詞，然而由于藏文構(gòu)詞規(guī)律的復(fù)雜性，在漢語上效果良好的序列標注模型不適合直接用于藏文分詞。因此本文提出一種基于格助詞規(guī)則與字符序列標注模型相結(jié)合的分詞模型，用以精確刻畫藏文的構(gòu)詞方式。

藏文的詞語通常由一個或者若干音節(jié)組成，但是在有些情況下，需要將一個音節(jié)切分，和此音節(jié)之前或者之后的音節(jié)組成詞語。本文深入討論了以藏文字丁、藏文字丁-音節(jié)點、音節(jié)作為序列標注的基本單位對分詞效果的影響?；谧謽俗⒎椒ǖ姆衷~算法通常采用局部特征，即字級別的特征。非局部特征，比如詞語級別的特征，也能顯著提高分詞效果，但是卻很難融入到現(xiàn)有的解碼算法中。Jiang[13]提出一種基于詞圖的重排序算法，融入非局部特征，分詞精確率得到較大提升。本文在基于詞圖的重排序方法上，提出了基于詞典懲罰的最短路徑算法，用以提高藏文分詞的性能。

2 藏文分詞框架

針對藏文分詞各個層面的處理對象以及問題特點，我們將原子切分、基于感知機解碼和構(gòu)建最短路徑這三個模型有機的融合在一個統(tǒng)一的框架下，如圖1所示。

圖1 藏文分詞框架

首先，根據(jù)藏文特有的構(gòu)詞規(guī)律將句子切分成最小粒度的序列，稱之為單元序列；隨后，根據(jù)感知機模型提供的判別式分類的權(quán)重，在單元序列上進行維特比解碼，從而生成有向圖，并通過查詢詞典為邊賦予不同的權(quán)重；最后，通過動態(tài)規(guī)劃算法求解加權(quán)有向圖中的最短路徑，生成最終分詞結(jié)果。

3 藏文最小構(gòu)詞粒度切分

一個或多個藏文字丁組成一個音節(jié)，一個或者多個音節(jié)組成詞，音節(jié)之間由音節(jié)點分隔。如圖2所示的藏文片段，其中文含義是“處在某一個級別”。

圖2 藏文片段

基于序列標注模型的漢語分詞過程可以視為在字層面上的組合，而藏文分詞的復(fù)雜性在于，不能在直接音節(jié)層面上進行組合，在有些情況下需要將某個音節(jié)拆分，和左邊或者右邊音節(jié)組合，或者獨立成詞。由于這種組合的靈活性，對于藏文的標注序列的最小構(gòu)詞粒度必須是小于音節(jié)的單位。本文設(shè)計三種構(gòu)詞粒度的方案以描述其構(gòu)詞規(guī)律，如圖3所示。

方案1： 藏文字丁。對句子按照每個字丁進行切分，如圖3中的切分a。

方案2： 藏文字丁-音節(jié)點。不將音節(jié)點單獨切分出來，而是將其與左邊字丁組合，如圖3中的切分b。

方案3： 音節(jié)。定義特殊格助詞表，先按照音節(jié)掃描切分句子，一旦音節(jié)中含有特殊格助詞則匹配相對應(yīng)的規(guī)則切分此音節(jié)，如圖3中c所示。

圖3 三種構(gòu)詞粒度切分方案舉例

選擇藏文的最小構(gòu)詞粒度的關(guān)鍵，在于將原始句子切分為分詞的原子序列。分詞的原子指的是分詞的最小處理單元，在分詞過程中，可以組合成詞，但內(nèi)部不能做進一步拆分。a方案沒有考慮任何構(gòu)詞規(guī)律，在分詞標注語料有限，藏文字丁構(gòu)詞規(guī)律較為復(fù)雜的情況下，統(tǒng)計模型缺乏足夠的知識進行標注學(xué)習(xí)；b方案在a方案的基礎(chǔ)上考慮音節(jié)規(guī)律，減小了分詞時的解碼搜索空間；而方案c則最大程度保存了音節(jié)的內(nèi)部結(jié)構(gòu)，卻又不會破壞構(gòu)詞粒度的原子性。本文實驗部分探討了在同樣規(guī)模標注語料庫下，采用以上不同的切分策略對最終分詞效果的影響。

4 基于感知機的藏文粗切分

對原子序列通過維特比算法進行序列標注，而序列標注的權(quán)重由感知機模型訓(xùn)練得到，其中感知機模型是判別式分類模型的一種。Collin[11]提出的基于感知機的序列標注方法是一種在線的學(xué)習(xí)方法。感知機模型的訓(xùn)練速度快，分類效果好。本文采用平均感知機算法[6]進行句子的粗切分，該算法記錄每一次權(quán)重的改變，以提高分詞系統(tǒng)的穩(wěn)定性，如算法1所示。

設(shè)輸入句子的原子序列xi∈X，輸出標注序列yi∈Y，X表示訓(xùn)練語料中的所有句子，Y表示對應(yīng)的標注，其中{b,m,e,s}是標注的符號集合。b表示詞的開始，m表示詞的內(nèi)部，e表示詞的結(jié)尾，s表示單獨成詞。

算法1 平均感知機算法

1: 輸入： 訓(xùn)練實例(xi,yi)

3: Fort← 1…T,i← 1…Ndo

為了盡可能的擬合數(shù)據(jù)，本文將Jiang[13]設(shè)計的特征模板的窗口擴展為4，如表1所示。

表1 特征模板

5 基于詞圖的重排序

對于基于感知機的分詞，除了通常使用的局部特征，非局部特征的引入也會提升分詞的性能。但是，非局部特征要在解碼的過程中動態(tài)的生成，很難直接將其加入到分類器中，并且引入非局部特征也會影響訓(xùn)練過程中對應(yīng)特征的調(diào)節(jié)。在自然語言處理的其他領(lǐng)域也面臨著類似的問題，一般的解決方案是使用重排序的方法引入非局部特征。然而，傳統(tǒng)方法是在n-best結(jié)果基礎(chǔ)上進行重排序，n-best所能表示的搜索空間較小，并且儲存冗余。感知機模型進行藏文粗切分的過程中保存分詞的候選，并將候選分詞結(jié)果壓縮為詞圖，最后采用基于詞圖的重排序算法尋找最合適的分詞結(jié)果。

本文針對藏文本身的特點，提出了基于最短路徑的詞典懲罰算法，快速從詞圖中選擇一條最優(yōu)路徑。

5.1 詞圖的生成與剪枝

可以將詞圖看作一個有向無環(huán)圖，如圖3所示。以構(gòu)詞單元之間的空隙作為圖的頂點，頂點之間的連線表示頂點之間的字符組合成詞。每條邊通過詞典獲得相應(yīng)的權(quán)重，在詞圖上尋找一條最短路徑，例如： <1,4>,<4,7>。

圖3 詞圖

按照詞圖頂點的拓撲順序，對每個節(jié)點保存以此節(jié)點為終點的所有邊，可以生成詞圖。例如，對于頂點3，保存邊<2,3>和<1,3>；對于頂點4，保存邊<1,4>、<2,4>和<3,4>。

如果保存解碼過程中的所有邊，則詞圖中會包含過多的無用路徑，在一定程度上會影響最短路徑的生成。本文通過限制每個節(jié)點的入度，只保存得分最高的n條邊，實現(xiàn)詞圖的簡單剪枝。由于詞圖結(jié)構(gòu)的特點，即使限制節(jié)點入度，同樣會包含很多路徑信息。

5.2 詞典懲罰策略

可能有如下三種切分：

5.3 基于詞圖的重排序算法

壓縮詞圖經(jīng)由詞典懲罰策略轉(zhuǎn)換為加權(quán)有向圖，所求的最終分詞結(jié)果就是從初始節(jié)點到結(jié)束節(jié)點的最短路徑?；趩卧从邢驘o環(huán)圖的最短路徑問題，可以采用Dijkstra貪心算法求解。 Dijkstra算法的時間復(fù)雜度為O(V2)，其中V表示圖中的頂點數(shù)，求解的是單源點到圖中所有點的最短路徑，而求解基于加權(quán)有向圖的最短路徑問題具有兩個不同之處： 首先有向邊的源點編號均小于終點編號，有向邊的方向具有一致性；其次，只需求解首尾兩點的最短路徑。因此，本文提出的最短路徑算法可以視為Dijkstra算法的簡化。算法從左到右依次計算每個節(jié)點與源點之間的最短路徑，時間復(fù)雜度為O(E)，其中E表示圖中的邊，對每個頂點，其每條入邊僅被檢測一次，所以算法實際總共迭代|E|次。

如算法2所示，v表示詞圖中的頂點，E表示頂點的連線，即邊。其中邊的權(quán)重是通過查詢詞典獲取，Path記錄最短路徑的信息，Path[v].previous表示以頂點v為終點的邊的起始頂點v′。 每個節(jié)點均存儲其上一個節(jié)點的信息，因此，在求解出最短路徑后，可以通過回溯算法快速生成最終的分詞結(jié)果。

算法2 生成最短路徑

1: 輸入： 詞圖L

2:Path← 0

3: Forv∈L.V按照拓撲順序 do

4: Forv′ 按照拓撲順序在v之前 do

5:E←

6: IfPath[v].score>Path[v′].score+E.weight

7:Path[v].score←Path[v′].score+E.weight

8:Path[v].previous←v′

9: 輸出： 最短路徑Path

6 實驗及分析

我們現(xiàn)有由青海師范大學(xué)提供的12 942條人工分詞的藏文句子，共110K詞語，語料的領(lǐng)域較為廣泛，從一定程度上能夠檢驗系統(tǒng)的魯棒性和可移植性。從中隨機選擇500句作為測試集，剩余的作為訓(xùn)練集。

為了研究構(gòu)詞粒度對于基于感知機的藏文分詞性能的影響，以基本字丁、基本字丁-音節(jié)點和音節(jié)為切分單位，本文設(shè)計3組實驗，實驗結(jié)果如表2所示。

表2 藏文分詞系統(tǒng)的性能

我們發(fā)現(xiàn)，構(gòu)詞粒度增大，分詞結(jié)果的性能也在提升，基于音節(jié)的感知機藏文分詞系統(tǒng)的F值比基于基本字丁的系統(tǒng)提高了3.3個百分點?？梢詫⒉匚姆衷~看作序列標注的過程，增大構(gòu)詞粒度，則序列變短，分類器決策的次數(shù)將減少，減少了搜索空間，準確率提高。

但是基于音節(jié)的感知機藏文分詞系統(tǒng)所達到的F值91.21%仍低于現(xiàn)有的基于規(guī)則的藏文分詞系統(tǒng)(基線系統(tǒng))的F值94.87%。我們將以上三組實驗看作是基于感知機模型的粗切分，分詞結(jié)果中往往會出現(xiàn)不成詞的切分。我們在基于音節(jié)的分詞系統(tǒng)上加入基于詞圖的重排序模塊，通過查詢詞典賦予每條邊不同的權(quán)重，從而搜索最短路徑。最終分詞的F值達到96.25%，比基于規(guī)則的分詞系統(tǒng)提高了1.38個百分點，比基于音節(jié)的分詞系統(tǒng)提高了5.04個百分點。

7 結(jié)論及未來工作

本文提出一種基于判別式模型的藏文分詞方法，并探究構(gòu)詞粒度的大小對分詞性能的影響，從而確定藏文分詞的基本切分粒度。然而，由于非局部特征不能直接用于感知機，我們采用基于詞圖的重排序算法引入非局部特征，并運用最短路徑算法產(chǎn)生最優(yōu)的分詞結(jié)果。

在基于統(tǒng)計的漢語分詞領(lǐng)域，最大熵和條件隨機場也獲得了較好的分詞效果， 未來我們將對比在同樣特征集合下，哪個模型更適于藏文分詞。另外，在重排序中我們僅考慮當(dāng)前詞的詞典特征，沒有考慮到當(dāng)前詞的上下文信息。下一步的工作將研究語言模型在重排序中的作用。

[1] 陳玉忠，李保利，俞士汶，等. 基于格助詞和接續(xù)特征的藏文自動分詞方案[J].語言文字應(yīng)用，2003(1):75-82.

[2] 陳玉忠，李保利，俞士汶. 藏文自動分詞系統(tǒng)的設(shè)計與實現(xiàn)[J].中文信息學(xué)報, 2003,17(03):15-20.

[3] 祁坤鈺.信息處理用藏文自動分詞研究[J]. 西北民族大學(xué)學(xué)報(哲學(xué)社會科學(xué)版), 2006,(4):92-97.

[4] 才智杰. 藏文自動分詞系統(tǒng)中緊縮詞的識別[J]. 中文信息學(xué)報, 2009,23(1):35-37.

[5] 才智杰. 班智達藏文自動分詞系統(tǒng)的設(shè)計與實現(xiàn)[J]. 青海師范大學(xué)民族師范學(xué)報，2010,21(2):75-77.

[6] 孫媛，羅桑強巴，楊銳，等.藏語交集型歧義字段切分方法研究[C]//第十二屆中國少數(shù)民族語言文字信息處理學(xué)術(shù)研討會論文集,2009.

[7] 劉匯丹，諾明花，趙維納，等. SegT： 一個實用的藏文分詞系統(tǒng)[J]. 中文信息學(xué)報, 2012, 26(1):97-103.

[8] 蘇俊峰，祁坤鈺，本太. 基于HMM 的藏語語料庫詞性自動標注研究[J]. 西北民族大學(xué)學(xué)報(自然科學(xué)版), 2009, 30(1): 42-45.

[9] 史曉東，盧亞軍. 央金藏文分詞系統(tǒng)[J]. 中文信息學(xué)報，2011,25(4):54-56.

[10] Nianwen Xue, Libin Shen. Chinese word segmentation as LMR tagging[C]//Proceedings of the 2nd SIGHAN Workshop on Chinese Language Processing, in conjunction with ACL’03, Sapporo, Japan, 2003: 176-179.

[11] Collins,Michael. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms[C]//Proceedings of the Empirical Methods in Natural Language processing Conference, Philadelphia, America, 2002: 1-8.

[12] Huidan Liu, Minghua Nuo, Longlong Ma, et al. Tibetan Word Segmentation as Syllable Tagging Using Conditional Random Fields[C]//Proceedings of the 25th Pacific Asia Conference on Language, Information and Computation, Singapore, 2011:168-177.

[13] Wenbin Jiang, Haitao Mi, QunLiu. Word lattice reranking for Chinese Word Segmentation and Part-of-Speech Tagging[C]//Proceedings of 22nd International Conference on Comtutational Linguistics, Manchester, UK, 2008:385-392.