倪耀群，曹 鵬，許洪波，唐慧豐，程學(xué)旗

（1.中國科學(xué)院 計算技術(shù)研究所，北京100190；2.中國科學(xué)院 研究生院，北京100049；3.解放軍外國語學(xué)院，河南 洛陽471003）

1 引言

1.1 維吾爾文和阿拉伯文、哈薩克文等文字共用很多字母

阿拉伯文是由28個輔音字母和12個發(fā)音符號（不包括疊音符）組成的拼音文字，世界上大約有60多個民族的文字是以阿拉伯字母為基礎(chǔ)來書寫的。為正確書寫和顯示這60多種文字中的專有字符，Unicode標(biāo)準(zhǔn)在阿拉伯基本字母集合（U＋600～U＋6FF）之外提供了阿拉伯語變形顯現(xiàn)形式－A（U＋FB50～U＋FDFB）和阿拉伯語變形顯現(xiàn)形式－B（U＋FE70～U＋FEFC）字符集。

中國新疆地區(qū)使用的維吾爾文、哈薩克文和柯爾克孜文都屬于這類文字，以阿拉伯字母為基礎(chǔ)書寫的維文稱為老維文，簡寫為ASU（Arabic－Script Uyghur），老維文有32個字母。而以阿拉伯字母為基礎(chǔ)的哈薩克文有33個字母，柯爾克孜文有30個字母和一個合體字母，這些文字共用了很多字母，編碼重疊較多，字符集差異很不明顯。例如，哈薩克文33個字母中有21個字母的字型形狀及編碼與維吾爾文完全相同［1］；波斯文有32個字母，其中28個是阿拉伯字母。下面列舉了幾種文字：

其中維文被谷歌瀏覽器chrome的“網(wǎng)頁檢測”識別為阿拉伯文；而谷歌翻譯的“檢測語言”功能，把維文識別當(dāng)作“普什圖語”（阿富汗的主要語言），如圖1所示。

圖1 谷歌翻譯誤將維文（《人民日報》記者深入災(zāi)區(qū)第一線采訪）檢測為“普什圖語”

如何將維吾爾文從阿拉伯文、哈薩克文、柯爾克孜文等以阿拉伯字母為基礎(chǔ)書寫的類似文字中識別出來，是維文信息處理的一個重要研究問題。

1.2 維吾爾文的書寫體系復(fù)雜

維吾爾文的書寫系統(tǒng)受其他語言的影響比較大，字符編碼存在一些混亂的情況。

維文32個字母因位置不同有126個書寫形體［2］（glyph），加上元音分節(jié)符hamza的各種變形等其他編碼后共使用了162個書寫形體［3］。然而ISO沒有為維文開辟專門的代碼區(qū)，而是把維文字符分配到阿拉伯基本字母集合、變形顯現(xiàn)形式－A和變形顯現(xiàn)形式－B這三塊不連續(xù)的區(qū)間。

對變形字母的編碼如何處理造成了編碼的混亂。（1）字母在單詞中不同位置發(fā)生了變形，應(yīng)該存儲為名義字母（Representative，32個），但有些網(wǎng)站上直接使用阿拉伯變形顯現(xiàn)形式的編碼來存儲該字母。如： 的編碼為“06CB”，其末尾形式為，也應(yīng)該存儲為“06CB”，但是有些網(wǎng)站存儲為變形顯現(xiàn)形式－A的編碼“FBDF”；（2）有些情況下元音字母之前應(yīng)該添加hamza，有人加了，有人不加；添加hamza之后可以變成一個復(fù)合字母（conjunct vowel form）［4］，也可以保持原來的兩個字母；（3）連寫字母和是否拆分為 和 也不盡相同。

另外由于維文網(wǎng)站的多元化導(dǎo)致維文網(wǎng)頁字體的編碼不一，同一個字母在不同網(wǎng)站中有多個編碼，如”的編碼有U＋649、U＋635和U＋6CC等。據(jù)統(tǒng)計，目前有264個網(wǎng)頁字體文件，如“Alp Basma Aq”、“UKIJ Tuz Tor”等。需要消除這些網(wǎng)頁文件造成的編碼差異，使用統(tǒng)一的編碼表示所有維文字符。

