范道爾吉，白鳳山，武慧娟

(內(nèi)蒙古大學(xué) 電子信息工程學(xué)院，內(nèi)蒙古 呼和浩特 010021)

1 引言

蒙古文國際標(biāo)準(zhǔn)編碼字符集中收錄了傳統(tǒng)蒙文的7個元音、27個輔音、11個標(biāo)點符號、10個數(shù)字和4個控制字符。該標(biāo)準(zhǔn)中只按蒙古文語音收入了抽象的蒙古文字符(稱為名義字符)，而同一個蒙古文字符的書寫(顯現(xiàn)形式)會根據(jù)其在詞語中的位置不同、單詞的詞性等屬性不同而發(fā)生變化，即呈現(xiàn)在人們面前的是該字符變化后的形式(稱為顯現(xiàn)字形)。由于ISO/IEC 10646標(biāo)準(zhǔn)中沒有收人蒙古文顯現(xiàn)字符，因此在顯示蒙文時需要將蒙古文的名義字符根據(jù)上下文映射到其相應(yīng)的顯現(xiàn)字形[1-2]。

微軟的Vista操作系統(tǒng)當(dāng)中已經(jīng)支持了上述蒙古文的變換處理，Office2007也支持蒙古文的豎排排版。同時Vista中也提供了蒙古文輸入法，但是這個輸入法用起來不夠方便，文字輸入速度不夠快。不方便之處在于文字變形時候由用戶判斷使用哪一個控制符號，因此必須學(xué)習(xí)蒙古文的變形原理和控制符號功能，入門比較困難。其次蒙古文單詞都比較長，平均有10個左右(對一個蒙古文字典數(shù)據(jù)的統(tǒng)計)，因此輸入起來比較慢?；谏鲜鰡栴}本文提出了一種新型蒙古文輸入法算法。

2 新輸入法特點

新輸入法具備如下特點：自動變形、常用特殊文字快速輸入、聯(lián)想輸入、自動學(xué)習(xí)和網(wǎng)絡(luò)互聯(lián)。自動變形是指用戶只需按變形鍵文字就自動變形，用戶選擇正確變形就可以，而不用自己輸入控制符；常用特殊文字快速輸入是指蒙古文有些附加成分經(jīng)常用，但變形控制比較繁瑣，因此把特殊附加成分集中在某個鍵上，按附加成分鍵時常用的附加成分全部顯示，用戶選擇輸入就可以；聯(lián)想輸入是指一個較長的蒙古文字用戶輸入一部分時自動補(bǔ)齊顯示供用戶選擇輸入；自動學(xué)習(xí)是記錄用戶輸入到字典里，字典內(nèi)容動態(tài)增長；網(wǎng)路互聯(lián)是指字典數(shù)據(jù)通過網(wǎng)絡(luò)進(jìn)行更新和下載。

3 自動變形算法

3.1 算法原理

蒙古文Unicode定義了3個控制符：自由變體選擇符1(FVS1)、自由變體選擇符2(FVS2)、自由變體選擇符3(FVS3)。同時還有4個特殊符號影響蒙古文的變形分別是：窄寬度不間斷空格(MSP)、元音間隔符(MVS)、零寬度連接符(ZWJ)、零寬度禁止鏈接符(ZWNJ)。MSP輸入附加成分時使用； MVS在字末元音和輔音間不連續(xù)而且字形需要發(fā)生變化時使用；ZWJ是在輸入單個名義字符的各種變形時使用；ZWNJ需要強(qiáng)行斷詞時候使用[3]。

圖1 算法流程圖

自動變形算法基本思想：把鍵盤輸入轉(zhuǎn)換成蒙古文Unicode編碼串，然后按某種規(guī)則把控制符的排列組合加到當(dāng)前輸入串上，計算帶控制符Unicode串的字形ID串，再根據(jù)所得字形ID串篩選合理變形的Unicode文字串供用戶選擇輸入。算法的難點在于控制符的組合方案、添加位置以及篩選算法。

3.2 單個名義字處理算法

