趙洪鱗 林貴州 陳水欽 蔡僑燕

(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東東莞 523808)

隨著信息革命的發(fā)生，人們的生活發(fā)生了翻天覆地的變化，最近幾十年，信息在人們的生活中越來(lái)越重要，覆蓋面也越來(lái)越廣，而且越來(lái)越多的實(shí)物轉(zhuǎn)化為信息進(jìn)行跟蹤存儲(chǔ)，未來(lái)的世界必定是信息的時(shí)代。特別是信息化的概念提出之后，越來(lái)越多的國(guó)家和地區(qū)積極投入信息化的研究開(kāi)發(fā)，已經(jīng)有很多具有跨時(shí)代意義的產(chǎn)品產(chǎn)生。而中國(guó)要與世界接軌，漢字被世界接受是必不可少的，因此漢字編碼對(duì)中國(guó)來(lái)說(shuō)具有跨時(shí)代意義。

1 漢字處理流程

漢字處理流程粗略來(lái)講是指通過(guò)外界輸入交換操作，經(jīng)過(guò)內(nèi)部智能處理，把輸入要求輸出的信息進(jìn)行輸出。詳細(xì)來(lái)講是通過(guò)漢字輸入碼，把想要的信息輸入智能系統(tǒng)，漢字輸入碼通過(guò)漢字交換碼表，找出與輸入碼相對(duì)應(yīng)的漢字機(jī)內(nèi)碼，然后再根據(jù)漢字機(jī)內(nèi)碼，找出與機(jī)內(nèi)碼對(duì)應(yīng)的漢字點(diǎn)陣碼，把對(duì)應(yīng)的點(diǎn)字碼在屏幕進(jìn)行輸出或者在打印機(jī)上打印輸出或通過(guò)漢字字形控制碼調(diào)整打印各種風(fēng)格的字體或字形。其流程圖如圖1所示 (根據(jù)文獻(xiàn) ［1］改進(jìn)):

圖1 漢字處理流程圖

2 漢字編碼類型

在計(jì)算機(jī)標(biāo)準(zhǔn)鍵盤上，漢字的輸入和西文字符的輸入有很大的不同。西文輸入，擊一次鍵就能直接輸入相應(yīng)的字符或代碼，鍵入就是輸入。但是在計(jì)算機(jī)進(jìn)行漢字輸入時(shí)，鍵入是指在鍵盤上的操作，輸入是指把所需的漢字或符號(hào)送到指定位置，是鍵入的目的。不同的輸入法對(duì)應(yīng)不同的漢字輸入碼編碼，不同的漢字輸入碼操作不同，但是可以得到相同結(jié)果。其中漢字編碼主要分為漢字字音編碼、漢字字形編碼、漢字?jǐn)?shù)字編碼、音形混合碼等。

在世界范圍內(nèi)，不同編碼類型在編碼規(guī)則上有很大不同，目前國(guó)際上的通用碼是ASCII(美國(guó)信息交換標(biāo)準(zhǔn)編碼，美標(biāo))。而在漢字編碼中，具有代表性的主要是GB2312、BIG5碼與GBK。GB2312是簡(jiǎn)體中文字符集的中國(guó)國(guó)家標(biāo)準(zhǔn)，全稱為“信息交換用漢字編碼字符集—基本集”，幾乎所有的中文系統(tǒng)和國(guó)際化的軟件都支持GB2312，是國(guó)標(biāo)碼 (中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)交換用漢字編碼);BIG5碼是針對(duì)繁體漢字的編碼，在香港和臺(tái)灣的電腦系統(tǒng)中應(yīng)用的比較普遍;GBK全名為漢字內(nèi)碼擴(kuò)展規(guī)范，是對(duì)GB碼的擴(kuò)展字符編碼，對(duì)多達(dá)2萬(wàn)多字的簡(jiǎn)繁漢字進(jìn)行了編碼。GBK與GB2312編碼兼容，向下支持ISO10646.1國(guó)際標(biāo)準(zhǔn)，是前者向后者過(guò)度的啟程標(biāo)準(zhǔn)。