總結(jié)以上兩點，維吾爾文的識別有其困難性和特殊性，為解決維文的識別，作者使用基于字符層的語言模型來確定文本的語種。

本文的組織結(jié)構(gòu)如下：第2節(jié)介紹了語種識別的相關(guān)工作；第3節(jié)介紹了維吾爾文的識別模型，分為模型參數(shù)確定、模型訓(xùn)練和維文識別算法流程；第4節(jié)測試了模型在網(wǎng)頁、論壇和微博客等不同類型數(shù)據(jù)上的性能；第5節(jié)就微博客數(shù)據(jù)的測試結(jié)果進(jìn)一步分析，討論了4種文字中識別語種所需要的字符串長度，在理論分析基礎(chǔ)上對實際數(shù)據(jù)計算后得出了語種識別的文本長度最低界限，以及不滿足下限的超短文本能達(dá)到的最高語種識別準(zhǔn)確率。

2 語種識別的相關(guān)工作

語種識別實質(zhì)是分類問題，一般有規(guī)則方法和統(tǒng)計方法，規(guī)則方法需要人工總結(jié)出語言知識并將其轉(zhuǎn)換為系統(tǒng)規(guī)則，依賴于設(shè)計人員對語言本身的充分了解和分析，而且結(jié)果的正確性很難把握。

文獻(xiàn)［5］利用一元語法模型（unigram）進(jìn)行漢字內(nèi)碼識別的方法，可以高速、準(zhǔn)確地識別簡體漢字和繁體漢字，滿足實時處理等各種應(yīng)用。但單一的以字為基本單位的unigram方法過于簡單，沒有考慮阿拉伯字母等其他語言的情況。

文獻(xiàn)［6］采用編碼模式、字符分布和雙字符序列分布的復(fù)合方法來檢測語言／編碼，效果很好，在UTF16和UTF8的情況下，盡管編碼方式正確識別了，語言信息仍是未知的。檢測語言時需要每一種語言的，大量的文本采樣數(shù)據(jù)，同時需要對語言的認(rèn)知／分析有一定的深度，對許多單字節(jié)編碼還沒有測試。文獻(xiàn)［7］在8種編碼（utf－8、us－ascii、iso－8859－1、shift－jis、euc－jp、iso－2022－jp、euc－kr、iso－2022－kr）上測試了 Naive Bayes（NB）和Support Vector Machine（SVM）模型，認(rèn)為SVM需要較少的內(nèi)存就可以達(dá)到98.22%識別準(zhǔn)確率，但是檢測的編碼之間重疊程度不大，僅是英日韓文字的不同編碼。

規(guī)則方法有薛亞平［1］和張?。?］，他們根據(jù)GB2l6690－2008信息技術(shù)—維吾爾文、哈薩克文、柯爾克孜文編碼字符集國家標(biāo)準(zhǔn)，按照不同文種的字符編碼構(gòu)造正則表達(dá)式進(jìn)行匹配，從而識別文種。由于維文、哈文、柯文和阿文的非重疊區(qū)很小，這幾種文本的正確識別具有一定的難度，識別率還不是很高，需要結(jié)合人工輔助來正確識別。

3 維吾爾文的識別模型

考慮到維吾爾文和其他采用阿拉伯字母書寫的文字盡管在編碼上有很多重疊，但是字母排列順序不同，這是文字自身表現(xiàn)出的區(qū)別于其他文字的明顯特征。因此，作者提出了一種基于n－gram模型的維文語種識別方法。

3.1 n－gram模型中階數(shù)n的確定

在n－gram建模方法使用這樣的假設(shè)：語言是一個馬爾可夫過程，某個字母的出現(xiàn)僅僅與前面的n－1個字母相關(guān)，因此m個Unicode字符構(gòu)成的字符串s的概率可以表示為式（1）：

其中P（wi｜wi－n＋1wi－n＋2…wi－1）用大數(shù)定律估計，即 wchar類型的字符串 wi－n＋1wi－n＋2…wi－1wi在所有以 wi－n＋1wi－n＋2…wi－1開頭的字符串中所占的比率。