設(shè)當(dāng)前輸入是[A]，因為是單個名義字符，因此它的候選只能是這個名義字符相對應(yīng)的所有顯示字符了。[A]的前加控制符集合是{NONE，ZWJ}，而且前加控制符只能是一個。[A]后加控制符集合1是{NONE，F(xiàn)VS1，F(xiàn)SV2，F(xiàn)VS3，ZWJ}，后加控制符集合2是{NONE， ZWJ}。因為后加控制可以是FSVn和ZWJ的組合，后加控制符最多只能是兩個。表1是所有可能加的組合。

表1 單個名義字符變形控制排列組合

這樣可以共生成20個組合，但是其中有些組合式是非法的，比如ZWJ+ZWJ的連續(xù)出現(xiàn)，可以簡化成一個ZWJ。對這些簡化后的組合計算對應(yīng)的字形ID串，結(jié)果中可能有大部分字形ID串是形同的，因此需要對組合文字進(jìn)一步篩選。如果所得字形ID串和無控制符時對應(yīng)的字形ID串一致的全部刪除(因為控制符沒有起變形作用)，不同控制符組合得出相同字形ID串的保留控制符少的串，如果控制符數(shù)量也相同則保留其中任意一個(因為字形效果是一樣的，這種可能性比較少)。最后把保留下來的內(nèi)容顯示給用戶供選擇輸入。這樣對用戶就屏蔽了變形規(guī)則和控制符的使用方法。保留下來的應(yīng)該都是合法的蒙古文文字，因為他們滿足變形規(guī)則。MSP、MVS和ZWNJ沒有使用，因為他們對單個符號沒有變形作用。

3.3 多個名義字符處理算法

輸入多個名義字符時控制符加在倒數(shù)第二個字符后頭和最后一個字符后頭。如果倒數(shù)第二個符號是控制符則只加在最后一個字符后頭。比如輸入字符串是[A][B][C](B不是控制符)，[B]后頭可以加控制符集合是{NONE，F(xiàn)VS1，F(xiàn)VS2，F(xiàn)VS3，MVS}，[C]后可以加的控制符集合是{ NONE，F(xiàn)VS1，F(xiàn)VS2，F(xiàn)VS3}。ZWJ、MSP和ZWNJ沒有使用，因為ZWJ對一個文字串沒有變形作用，MSP的效果是有空格作用，但是文字看做是連續(xù)，因此把它分配在蒙古文模式下的空格鍵上，用戶可以直接輸入，ZWNJ的變形效果可以用空格(0x0020)鍵代替，空格(0x0020)可以分配在英文輸入模式下的空格鍵上。MSP也有輸入特殊變形附加成分的作用，但是本輸入中把特殊附加成分集中在TAB鍵上，按TAB時把已經(jīng)準(zhǔn)備好的特殊附加成分Unicode串(已經(jīng)帶了控制符比如MSP)列出來供用戶快速輸入。

自動變形算法在輸入一個文字時候可以多次使用，因為一個蒙古文字當(dāng)中可能需要多個控制符。比如當(dāng)前輸入是[A][B][C]發(fā)現(xiàn)[B]的形狀不正確，因此使用了一次自動變形選擇了正確的字形ID串，因此當(dāng)前輸入變成了[A][B+FVS1][C]，用戶接著輸入[A][B+FVS1][C][D][E]結(jié)果發(fā)現(xiàn)[D][E]都不是想要的字形，因此再運(yùn)行一次自動變形算法選擇正確的字形結(jié)果變成了[A][B+FVS1][C][D+MVS][E+FVS1]，每次的算法之間沒有關(guān)聯(lián)，相互獨立。

3.4 字形ID串的計算方法

Uniscribe即Unicode文字處理程序 (usp10.dll)，是用來對復(fù)雜文字進(jìn)行整形和布局的系統(tǒng)工具。目前Uniscribe支持蒙古文、維吾爾文等我國少數(shù)民族文字。對于復(fù)雜文本語言而言， 輸人的是Unicode名義字符串經(jīng)過布局引擎的處理后，輸出將是正確的顯現(xiàn)字型序列及字型間正確的位置數(shù)據(jù)[4-5]。