3 漢字編碼

漢字的編碼不是唯一的，主要有機(jī)內(nèi)碼與字型碼。漢字機(jī)內(nèi)碼是指計(jì)算機(jī)內(nèi)部存儲(chǔ)、處理加工和傳輸漢字時(shí)所用的由0和1符號(hào)組成的代碼。輸入碼被接受后就由漢字操作系統(tǒng)的“輸入碼轉(zhuǎn)換模塊”轉(zhuǎn)換為機(jī)內(nèi)碼，與所采用的鍵盤輸入法無(wú)關(guān)。機(jī)內(nèi)碼是漢字最基本的編碼，不管是什么漢字系統(tǒng)和漢字輸入方法，輸入的漢字外碼到機(jī)器內(nèi)部都要轉(zhuǎn)換成機(jī)內(nèi)碼，才能被存儲(chǔ)和進(jìn)行各種處理。

機(jī)內(nèi)碼與區(qū)位碼稍有區(qū)別。漢字區(qū)碼和位碼都在1－94之間，若直接用區(qū)位碼做機(jī)內(nèi)碼會(huì)與ASCII碼混淆。為了避免沖突，需要避開(kāi)基本ASCII碼中的控制碼 (00H－1FH)，還要與ASCII中的字符相區(qū)別。為了相區(qū)別這兩點(diǎn)，我們將漢字編碼加上2020H得到國(guó)標(biāo)碼，再由國(guó)標(biāo)碼加上8080H得到機(jī)內(nèi)碼。如圖2所示:

圖2 漢字編碼圖

漢字字型碼又稱字模，用于漢字在顯示屏或打印機(jī)輸出。漢字字型碼通常有點(diǎn)陣和矢量表示這兩種表示方式。用點(diǎn)陣表示字型時(shí)，漢字字型碼指的是這個(gè)漢字字型點(diǎn)陣的代碼。根據(jù)輸出漢字的要求不同，點(diǎn)陣的多少也不同。簡(jiǎn)易型漢字為16×16點(diǎn)陣，提高型漢字為24×24點(diǎn)陣，32×32點(diǎn)陣，48×48點(diǎn)陣等等。點(diǎn)陣規(guī)模愈大，字型愈清晰美觀，所占存儲(chǔ)空間也愈大。而矢量表示方式存儲(chǔ)的是描述漢字字型的輪廓特征，當(dāng)要輸出漢字時(shí)，通過(guò)計(jì)算機(jī)的計(jì)算，由漢字字型描述生成所需大小和形狀的漢字點(diǎn)陣。矢量化字型描述與最終文字顯示的大小，分辨率無(wú)關(guān)，因此可以產(chǎn)生高質(zhì)量的漢字輸出。Windows中使用的TrueType技術(shù)就是漢字的矢量表示方式。

漢字的顯示和輸出，普遍采用點(diǎn)陣方法。不同字形的漢字，就有不同的點(diǎn)陣字形。每個(gè)漢字的點(diǎn)陣都是由二進(jìn)制0和1組成的矩形方陣，0代表沒(méi)有，1代表有點(diǎn)，將0和1分別用不同顏色畫出，就形成一個(gè)漢字字形，構(gòu)成它在字庫(kù)中的字模信息。

16×16點(diǎn)陣的漢字其點(diǎn)陣有16行，每一行有16個(gè)點(diǎn)，這樣一個(gè)16×16點(diǎn)陣的漢字需要用2×16，即32個(gè)字節(jié)來(lái)存放。所以顯示一個(gè)漢字時(shí)，需要一次性讀取32個(gè)字節(jié)，并將每?jī)蓚€(gè)字節(jié)為一行打印出來(lái)，即可形成一個(gè)漢字。同理，24×24點(diǎn)陣和32×32點(diǎn)陣的漢字規(guī)則分別要用72個(gè)字節(jié)和128個(gè)字節(jié)存放一個(gè)漢字。

以“漢”字為例，對(duì)其進(jìn)行16X16點(diǎn)陣的編碼和顯示原理，如圖3所示:

