藏文排序優先級算法研究

邊巴旺堆,卓 嘎, 董志誠,武 強,王龍業

(西藏大學 工學院,西藏 拉薩 850000)

?

藏文排序優先級算法研究

邊巴旺堆,卓 嘎, 董志誠,武 強,王龍業

(西藏大學 工學院,西藏 拉薩 850000)

規則函數;優先級;藏文;算法

1 前言

藏文排序與中文排序、英文排序不同，它是以藏文音節中的基本輔音字符(以下簡稱基字)在國際編碼標準中的順序為排序的基本順序，結合藏文構詞規則、文法規則和各種優先級一起作用于排序對象上形成的排序規則。這種規則不以音節中出現的字符順序為排序依據，而是以基字為核心依據，結合各種規則的排序算法。

到目前為止，許多藏文信息領域學者對藏文排序方面做了前瞻性的研究工作。文獻[1]對藏文排序提出了最初的設想及其實現方法，該文是藏文排序的開山鼻祖；文獻[2]中提出藏文的構造序和字符序概念, 并在此基礎上提出解決藏文詞典序的計算機方案；文獻[3]中分析了藏字字形、結構形態、傳統字符順序以及藏字字長和層高等特征, 構建出藏語排序的數學模型，然后依據模型要求為每類藏文符號進行數字賦值。本文的最大貢獻在于對藏文排序提出了數學模型，并提供了實現藏文排序的方案；文獻[4]中DUCET為每個藏文引入一個排序碼，將二維的藏文音節轉化成一維的字母串，從DUCET 中查出每個字母的排序碼,得到藏文音節對應的排序碼串，最后，通過比較排序碼串實現藏文音節間的排序。該文比較系統的闡述了藏文排序算法的實現；文獻[5]中闡述了藏文國家編碼標準情況下的藏文排序問題。由于藏文國家編碼標準中為藏文縱向疊加的部分給出獨立的編碼，所以實現排序算法相對簡單，但是這種排序與藏文詞典的排序出入比較大；文獻[6]中用空格符填補構件空缺的藏文音節，使待排序的藏文構件變為齊全，然后比較音節大小，實現了藏文排序，但是這種補充空缺位的方法在排序過程中不但沒有減輕系統的運算量，反而增加許多問題，影響大數據量的藏文詞語的排序速度。

以上各位學者對藏文排序提出了各自的排序算法，但是有些排序算法并不能滿足現實需求。本文力求通過研究藏文構詞規則和詞典的排序規則，制定規則函數和排序優先級規則來設計優先級算法，實現藏文詞語的排序優先級算法。

眾所周知，藏文是一種橫向線性結構，縱向疊加結構的拼音文字，是由42種基字和16種元音拼寫而成。無論藏文詞語有多少，它都是由7種構建元素拼寫而成。如圖1所示。它們的書寫順序如圖2所示，其中數字既表示藏文的書寫順序，又表示藏文的構件位置。每一種構件都有各自的元素。

圖1 藏文音節結構

圖2 藏文構件及其書寫順序

在文獻[7]中，實現了從藏文音節中識別其構件元素的算法，通過該算法我們就可以得到了所有構件的具體內容，而本論文在文獻[7]的基礎上，對藏文構件的優先級和音節的優先級進行闡述。

1 規則函數

雖然構造藏文音節的構件只有7種，而且構件之間采用排列與組合方式實現藏文音節的，但是這種組合方式需要遵守藏文的語法規則。

(1) 根據藏文前加字的語法規則，設函數q(i)為5個前加字做前綴的語法規則，則有

表示5種前加字允許做對應基字的前綴；

(2) 根據上加字的語法規則，設函數s(i)為3個上置輔音做上加字的語法規則，則有

表示3個上加字允許做對應基字的上置輔音；

(3) 根據下加字的語法規則，設函數x(i)為下置輔音做下加字的規則函數，則有

表示3個下加字允許做對應基字的下置輔音。

(4) 根據標識符的語法規則，設函數b(i)為標識符的規則函數，則有

(5) 根據藏文語法規范和解決段字現象的基本方法，設藏文縮寫置換規則函數T(i)，則有

2 優先級規則

想要解決藏文排序問題，就必須解決藏文構件的優先級問題，只要解決了優先級，就能較好的處理藏文排序的正確性和有效性。因此首先確定各個構件內部元素的優先級順序。辦法是根據國際編碼標準，對所有構件的每一個元素進行逐一確定其優先級。