ScriptItemize函數(shù)完成Unicode名義字符串的分割工作，把統(tǒng)一屬性的文字分割成一個一個Items。ScriptShape函數(shù)完成Unicode名義字符串到字形ID串的轉(zhuǎn)換工作，可以利用這個函數(shù)獲得蒙古文的字形ID串。最后可以用ScriptPlace和ScriptTextOut函數(shù)完成字形的輸出[5]。下面是在Delphi7環(huán)境下實現(xiàn)字形ID串計算的部分代碼：

rslt ：= ScriptItemize(

pointer(wstr), //widestring類型的蒙古文字符串，我們自己添加控制符后的串

len,//wstr的長度

cMaxItems,//最大分割數(shù)量，如果wstr全是蒙古文，則1就夠了，為了安全可以給500

@psControl, //SCRIPT_CONTROL結(jié)構(gòu)體指針

@psState,// SCRIPT_STATE結(jié)構(gòu)體指針

@items[0], //TScriptItem數(shù)組的地址，這里返回分割后的串，為后續(xù)處理中用到

@cItems);//items中實際返回的個數(shù)

idx ：= items[0].iCharPos;//開始位置

lll ：= items[1].iCharPos - idx;//長度計算

mx_glyph ：= lll * 2 + 16;//字形ID的最大長度計算

glyph_cnt ：= 0;

//準(zhǔn)備緩存

setlength(clusts,mx_glyph);

setlength(glyphs,mx_glyph);//字形ID返回的緩存

setlength(sva,mx_glyph);

rslt ：= ScriptShape(

dc, //設(shè)備，使用mongolian baiti字體

@ssc, //TScriptCache指針，輸入nil，返回值在后續(xù)輸出時使用

@wstr[idx+1], //字符串開始指針

lll, //wstr中的長度

mx_glyph,//最大字形ID個數(shù)

@items[i].a, // ScriptItemize中得到的items

@glyphs[0], //存放字形ID串?dāng)?shù)組指針，字形ID在這里返回

@clusts[0],

@sva[0], // SCRIPT_VISATTR數(shù)組

@glyph_cnt);//實際得到的字形ID的個數(shù)

3.5 控制符組合有效性判斷

表2是$1820的所有控制符的自由組合和變形后的字形。

表2 編碼$1820對應(yīng)的所有變形和字形ID

清空有效組合集合A，A中按行記錄“控制符組合、字形ID(沒有空格)”

對所有得到的變形控制組合依次作如下處理：

(1) 字形ID串中的空格全部去掉(編碼3去掉)，只剩下蒙古文變形ID記做x；

(2) 判斷x是否在集合A中，如果已經(jīng)存在執(zhí)行(3)，否則執(zhí)行(4)；

(3) 和x對應(yīng)的控制符組合長度是否比A中已經(jīng)存在控制符組合短，如果短執(zhí)行(4)，否則執(zhí)行(5)；

(4) 把當(dāng)前處理串添加到A中；

(5) 還有未處理串跳轉(zhuǎn)(1)繼續(xù)，否則結(jié)束。

按上述算法處理后得到如表3所示表格。

表3 編碼$1820對應(yīng)的合理變形篩選結(jié)果

續(xù)表

表中得到就是0x1820的所有顯示字符，輸入法中可以把這些列出來供用戶選擇，因此用戶沒必要自己輸入控制符，因此方便了用戶輸入。多個名義字符時上述算法也是適用的，所得結(jié)果是當(dāng)前文字的所有合法變形文字。

4 字典數(shù)據(jù)的存儲和檢索算法

4.1 字典數(shù)據(jù)存儲方法

使用字典數(shù)據(jù)可以讓輸入法具備聯(lián)想功能，字典數(shù)據(jù)中存儲Unicode編碼串的蒙古文字。用戶輸入時實時檢索字典，如果字典中存在與當(dāng)前輸入匹配的字(可以使用模糊匹配，頭部包含的字就算匹配)，直接顯示在選擇區(qū)域中，在輸入比較長的文字就不必全部輸入就可以直接選擇了，省去了繁瑣的文字變形。