圖3 16X16點(diǎn)陣的編碼和顯示原理

4 編碼分析

根據(jù)編碼原則，在保證編碼覆蓋范圍盡可能廣的同時(shí)，也要考慮編碼存儲(chǔ)容量和編碼傳輸速度。下面我們從信息論的角度分析編碼原則。

4.1 無(wú)錯(cuò)編碼碼率

設(shè)X為一信源字母集，U={0，1，…，D－1}為D進(jìn)碼字字母集，n，k為正整數(shù)，映射f:Xn→UK稱為等長(zhǎng)編碼，映射φ:UK→Xn稱為相應(yīng)的譯碼，對(duì)每個(gè)xn∈Xn，f(xn)=uk∈UK稱為碼字，碼字全體構(gòu)成的集合稱為由f編出的碼。R=k/n稱為f的編碼速率，簡(jiǎn)稱為碼率。R的單位是D進(jìn)碼字字母/信源字母，即平均每個(gè)信源符號(hào)用R個(gè)D進(jìn)數(shù)字表示如用二進(jìn)制單位，則R=k/n*log2D比特/信源字母。

因?yàn)橛成鋐:Xn→UK必須是一一映射， X=N(X表示集合X元素個(gè)數(shù))，所以 Uk≥Nn。所以R=k/n*log2D≥log2N。

采用等長(zhǎng)編碼容易識(shí)別編碼，但是如果信源中需要編碼的字符量過(guò)大，會(huì)占用過(guò)多的存儲(chǔ)空間。采用變長(zhǎng)編碼可以節(jié)省存儲(chǔ)空間，但是根據(jù)編碼區(qū)分信源字母上會(huì)增加難度。

例:以1，2，3，4為信源字母集，對(duì)其用等長(zhǎng)和變長(zhǎng)編碼，如圖4所示。

解:X =4，用二進(jìn)制編碼，碼率R=k/n*log2D≥log24=2。

圖4 二進(jìn)制等長(zhǎng)和變長(zhǎng)編碼

等長(zhǎng)編碼把譯碼從前往后一兩個(gè)為一組，很容易編譯出信源字母順序。例01001011，譯碼為2134。

變長(zhǎng)編碼針對(duì)相同的譯碼采用不同的順序可能會(huì)有不同的結(jié)果。例0111，可以譯為123，也可以譯為04。

針對(duì)漢字編碼，普遍采用的等長(zhǎng)編碼，如果能夠提出簡(jiǎn)易的譯碼函數(shù)，或者保證每一個(gè)碼字都不是其他碼的前綴，就可以采用變長(zhǎng)編碼，提高漢字編碼質(zhì)量。

4.2 唯一可譯碼

不同的漢字在使用中有不同的概率，漢字的數(shù)量又太龐大，很多字在現(xiàn)代生活已經(jīng)不使用。如果我們對(duì)出現(xiàn)概率比較大的字，盡可能采用短的代碼組表示，使用概率比較小的字采用長(zhǎng)編碼，即可提高編碼效率。牽涉到編碼字母概率的問(wèn)題，也就是信源熵的問(wèn)題。

信息具有不確定性，我們用熵來(lái)度量這種不確定性，熵也可以說(shuō)是每個(gè)信號(hào)的平均信息量。香濃提出的熵的公式為:

其中p(x)為信號(hào)x在X中出現(xiàn)的概率。熵也成為香濃熵，信源熵。從中可以看出，等概率分布時(shí)熵值最大，反應(yīng)的實(shí)質(zhì)是其包含了最少的信息量，其不確定量最大。

根據(jù)克萊夫特不等式，碼字字母取值與D進(jìn)制字母集的即時(shí)碼 (稱唯一可譯編碼f為即時(shí)編碼，如果f編出的碼字集中，沒(méi)有一個(gè)碼是其他碼的前綴，f編出的碼稱為即時(shí)碼)，其碼字長(zhǎng)分別為l1，l2，…，lm時(shí)必須滿足。我們可以證明碼長(zhǎng)l(x)=［log(1/p(x))］+1(取整)滿足克萊夫特不等式，因此可以構(gòu)造唯一可譯碼。該可譯碼平均碼長(zhǎng):

