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

邊巴旺堆,卓 嘎, 董志誠(chéng),武 強(qiáng),王龍業(yè)

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

?

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

邊巴旺堆,卓 嘎, 董志誠(chéng),武 強(qiáng),王龍業(yè)

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

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

1 前言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以上6個(gè)定義是藏文構(gòu)件的字符優(yōu)先級(jí)，它們?cè)诓匚呐判蜻^(guò)程中將起到至關(guān)重要的作用。

3 優(yōu)先級(jí)算法

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

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

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

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

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

ELSE IF繼續(xù)；

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

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

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

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

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

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

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

(6) 有上加字。即表達(dá)式為J1S1∑(Q×X×Y×H)時(shí)，除了J1S1Q0X0Y0H0元素的優(yōu)先級(jí)最高外，在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í)行上述過(guò)程，直至將所有攜帶S元素的優(yōu)先級(jí)全部確定完為止。轉(zhuǎn)到(7)；

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

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

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

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

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

循環(huán)

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

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

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

其算法流程如圖3所示。

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

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

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

4 測(cè)試算法

根據(jù)算法1和2，在同一個(gè)基字中最多有32種級(jí)別的優(yōu)先級(jí)順序，如表1所示。表中的每一個(gè)級(jí)別都有構(gòu)件元素的不同就會(huì)有不同的級(jí)別。例如，表1的第二種優(yōu)先級(jí)級(jí)別中，因?yàn)榇蠛蠹幼值牟煌?，就形成了?jí)別內(nèi)部的19種二層級(jí)別。再例如，第四種優(yōu)先級(jí)級(jí)別中，因?yàn)樵艉痛蠛蠹幼值慕M合方法不同，會(huì)就有級(jí)別內(nèi)部的二層級(jí)別19×5=95種。由此可見(jiàn)，構(gòu)成音節(jié)的構(gòu)件數(shù)量越多，二層優(yōu)先級(jí)的種類就越多。

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

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

表2 測(cè)試結(jié)果

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

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

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

[10] 邊巴旺堆. 基于ISO/IEC10646藏文編碼字符集標(biāo)準(zhǔn)的藏文排序算法設(shè)計(jì)與實(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

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

TP391

A