在n－gram模型中階數(shù)n的選擇存在著一個平衡，馮沖、黃河燕［9］認(rèn)為理想的識別模型應(yīng)當(dāng)既能夠描述訓(xùn)練樣本所獨有的語種和編碼特點，又不過分反映樣本中特定的文本內(nèi)容和語言現(xiàn)象。為了確定n－gram的階數(shù)，作者在4種語言的網(wǎng)頁正文中統(tǒng)計了 所 有 uni－gram，bigram，tri－gram，4－gram 和 5－gram，以及這些gram出現(xiàn)的次數(shù)。

以維文為例，bigram有1 132個，其中最頻繁的bigram出現(xiàn)了5 822 195次，有60個bigram出現(xiàn)次數(shù)超過一百萬次，大部分（751個）bigram出現(xiàn)次數(shù)在1 000次以上；對比tri－gram有17 854個，只有5個tri－gram出現(xiàn)次數(shù)超過一百萬次，10 025個trigram出現(xiàn)次數(shù)小于100次，數(shù)據(jù)稀疏現(xiàn)象比較明顯。對阿拉伯文的統(tǒng)計也驗證了這一點。

綜合考慮，因為tri－gram的統(tǒng)計意義不明顯，按照大數(shù)定律估計的概率由于數(shù)據(jù)稀疏不很準(zhǔn)確，而且會造成更大的系統(tǒng)開銷（約16 777 216個存儲單元），所以最終確定以bigram模型計算字符串概率：其中的P（w1）是字符串的開始字符，如果在每個字符串前面加上一個虛擬開始符號（概率為1），可以去掉該項，簡化計算。

3.2 Bigram模型的訓(xùn)練

P（bigram｜L）是語言L中bigram出現(xiàn)的概率，為表現(xiàn)統(tǒng)計意義，忽略那些頻率較低的bigram，如維文有7個bigram只出現(xiàn)一次，這些bigram代表了樣本中特殊的偶發(fā)的語言現(xiàn)象，對區(qū)分語種的作用微乎其微。維吾爾文和阿拉伯文的bigram頻次分布如圖2（見下頁）。

為充分表現(xiàn)語言在bigram上的共性并去除偶發(fā)現(xiàn)象的干擾，作者選用高頻bigram組成該語言的特征表，同時為防止圖2所示長尾效應(yīng)的影響，特征表中的bigram概率之和應(yīng)該大于一個閾值（作者選取0.9）。按照這個原則，作者在阿拉伯文中選取了400個bigram，在維文中選取了1 000個bigram。

作者根據(jù)阿拉伯文和維文字母編碼的特點，對維文變形顯現(xiàn)字符映射到基本阿拉伯字符，經(jīng)過映射后字符的UTF8編碼在D880～DBBF（U＋600～U＋6FF）范圍內(nèi)，進(jìn)一步對其壓縮，將這個256個編碼的區(qū)間映射到unsigned char（0～255），使得語言模型的存儲結(jié)構(gòu)（語言特征表）大大減小。

圖2 維吾爾文和阿拉伯文bigram特征頻次分布圖

3.3 對未知文本的語種識別

按照Bayes公式，字符串s屬于某種語言L的概率

其中P（s）為定值，而先驗概率P（L）可以根據(jù)訓(xùn)練文本中維文、阿拉伯文、哈薩克文等文章所占的比例計算出來。但是在測試新的未知文本時，難以預(yù)知該文本的來源，因此簡單認(rèn)為所有待檢測文本所屬的文種是等概率的，即P（L）為一個常數(shù)。

而后驗概率P（s｜L）的對數(shù)

count（bigram）為字符串s中某個bigram 出現(xiàn)的次數(shù)，但是P（bigram｜L）有可能為零，原因有二，一是訓(xùn)練文本中根本沒有出現(xiàn)該bigram，二是某些低頻的bigram沒有被該語言的bigram特征表收錄（如維文去除了132個bigram，保留了1 000個bigram）。這就需要進(jìn)行零概率的拉普拉斯校準(zhǔn)。

在概率空間（0，1）上對數(shù)函數(shù)是嚴(yán)格單調(diào)遞增的，即P（bigram｜L）與其對數(shù)值正相關(guān)，因此count（bigram）×P（bigram｜L）與count（bigram）×logP（bigram｜L）正相關(guān)。