注以上定義中的φ為空值，即沒有數據；

根據藏文各大辭典的排序規則得到，如圖2所示的構造位1、2、3、4、5都相同的情況下，構造位6和7在一定程度上是同步進行排序的 ，即后加字和后加字帶再后加字，兩者的優先級順序是后加字的先排，緊接著排該后加字帶再后加字的音節。所以，有必要將后加字和再后加字兩個構件合并為一個構件。同時，根據藏文辭典的排序規則得到，標識符的優先級高于后加字，也就是在相同條件下，帶標示符的音節排在帶后加字的音節前面。為了便于處理標識符、后加字和再后加字的優先級問題，同時根據藏文詞典的排序方法，可以將它們看做一個特殊的后加字，即后加字、再后加字和標識符一起合并為一個大后加字。

以上6個定義是藏文構件的字符優先級，它們在藏文排序過程中將起到至關重要的作用。

3 優先級算法

定義7 由于藏文的一個音節最多可以由7個(現在優化為6個，以下相同)構件組成，并且同一種構件在同一個音節中只能使用一次，則待排序藏文音節就是由集合J、Q、S、X、Y和H 6個中任選一個元素組成的一個元組。

根據定義7，設計如下的算法。

算法1： 識別現代藏文音節算法

輸入： 廣義笛卡爾J×S×Q×X×Y×H的各項元素；

IF在笛卡爾積J×S×Q×X×Y×H的各項元素中，是否滿足規則函數q(i)、s(i)、x(i)和b(i) THEN 輸出結果，

ELSE IF繼續；

輸出： 現代藏文音節；

定義8 現代藏文音節的排序優先級規則是廣義笛卡爾集J×S×Q×X×Y×H的各元素周而復始的執行以下步驟的結果。

(1) 元素J1S0Q0X0Y0H0的優先級最高，然后在J1不變的前提下，執行步驟(2)；

(5) 有前加字。即其數學模型為J1S0Q1∑(X×Y×H)時，根據藏文文字特點和藏文文法規則，此時，音節中除J和Q外，還必須至少包含一個其他構件，而包含的構件不同就有不同的優先級，不同的構件數量也就有不同的優先級順序。

為了準確的確定帶有前加字音節的優先級，現定義其優先級準則如下。

首先執行僅帶有后加字的優先級；其次執行帶有元音和后加字，此時以第一個元音字符為起始，執行后加字的優先級順序，再更換第二個元音，執行后加字的優先級順序，直至把所有帶元音和后加字的優先級全部確定完；最后執行帶有下加字、元音和后加字的優先級，此時以第一個下加字為起始，執行帶有元音和后加字的步驟，然后更換下一個下加字，直至把所有的下加字的優先級全部確定完為止。

實際上，在確定帶有前加字音節的優先級時，前加字保持不變的前提下，先后執行上述步驟(2)、(3)和(4)，然后更換前加字，繼續執行步驟(2)、(3)和(4)，直至把所有帶前加字的音節全部確定。這樣，就準確的確定了其優先級。轉到(6)；

(6) 有上加字。即表達式為J1S1∑(Q×X×Y×H)時，除了J1S1Q0X0Y0H0元素的優先級最高外，在S1不變的前提下，先后執行步驟(2)、(3)、(4)和(5)確定攜帶H的音節、攜帶Y的音節、攜帶Y和H的音節、攜帶X的、攜帶X和H的、攜帶X、Y和H的、攜帶Q和H的、攜帶Q和Y、攜帶Q、Y和H、攜帶Q和X的、攜帶Q、X和H的、攜帶Q、X和Y的、攜帶Q、X、Y和H的音節，然后把S1變為S2，執行上述過程，直至將所有攜帶S元素的優先級全部確定完為止。轉到(7)；

(7) 結束上述步驟，轉到步驟(1)，從J中選取下一個基字，并執行(2)。往復循環，直至將所有J的元素都按照定義8確定其優先級完為止。這樣，現代藏文所有音節的優先級就確定完成。

說明： 凡是下角標為0時，表示在該音節中沒有該類構件。

根據定義8，設計如下算法，實現實現藏文音節的優先級順序。

算法2： 現代藏文音節的優先級順序

輸入： 現代藏文

循環

過程1IFS0Q0X0Y0H0THEN優先級為1ELESIF繼續；

過程2IFS0Q0X0Y0∑HiTHEN優先級為2，ELESIF繼續；

