邊巴旺堆,卓 嘎, 董志誠,武 強,王龍業(yè)

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

?

藏文排序優(yōu)先級算法研究

邊巴旺堆,卓 嘎, 董志誠,武 強,王龍業(yè)

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

規(guī)則函數(shù);優(yōu)先級;藏文;算法

1 前言

藏文排序與中文排序、英文排序不同，它是以藏文音節(jié)中的基本輔音字符(以下簡稱基字)在國際編碼標(biāo)準(zhǔn)中的順序為排序的基本順序，結(jié)合藏文構(gòu)詞規(guī)則、文法規(guī)則和各種優(yōu)先級一起作用于排序?qū)ο笊闲纬傻呐判蛞?guī)則。這種規(guī)則不以音節(jié)中出現(xiàn)的字符順序為排序依據(jù)，而是以基字為核心依據(jù)，結(jié)合各種規(guī)則的排序算法。

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

以上各位學(xué)者對藏文排序提出了各自的排序算法，但是有些排序算法并不能滿足現(xiàn)實需求。本文力求通過研究藏文構(gòu)詞規(guī)則和詞典的排序規(guī)則，制定規(guī)則函數(shù)和排序優(yōu)先級規(guī)則來設(shè)計優(yōu)先級算法，實現(xiàn)藏文詞語的排序優(yōu)先級算法。

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

圖1 藏文音節(jié)結(jié)構(gòu)

圖2 藏文構(gòu)件及其書寫順序

在文獻(xiàn)[7]中，實現(xiàn)了從藏文音節(jié)中識別其構(gòu)件元素的算法，通過該算法我們就可以得到了所有構(gòu)件的具體內(nèi)容，而本論文在文獻(xiàn)[7]的基礎(chǔ)上，對藏文構(gòu)件的優(yōu)先級和音節(jié)的優(yōu)先級進(jìn)行闡述。

1 規(guī)則函數(shù)

雖然構(gòu)造藏文音節(jié)的構(gòu)件只有7種，而且構(gòu)件之間采用排列與組合方式實現(xiàn)藏文音節(jié)的，但是這種組合方式需要遵守藏文的語法規(guī)則。

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

表示5種前加字允許做對應(yīng)基字的前綴；

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

表示3個上加字允許做對應(yīng)基字的上置輔音；

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

表示3個下加字允許做對應(yīng)基字的下置輔音。

(4) 根據(jù)標(biāo)識符的語法規(guī)則，設(shè)函數(shù)b(i)為標(biāo)識符的規(guī)則函數(shù)，則有

(5) 根據(jù)藏文語法規(guī)范和解決段字現(xiàn)象的基本方法，設(shè)藏文縮寫置換規(guī)則函數(shù)T(i)，則有

2 優(yōu)先級規(guī)則

想要解決藏文排序問題，就必須解決藏文構(gòu)件的優(yōu)先級問題，只要解決了優(yōu)先級，就能較好的處理藏文排序的正確性和有效性。因此首先確定各個構(gòu)件內(nèi)部元素的優(yōu)先級順序。辦法是根據(jù)國際編碼標(biāo)準(zhǔn)，對所有構(gòu)件的每一個元素進(jìn)行逐一確定其優(yōu)先級。

注以上定義中的φ為空值，即沒有數(shù)據(jù)；

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

以上6個定義是藏文構(gòu)件的字符優(yōu)先級，它們在藏文排序過程中將起到至關(guān)重要的作用。

3 優(yōu)先級算法

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

根據(jù)定義7，設(shè)計如下的算法。

算法1： 識別現(xiàn)代藏文音節(jié)算法

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

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

ELSE IF繼續(xù)；

輸出： 現(xiàn)代藏文音節(jié)；

定義8 現(xiàn)代藏文音節(jié)的排序優(yōu)先級規(guī)則是廣義笛卡爾集J×S×Q×X×Y×H的各元素周而復(fù)始的執(zhí)行以下步驟的結(jié)果。

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

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

為了準(zhǔn)確的確定帶有前加字音節(jié)的優(yōu)先級，現(xiàn)定義其優(yōu)先級準(zhǔn)則如下。

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

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

(6) 有上加字。即表達(dá)式為J1S1∑(Q×X×Y×H)時，除了J1S1Q0X0Y0H0元素的優(yōu)先級最高外，在S1不變的前提下，先后執(zhí)行步驟(2)、(3)、(4)和(5)確定攜帶H的音節(jié)、攜帶Y的音節(jié)、攜帶Y和H的音節(jié)、攜帶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的音節(jié)，然后把S1變?yōu)镾2，執(zhí)行上述過程，直至將所有攜帶S元素的優(yōu)先級全部確定完為止。轉(zhuǎn)到(7)；

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

說明： 凡是下角標(biāo)為0時，表示在該音節(jié)中沒有該類構(gòu)件。

根據(jù)定義8，設(shè)計如下算法，實現(xiàn)實現(xiàn)藏文音節(jié)的優(yōu)先級順序。

算法2： 現(xiàn)代藏文音節(jié)的優(yōu)先級順序

輸入： 現(xiàn)代藏文

循環(huán)

過程1IFS0Q0X0Y0H0THEN優(yōu)先級為1ELESIF繼續(xù)；

過程2IFS0Q0X0Y0∑HiTHEN優(yōu)先級為2，ELESIF繼續(xù)；

輸出： 音節(jié)的優(yōu)先級順序；

其算法流程如圖3所示。

圖3 優(yōu)先級算法流程圖

算法1和算法2，可以實現(xiàn)藏文音節(jié)的優(yōu)先級順序，并且應(yīng)用在藏文排序算法的實現(xiàn)上。

由于藏文詞語的排序不僅考慮第一個音節(jié)的排序優(yōu)先級，而且當(dāng)?shù)谝粋€音節(jié)相同時，按照第二個音節(jié)的優(yōu)先級才能準(zhǔn)確的確定該詞語的排序優(yōu)先級，同理，當(dāng)?shù)诙€音節(jié)相同時、當(dāng)?shù)谌齻€音節(jié)相同時……，因此，需要循環(huán)使用算法1和2給出組成藏文詞語的所有音節(jié)的優(yōu)先級，在此優(yōu)先級的基礎(chǔ)上，確定排序算法，才能得到符合藏文詞典規(guī)則的排序結(jié)果。

4 測試算法

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

表1 相同基字的優(yōu)先級種類統(tǒng)計表

注： 表中的Null是表示組成該音節(jié)沒有該類構(gòu)件。

表2 測試結(jié)果

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

表3 東嘎大詞典的測試結(jié)果

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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

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

[10] 邊巴旺堆. 基于ISO/IEC10646藏文編碼字符集標(biāo)準(zhǔn)的藏文排序算法設(shè)計與實現(xiàn). 西藏大學(xué)工學(xué)院碩士學(xué)位論文.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

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

TP391

A