最終使得字符串s出現(xiàn)概率最大的語言，就是s所屬的語言，定義為L＊：

只需要將待識別的網(wǎng)頁文本掃描一遍，統(tǒng)計count（bigram），然后按照式（5）計算該網(wǎng)頁文本屬于某種語言的概率。理論上，有多少個語種，就需要多少次相似度計算。作者的目的僅僅是識別維吾爾文，所以可以簡化計算，將識別文本看成二分類問題，即比較該文本屬于維文（正例）和非維文（負(fù)例）概率。非維文的計算本來需要將維文以外的其他所有語言的文本一起作為負(fù)例樣本，鑒于哈薩克文和柯爾克孜文的樣本非常少，作者簡單的把阿拉伯文當(dāng)作負(fù)例樣本。

維文訓(xùn)練網(wǎng)頁有6萬頁面（2008年采集的維文網(wǎng)頁和論壇，3GB）和6 560個阿拉伯文頁面（2008年采集的中國網(wǎng)阿拉伯文版，200MB）。

模型訓(xùn)練和網(wǎng)頁維文識別的流程如圖3所示（見下頁）。

4 維吾爾文識別結(jié)果及分析

現(xiàn)有的維吾爾文識別方法是基于表達(dá)式規(guī)則和人工輔助的［1，8］，且并沒有給出識別準(zhǔn)確率，與作者采用的統(tǒng)計方法缺乏可比性。因此，作者通過使用不同時間、不同來源的網(wǎng)頁數(shù)據(jù)（新聞和論壇），以及不同類型的網(wǎng)頁數(shù)據(jù)（微博客）來進(jìn)行實驗測試，驗證了該方法在不同數(shù)據(jù)上的良好性能和穩(wěn)定性。

4.1 對網(wǎng)頁和論壇的測試

測試環(huán)境：硬件環(huán)境：AMD 3600＋ CPU，2.5G內(nèi)存，80G硬盤

程序識別網(wǎng)頁的處理速度大約為100MB／s。對單個網(wǎng)頁（中文、阿拉伯文、哈薩克文、柯爾克孜文、維吾爾文）的判別結(jié)果如表1所示。

對不同時間、不同來源的多個網(wǎng)站的網(wǎng)頁分組測試結(jié)果如表2所示。

分析：

圖3 模型訓(xùn)練和維文識別流程圖

表1 五種語言的網(wǎng)頁文種判別結(jié)果

表2 四種語言網(wǎng)頁開放測試的正確率

2）對正文較長的新聞、論壇等網(wǎng)頁，維吾爾文的識別準(zhǔn)確率較高。

3）訓(xùn)練中使用的阿拉伯文和維吾爾文，在識別時也得到了非常高的準(zhǔn)確率。

4.2 對微博客的測試

微博客的特點是文本長度短，轉(zhuǎn)發(fā)造成的重復(fù)內(nèi)容多，而且轉(zhuǎn)發(fā)還造成同一文本內(nèi)包含了多種文字。因此對微博客需要去重后才能正確評價文本分類識別的準(zhǔn)確率。文獻(xiàn)［10］提到了一種通過文本壓縮將文本轉(zhuǎn)換為一個大整數(shù)從而去重的方法。

在2010年推特識別結(jié)果中隨機(jī)采樣了31條數(shù)據(jù)進(jìn)行人工判斷，發(fā)現(xiàn)有30條判斷正確（準(zhǔn)確率96.6%），1條來自伊朗的波斯文消息被判別為維吾爾文，該消息呈現(xiàn)如下形式：

Deutsche Welle RT＠User2Iran awaiting 40%inflation

http：／／bit.ly／6e1wPH ＃iranelection

容易看出，這條消息中包含德、英、波斯三種文字，其中波斯文的25個阿拉伯字符占消息字符總數(shù)的18.461 538%，其維文得分0.001 361比阿拉伯文得分0.001 283只高出了0.000 078。而且“伊朗”這個詞的波斯文拼寫“”與維文拼寫“”最后三個連續(xù)的字符都相同（），類似這樣的單詞片段導(dǎo)致程序的誤判。