輸出： 音節的優先級順序；

其算法流程如圖3所示。

圖3 優先級算法流程圖

算法1和算法2，可以實現藏文音節的優先級順序，并且應用在藏文排序算法的實現上。

由于藏文詞語的排序不僅考慮第一個音節的排序優先級，而且當第一個音節相同時，按照第二個音節的優先級才能準確的確定該詞語的排序優先級，同理，當第二個音節相同時、當第三個音節相同時……，因此，需要循環使用算法1和2給出組成藏文詞語的所有音節的優先級，在此優先級的基礎上，確定排序算法，才能得到符合藏文詞典規則的排序結果。

4 測試算法

根據算法1和2，在同一個基字中最多有32種級別的優先級順序，如表1所示。表中的每一個級別都有構件元素的不同就會有不同的級別。例如，表1的第二種優先級級別中，因為大后加字的不同，就形成了級別內部的19種二層級別。再例如，第四種優先級級別中，因為元音和大后加字的組合方法不同，會就有級別內部的二層級別19×5=95種。由此可見，構成音節的構件數量越多，二層優先級的種類就越多。

表1 相同基字的優先級種類統計表

注： 表中的Null是表示組成該音節沒有該類構件。

表2 測試結果

從東嘎詞典的目錄中任意選取2串詞語進行測試，得到表3所示的測試結果。從這兩個測試結果表明，確定藏文音節的優先級算法是正確的，算法符合實際藏文詞典的排序順序。

表3 東嘎大詞典的測試結果

注： 表中的目錄內容來自東嘎大詞典目錄的第31頁和第102頁。

5 結束語

本文研究了藏文詞語的構件、建立規則函數和構件內部元素的優先級，并對藏文詞典排序方法的研究，順利設計算法1和算法2。算法1是解決廣義笛卡爾積中抽取滿足藏文規則函數的詞語，限制該廣義笛卡爾積的元素，其目的是將從中抽取的每一個元素都能符合現代藏文的構詞規則，為算法2的設計奠定了基礎，而算法2就是對藏文詞語的構件進行優先級設置，通過對該算法進行測試表明，滿足藏文語法規則的前提下，該算法的優先級是正確的。只有藏文音節的優先級算法設計好了，才能較好的實現藏文排序的自動化。今后將對藏文排序中出現的梵音轉寫藏文詞語的排序規則進行研究。這是因為藏文中經常出現這類詞語，而這類詞語的構詞規則與現代詞語截然不同，并且這類詞語的排序優先級也與現代藏文不同，只有深入研究，才能解決梵音轉寫藏文詞語的排序規則及優先級算法了。

[1] 扎西次仁.藏文的排序規則及其計算機自動排序的實現[J].中國藏學研究.1999(04):128-135.

[2] 江荻，周季文.論藏文的序性及排序方法[J]. 中文信息學報,2000,14(1): 56-64.

[3] 江荻，康才. 書面藏語排序的數學模型及算法[J]. 計算機學報，2004，4：524-529.

[4] 黃鶴鳴 趙晨星. 基于DUCET的藏文排序方法[J].中文信息學報，2008，22(4):109-113.

[5] 珠杰，歐珠.基于藏文編碼GB的藏文排序方法研究[J]. 西藏大學學報(自然科學版). 2008(01)： 33-35.

[6] 劉萍，黃鶴鳴. 現代藏文音節排序的算法設計[J].西北師范大學自然學報.2012(06)： 44-47.

[7] 邊巴旺堆，卓嘎，陳延利，等. 藏文構件元素識別算法研究[J].中文信息學報,2014,28(3):26-33.

[8] 東嘎洛桑赤來.東嘎大辭典[M].北京： 中國藏學出版社，2002.

[9] 怡孫主編.藏漢大辭典[M].北京： 民族出版社.1984.

[10] 邊巴旺堆. 基于ISO/IEC10646藏文編碼字符集標準的藏文排序算法設計與實現. 西藏大學工學院碩士學位論文.2009.

Study on the Sorting Algorithm of Tibetan Dictionary

Bianba Wangdui， Drolkar， DONG Zhicheng， WU Qiang， WANG Longye

(School of engineering, Tibet University, Lhasa, Tibet 850000, China)

rule function; priority; Tibetan; algorithm

1003-0077(2015)01-0191-06

2014-01-26 定稿日期： 2014-05-26

國家自然科學基金(61163013)；國家自然科學基金(1261021)

TP391

A