它比理論編碼最優(yōu)值——信源熵H(X)只多2個(gè)比特。

4.3 冗余度

根據(jù)文獻(xiàn) ［2］，用H(X，Y)表示聯(lián)合熵，它是隨機(jī)變量 (X，Y)的聯(lián)合分布為p(x，y)=p(X=x，Y=y)的熵:

用H(Y|X)表示隨機(jī)變量X條件下Y的熵，用p(y|x)=p(Y=y|X=x)表示條件概率分布:

稱H∞(X)為平穩(wěn)信源X的熵率，熵率的兩種等價(jià)形式:

1)H∞(X)=(1/n)*H(X1，X2，…，Xn);

2)H∞(X)=H(Xn|X1，X2，…，Xn－1);

冗余度表征了信源信息率的多于程度，是描述信源客觀統(tǒng)計(jì)特征的一個(gè)物理量。冗余度越大，則信息的效率就越低;反之效率越高。

由廣義Shannon不等式，有

對(duì)于記憶信源，最小單個(gè)消息熵應(yīng)為H∞(X)，即從理論上看，對(duì)于有記憶信源只需傳送H∞(X)即可，但是前提是必須要掌握全部概率統(tǒng)計(jì)特征。但是人們智能掌握有限的n階，這是至少需要傳送信息熵:

那么與理論值相比，就多傳送了Hn(X)－H∞(X)。因此可以用信源效率η，定量描述信源的有效性:

如在英文中，26個(gè)字母和空格的使用頻率如表1所示 (根據(jù)文 ［3］，以統(tǒng)計(jì)8 000字為例):

獨(dú)立等概率 (即每個(gè)字符相互獨(dú)立且出現(xiàn)的概率是1/27)的情況下，

獨(dú)立不等概率的情況下，

表1 字母和空格的使用頻率

如果有完整統(tǒng)計(jì)，可以統(tǒng)計(jì)出字母的相關(guān)性，得出條件概率，計(jì)算出條件熵，直至H∞(X)。

由于采用的逼近方法和所取的樣本不同，推算值也可能不同。根據(jù)Shannon的推斷值，我們?nèi)∞(X)為:

則可以計(jì)算出:

信源效率: η=H∞(X)/Hn(X)=0.29;

相對(duì)冗余度: r=1－H∞(X)/Hn(X)=0.71。

這就說(shuō)明，英文信源從理論上看有效成分只有71%，可以根據(jù)這一容量對(duì)其進(jìn)行壓縮編碼。

對(duì)于其他文字，也有不少人做了大量的統(tǒng)計(jì)工作，如表2［3］:

表2 各種文字的信源對(duì)比

從表中可以看出，中文的各層次上都比其他語(yǔ)言高出很多，這也說(shuō)明中文是最復(fù)雜的語(yǔ)言，也是最難學(xué)的語(yǔ)言。中文對(duì)信息傳達(dá)的效率不高，冗余度大，由此可以看出漢字還可以對(duì)其進(jìn)行改進(jìn)，進(jìn)行完善。特別是對(duì)其進(jìn)行信息化編碼，更有利于簡(jiǎn)明高效的傳達(dá)信息。

從碼率和熵的角度可知存在最優(yōu)編碼。隨著人們生活的改變，漢字熵也會(huì)改變。從漢字的冗余度進(jìn)行分析可知，漢字傳輸信息效率還可以改進(jìn)提高。從目前的形勢(shì)看我們還沒(méi)辦法做到最優(yōu)編碼，但是隨著理論的深化和技術(shù)的完善，一定可以找到更有效的編碼方案。

［1］盧永奇.信息編碼與漢字處理原理［J］.云南大學(xué)師范報(bào):自然科學(xué)版，2004，24(2):24－27.

［2］葉中行.信息論基礎(chǔ)［M］.北京:高等教育出版社，2003.

［3］熊輝.數(shù)學(xué)建模［M］.北京:中國(guó)人民大學(xué)出版社，2011:193－195.