5 語言識別問題中的文本長度下界分析

語言分類的文本長度下界其實就是求解若干字符串集合的公共字符串，作者將研究范圍限定在維吾爾文、阿拉伯文、哈薩克文和柯爾克孜文四種文字的字符串集合中。

對同種語言的每個網(wǎng)頁抽取正文后，用空格、標(biāo)點符號、數(shù)字、字母等作為分割標(biāo)記切分正文得到若干字符串，將它們放到一個集合中，形成一個語言詞串（token）集合。維吾爾文、阿拉伯文、哈薩克文和柯爾克孜文四種文字的字符串集合中分別含有251 928，82 559，21 972和14 521個字符串。這些字符串在長度上的分布如圖4所示。

最終目的是找出這四個集合的最大公共子串。

圖4 四種語言單詞／token按照字符串長度上的分布

5.1 兩個字符串集合的公共字符串

字符串集合 A＝｛A1，A2，A3…Am｝和B＝｛B1，B2，B3，…，Bn｝，假設(shè) A1，A2，A3，…，Am的平均長度為L1，B1，B2，B3，…，Bn的平均長度為L2，則：

A的子串個數(shù)上限為mC2L1，同理B的子串個數(shù)上限為nC2L2，通過字符串比較得到公共子串（common sub）的比較次數(shù)上限為mC2L1nC2L2，設(shè) m＝n＝10 000，L1＝L2＝10，比較次數(shù)大約為2 025億次。實際上m，n比10 000大很多（對維文來說20萬單詞是很保守的估計），使得兩個大集合之間的公共子串求解變得不可行。更遑論四個集合的公共子串的計算了。

我國傳統(tǒng)的抗旱工作模式是危機(jī)管理，即在旱情出現(xiàn)后才對干旱作出反應(yīng)，臨時組織動員廣大干部群眾，并拿出大量資金和物資投入抗旱減災(zāi)工作中。但隨著社會主義市場經(jīng)濟(jì)體系的不斷完善，傳統(tǒng)的危機(jī)管理模式在觀念、措施、手段和政策上呈現(xiàn)出一些不適應(yīng)的地方：一是重視“抗”,忽視“防”，難以做到以最小的投入取得最大的抗旱減災(zāi)效果；二是重視工程措施，忽視非工程措施，難以發(fā)揮工程設(shè)施的最大抗旱效益；三是重視行政手段，忽視經(jīng)濟(jì)、法律、科技手段，抗旱減災(zāi)能力缺陷明顯；四是重視經(jīng)濟(jì)效益，忽視生態(tài)效益，難以滿足和諧發(fā)展要求。

為此，對公共子串做出限制，要求公共子串必須真實存在于某個語言的字符串集合中。也就是說，公共子串必須是某種語言的合法單詞或其變形（token），稱這樣的單詞為合法公共字符串。

5.2 四種語言字符串集合的合法公共字符串

依照上述合法公共字符串的定義，可以在有限時間內(nèi)求得每個集合相對于其他三個集合的合法公共字符串。流程如下：

1）ABCD為四個字符串集合，S（A）為集合A中所有字符串的子串集合的并集，同理得到S（B）、S（C）和S（D），從上面的分析容易得出

｜S（A）｜＝10 000×10×9／2（大約為百萬數(shù)量級）

2）對集合A中的每個字符串Ai分別在集合S（B）、S（C）和S（D）中查找，如果在三個集合中全都查到，則Ai是一個合法公共字符串。

3）同樣的方法驗證集合B、C、D中的每個字符串是否為合法公共字符串。

4）所有合法公共字符串中長度最長的字符串就是四個集合的最長合法公共字符串，也就是語言分類的文本長度下界。

實驗環(huán)境：建立的四個語言的集合比較消耗內(nèi)存（大約2GB）和時間，在 windows7（64bit）4G內(nèi)存環(huán)境下經(jīng)過約20分鐘運行得到合法公共字符串（簡稱公共單詞）共1 112個，其長度分布和該長度對應(yīng)的識別準(zhǔn)確率如圖5所示（見下頁）。

圖5 不同字符串長度對應(yīng)的公共單詞個數(shù)及識別準(zhǔn)確率

