藏文排序优先级算法研究

2015-04-25边巴旺堆董志诚王龙业

中文信息学报 2015年1期

关键词：藏文音节排序

边巴旺堆,卓嘎, 董志诚,武强,王龙业

(西藏大学工学院,西藏拉萨 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