采用樹形結(jié)構(gòu)存儲蒙古文字典數(shù)據(jù)比較合理，這樣可以節(jié)省存儲空間，相同頭部的文字只需要存儲一份。樹的根節(jié)點沒有意義，其他節(jié)點由蒙古文名義字符的編碼和7個控制符構(gòu)成，樹形存儲結(jié)構(gòu)如圖2所示。

圖2 樹形結(jié)構(gòu)

樹中每個節(jié)點最多有41個子節(jié)點，從根開始到一個葉子節(jié)點是一個最長蒙古文字，但是到中間節(jié)點時也可以是一個蒙古文字。因此在每個節(jié)點上要用標(biāo)記記錄是否能構(gòu)字。

匹配算法：假設(shè)當(dāng)前如輸入是[A] [B] [C] [D]，當(dāng)前處理編碼記為x，x的初始值是[A]，樹中的當(dāng)前節(jié)點記為r，r的初始值是根節(jié)點。

(1) 查找r的子節(jié)點中有沒有和x匹配的節(jié)點，查找時可以使用簡單的下表對應(yīng)方法，如果找到匹配子節(jié)點繼續(xù)執(zhí)行(3)，否則執(zhí)行(2)。

(2) r的7個控制符子節(jié)點的子節(jié)點中有沒有和x匹配的節(jié)點，如果有執(zhí)行(3)，否則算法結(jié)束沒有找到匹配結(jié)果。

(3) r=匹配子節(jié)點，x是不是最后一個編碼，如果是算法結(jié)束，找到匹配串，從根節(jié)點到r，以及r以后的所有子節(jié)點都是匹配結(jié)果，否則x=下一個編碼，跳轉(zhuǎn)(1)

如果在(2)中有多個控制符子節(jié)點匹配的話，上述算法(1)、(2)、(3)需要遞歸執(zhí)行。

4.2 自動學(xué)習(xí)和字典共享技術(shù)

如果用戶輸入的完整文字在字典中找不到匹配串，可以動態(tài)加進(jìn)字典中。添加算法也可以使用查找算法，在判定不匹配時把開始不匹配部分添加到當(dāng)前樹結(jié)構(gòu)中，并保存到本地。同時可以使用網(wǎng)絡(luò)技術(shù)，架設(shè)一個網(wǎng)絡(luò)服務(wù)器，把用戶字典定時匯總，并把最新字典數(shù)據(jù)傳輸給每個用戶。

5 結(jié)束語

文中提出的新型蒙古文輸入法算法，經(jīng)試驗證實是可行有效的方法，可以大大提高蒙古文輸入速度和效率，用戶容易掌握和使用，對促進(jìn)蒙古文信息化處理有重要意義。同時本方案也非常適合在手持設(shè)備上使用，因為手持設(shè)備的資源有限，因此這種自動輸入算法更加適合。

[1] 確精扎布.蒙古文編碼[M].呼和浩特：內(nèi)蒙古大學(xué)出版社,2000.

[2] 姚延棟,吳健,孫玉芳,呼斯勒.傳統(tǒng)蒙古文變形顯示機(jī)制研究與實現(xiàn)[J].中文信息學(xué)報,2005,18(5)：84-89.

[3] S.蘇雅拉圖.傳蒙古文整詞編碼研究[J].中文信息學(xué)報, 2001,15(2)：57-64.

[4] 孟凡強(qiáng),吳健,賈彥民.蒙古文顯示在OpenOffice.Org辦公套件中的實現(xiàn)[J].中文信息學(xué)報,2007,21(2)：117-121.

[5] 周揚(yáng)榮,賈彥民.復(fù)雜文本布局引擎機(jī)制及應(yīng)用研究[J].中國科學(xué)院研究生院學(xué)報,2006,23(3)：390-395.

[6] 斯·勞格勞,敖其爾. Windows環(huán)境下蒙古文復(fù)雜文本處理的研究[J].內(nèi)蒙古大學(xué)學(xué)報,2007,38(5)：582-585.

[7] 烏達(dá)巴拉,鞏政.蒙古文OpenType字體制作技術(shù)[J].內(nèi)蒙古大學(xué)學(xué)報,2006,37(5)：570-573.