作者給出文本語種判別長度下界為8（大于7個字符）。少于8個字符的字符串無法判斷語言類別，圖3給出的準(zhǔn)確率也是理論上的最高值。

應(yīng)該指出，這個數(shù)據(jù)基于作者研究的范圍統(tǒng)計得到，而網(wǎng)頁實際出現(xiàn)的詞串有可能未被統(tǒng)計，或者屬于其他未定義語言。實際識別準(zhǔn)確率可能更高（從兩種文字的正規(guī)文本集合中識別維文）或者更低（從更多種類文字的非正式文本中識別維文）。

6 總結(jié)與下一步工作

本文介紹了一種利用二元語法模型（bigram）進(jìn)行從維吾爾文、阿拉伯文、哈薩克文和柯爾克孜文網(wǎng)頁中識別維吾爾文的方法，針對維文的編碼混亂的各種情況進(jìn)行細(xì)致的預(yù)處理，能夠從類似阿拉伯文的網(wǎng)頁中高速、準(zhǔn)確的識別維文（網(wǎng)頁論壇的識別達(dá)到準(zhǔn)確率98.9%，微博客96.6%，速度約100MB／s）。對短文本的測試結(jié)果分析引入了文本識別長度下界的概念，作者對四種語言的公共字符串進(jìn)行了理論分析和統(tǒng)計計算，從而確定了四種文字中正確識別需要的文本長度下界為8個字符。

經(jīng)過對不同時期采集的開放數(shù)據(jù)（2008年和2011年的維吾爾文、阿拉伯文網(wǎng)頁、2010年的推特數(shù)據(jù)）的測試，表明該方法可以快速、準(zhǔn)確地處理維文網(wǎng)頁的識別問題，對于微博客等短文本在預(yù)處理（將消息按照字符集分解為幾個比較“純凈的”單語言網(wǎng)頁）之后再做語種識別，還能進(jìn)一步提高判斷精度。

由于采用阿拉伯字母書寫的語言比較多，在字符集上相互之間的交疊大而復(fù)雜，因此按照N元語法模型對更多的文字（如波斯文、普什圖文、烏爾都文……）訓(xùn)練更多的語言特征，是解決語種分類錯誤的一條有效途徑。

［1］薛亞平，袁保社.全文檢索系統(tǒng)中語種識別與索引技術(shù)研究［J］.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2009，（12）：49－51.

［2］哈力克·尼亞孜，吾買爾·阿皮孜.基礎(chǔ)維吾爾語［M］.新疆大學(xué)，1995：1－2.

［3］瓦熱斯江·阿布都克力木.維文Unicode在線處理技術(shù)與實現(xiàn)［D］.新疆大學(xué)碩士研究生學(xué)位論文，2002：17－18.

［4］Imad Saleh，Waris Abdukerim Janbaz.Web Development Considerations for Unicode－based Text Processing in Uyghur Language［C］／／Proceedings of the 30th Internationalization and Unicode Conference，November 2006，Washington，DC USA：15－17.

［5］李繼鋒，劉群.基于N－Gram模型的高速漢字編碼識別系統(tǒng)［J］.計算機(jī)工程與應(yīng)用，2004，（3）：39－42.

［6］Shanjian Li，Katsuhiko Momoi.A composite approach to language／encoding detection［OL］，http：／／www－archive.mozilla.org／projects／intl／UniversalCharsetDetection.html.

［7］Seungbeom Kim，Jongsoo Park.Automatic Detection of Character Encoding and Language［R］，CS 229，Machine Learning，Autumn 2007，Stanford University.

［8］張健，任煒，蔣欣，等.多語種eml文件編碼及語種識別算法研究［J］.新疆大學(xué)學(xué)報（自然科學(xué)版），2010，27（4）：482－485.

［9］馮沖，黃河燕，陳肇雄，等.基于字符層馬爾科夫模型的多語種識別［J］.計算機(jī)科學(xué)，2006，33（1）：226－235.

［10］曹鵬，李靜遠(yuǎn)，滿彤，等.Twitter中近似重復(fù)消息的判定方法研究［J］.中文信息學(xué)報，2011，25（1）：20－27.