第4章無(wú)損數(shù)據(jù)壓縮

4.1仙農(nóng)-范諾與霍夫曼編碼4.2算術(shù)編碼4.3RLE編碼4.4詞典編碼第4章無(wú)損數(shù)據(jù)壓縮數(shù)據(jù)壓縮可分成兩種類型，一種叫做無(wú)損壓縮，另一種叫做有損壓縮。

無(wú)損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)完全相同

有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)有所不同本章主要介紹目前用得最多和技術(shù)最成熟的無(wú)損壓縮編碼技術(shù)。

第4章無(wú)損數(shù)據(jù)壓縮在數(shù)據(jù)壓縮技術(shù)中,編碼技術(shù)可分成三種類型:

熵編碼：不考慮數(shù)據(jù)源的無(wú)損數(shù)據(jù)壓縮技術(shù),它把數(shù)據(jù)都看作“符號(hào)”，其核心思想是按照符號(hào)出現(xiàn)的概率大小給符號(hào)分配長(zhǎng)度合適的代碼。概率大的代碼長(zhǎng)度長(zhǎng)，概率小的代碼長(zhǎng)度短。

源編碼：編碼時(shí)考慮數(shù)據(jù)信號(hào)源的特性和信號(hào)的內(nèi)容。通常為有損編碼技術(shù)。混合編碼：組合源編碼和熵編碼的數(shù)據(jù)有損壓縮技術(shù)。2.1數(shù)據(jù)冗余一、冗余的概念數(shù)據(jù)能被壓縮的依據(jù)是數(shù)據(jù)本身存在冗余。冗余有：人為冗余視聽(tīng)冗余數(shù)據(jù)冗余2.1數(shù)據(jù)冗余二、決策量在有限數(shù)目的互斥事件集合中，決策量是事件數(shù)的對(duì)數(shù)值，即

H0=log(n)對(duì)數(shù)的底數(shù)決定決策量的單位，sh(2)、Nat(e)、Hart(10)。2.1數(shù)據(jù)冗余三、信息量信息量是具有確定概率事件的信息的定量度量，定義為：

I(x)=log2(1/p(x))=-log2p(x)對(duì)一個(gè)等概率事件的集合，每個(gè)事件的信息量等于該集合的決策量。四、熵按照仙農(nóng)(Shannon)的理論，信源S的熵定義為

其中pi是符號(hào)si在S中出現(xiàn)的概率；log(1/pi)表示包含在si中的信息量，H(s)為事件的信息量的平均值，也稱為事件的平均信息量。2.1數(shù)據(jù)冗余五、數(shù)據(jù)冗余量數(shù)據(jù)的冗余量(R)定義為決策量(H0)超過(guò)熵的量，即為：

R=H0-H(S)2.1數(shù)據(jù)冗余4.1仙農(nóng)-范諾與霍夫曼編碼

[例4.1]有一幅40個(gè)像素組成的灰度圖像，灰度共有5級(jí)，分別用符號(hào)A、B、C、D和E表示,各符號(hào)在圖像中出現(xiàn)的數(shù)目見(jiàn)下表符 號(hào)

ABCDE出現(xiàn)的次數(shù)

157765如果用3個(gè)比特表示5個(gè)等級(jí)的灰度值，也就是每個(gè)像素用3比特表示，編碼這幅圖像總共需要120比特。

一、仙農(nóng)-范諾編碼4.1仙農(nóng)-范諾與霍夫曼編碼按照仙農(nóng)理論，這幅圖像的熵為

H(S)=(15/40)

log2(40/15)+(7/40)

log2(40/7)+

+(5/40)

log2(40/5)=2.196

即每個(gè)符號(hào)用2.196比特表示，40個(gè)像素需用87.84比特。

4.1仙農(nóng)-范諾與霍夫曼編碼仙農(nóng)-范諾(Shannon-Fano)算法采用從上到下的方法進(jìn)行編碼。首先按照符號(hào)出現(xiàn)的頻度或概率排序，例如A，B，C，D和E。然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù)，如圖所示。按照這種方法進(jìn)行編碼得到的總比特?cái)?shù)為91，實(shí)際的壓縮比約為1.3:1。A:2位X15B:2位X7C:2位X7D:3位X6E:3位X54.1仙農(nóng)-范諾與霍夫曼編碼二、霍夫曼編碼

霍夫曼(Huffman)則采用從下到上的編碼方法，仍以剛才的例子說(shuō)明它的編碼步驟：

①初始化，根據(jù)符號(hào)概率的大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序4.1仙農(nóng)-范諾與霍夫曼編碼②把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)，如P1。

③重復(fù)步驟2，得到節(jié)點(diǎn)P2、P3和P4，形成一棵“樹(shù)”。④從根節(jié)點(diǎn)P4開(kāi)始到相應(yīng)于每個(gè)符號(hào)的“樹(shù)葉”，從上到下標(biāo)上“0”(上枝)或者“1”(下枝)

。⑤從根節(jié)點(diǎn)P4開(kāi)始順著樹(shù)枝到每個(gè)葉子分別寫(xiě)出每個(gè)符號(hào)的代碼。

P1P2P3P40101100101001011101114.1仙農(nóng)-范諾與霍夫曼編碼

⑥按照仙農(nóng)理論，這幅圖像的熵為

H(S)=(15/39)

log2(39/15)+(7/39)

log2(39/7)+

+(5/39)

log2(39/5)=2.1859

壓縮比1.37:1

Huffman編碼需要各種代碼意義的“詞典”，即碼簿，那么就可以根據(jù)碼簿一個(gè)碼一個(gè)碼地依次進(jìn)行譯碼。4.1仙農(nóng)-范諾與霍夫曼編碼編碼原理——對(duì)出現(xiàn)頻率高的信源編碼長(zhǎng)度短，而對(duì)出現(xiàn)頻率低的信源編碼長(zhǎng)度長(zhǎng)。其編碼步驟如下：

[1]信號(hào)源的數(shù)據(jù)按照出現(xiàn)概率遞減的順序排列

[2]合并兩個(gè)最小出現(xiàn)概率，作為新數(shù)據(jù)出現(xiàn)概率

[3]重復(fù)進(jìn)行[1][2]，直至概率相加為1為止

[4]合并運(yùn)算時(shí)，概率大者取0，概率小者取1(或相反）

[5]記錄概率為1處到各信號(hào)源的0、1序列，則得到相應(yīng)的Huffman編碼。4.1仙農(nóng)-范諾與霍夫曼編碼

編碼特點(diǎn)

[1]編碼長(zhǎng)度可變，壓縮與解壓縮較慢

[2]硬件實(shí)現(xiàn)困難

[3]編碼效率取決于信號(hào)源的數(shù)據(jù)出現(xiàn)概率

[4]霍夫曼碼沒(méi)有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒(méi)有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。但如果碼串中有錯(cuò)誤，哪怕僅僅是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，更糟糕的是一錯(cuò)一大串，全亂了套，這種現(xiàn)象稱為錯(cuò)誤傳播(errorpropagation)4.2算術(shù)編碼

算術(shù)編碼把一個(gè)信源集合表示為實(shí)數(shù)線上的0到1之間的一個(gè)區(qū)間。這個(gè)集合中的每個(gè)元素都要用來(lái)縮短這個(gè)區(qū)間。信源集合的元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時(shí)，就需要一些更多的數(shù)位來(lái)表示這個(gè)區(qū)間，這就是區(qū)間作為代碼的原理。算術(shù)編碼首先假設(shè)一個(gè)信源的概率模型，然后用這些概率來(lái)縮小表示信源集的區(qū)間。消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)。

4.2算術(shù)編碼[例4.2]假設(shè)信源符號(hào)為{00,01,10,11}，這些符號(hào)的概率分別為{0.1,0.4,0.2,0.3}，根據(jù)這些概率可把間隔[0,1)分成4個(gè)子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)，其中表示半開(kāi)放間隔，即包含不包含。上面的信息可綜合在表中。符號(hào)00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)4.2算術(shù)編碼現(xiàn)對(duì)輸入的二進(jìn)制消息序列10001100101101進(jìn)行編碼。新子區(qū)間的起始位置＝ 前子區(qū)間的起始位置＋ 當(dāng)前符號(hào)的區(qū)間左端×前子區(qū)間長(zhǎng)度新子區(qū)間的長(zhǎng)度＝ 前子區(qū)間的長(zhǎng)度×

當(dāng)前符號(hào)的概率（等價(jià)于范圍長(zhǎng)度）算術(shù)編碼過(guò)程舉例

4.2算術(shù)編碼4.2算術(shù)編碼步驟間隔譯碼符號(hào)譯碼判決1[0.5,0.7)100.51439在間隔[0.5,0.7)2[0.5,0.52)000.51439在上一間隔的第1個(gè)1/10

3[0.514,0.52)110.51439在上一間隔的第7個(gè)1/104[0.514,0.5146)000.51439在上一間隔的第1個(gè)1/10

5[0.5143,0.51442)100.51439在上一間隔的第5個(gè)1/106[0.514384,0.51442)110.51439在上一間隔的第7個(gè)1/107[0.5143876,0.5144402)010.51439在上一間隔的第2個(gè)1/104.2算術(shù)編碼編碼過(guò)程：考慮一個(gè)有M個(gè)符號(hào)的字符表集ai=(1,2,…,M)，假設(shè)概率p(ai)=pi，而。輸入符號(hào)用xn

=ai表示，第n個(gè)子間隔的范圍用表示。其中l(wèi)0=0，d0=1和p0=0，ln表示間隔左邊界的值,rn表示間隔右邊界的值，dn=rn-ln表示間隔長(zhǎng)度。編碼步驟如下：4.2算術(shù)編碼步驟1：首先在1和0之間給每個(gè)符號(hào)分配一個(gè)初始子間隔，子間隔的長(zhǎng)度等于它的概率，初始子間隔的范圍用I1=[l1,r1)=[,)表示。令d1=r1-l1，L=l1和R=r1

。步驟2：L和R的二進(jìn)制表達(dá)式分別表示為： 和

其中uk和vk等于“1”或者“0”。4.2算術(shù)編碼比較u1和v1：①如果u1≠v1，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3；②如果u1=v1

，就發(fā)送二進(jìn)制符號(hào)u1。比較u2和v2：①如果u2≠v2

，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3；②如果u2=v2

，就發(fā)送二進(jìn)制符號(hào)u2。…這種比較一直進(jìn)行到兩個(gè)符號(hào)不相同為止，然后進(jìn)入步驟3，

4.2算術(shù)編碼步驟3：n加1，讀下一個(gè)符號(hào)。假設(shè)第n個(gè)輸入符號(hào)為xn=ai，按照以前的步驟把這個(gè)間隔分成如下所示的子間隔：

令dn=rn-ln，L=ln和R=rn

，然后轉(zhuǎn)到步驟2。4.2算術(shù)編碼發(fā)送1算術(shù)編碼概念

發(fā)送0發(fā)送011例：對(duì)序列a2,a1,a3編碼過(guò)程：4.2算術(shù)編碼接受的數(shù)字間隔譯碼輸出1[0.5,1)-0[0.5,0.75)0[0.5,0.625)1[0.5625,0.625)-1[0.59375,0.609375)………a2a1a3譯碼過(guò)程4.2算術(shù)編碼在算術(shù)編碼中需要注意的幾個(gè)問(wèn)題：

①由于實(shí)際的計(jì)算機(jī)的精度不可能無(wú)限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問(wèn)題，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此這個(gè)問(wèn)題可使用比例縮放方法解決。

②算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔[0,1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。

③算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。4.2算術(shù)編碼算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號(hào)的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改，在編碼期間估算信源符號(hào)概率的過(guò)程叫做建模。

現(xiàn)實(shí)中有許多這樣的圖像，在一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的像素都具有相同的顏色值。在這種情況下就不需要存儲(chǔ)每一個(gè)像素的顏色值，而僅僅存儲(chǔ)一個(gè)像素的顏色值，以及具有相同顏色的像素?cái)?shù)目就可以，或者存儲(chǔ)一個(gè)像素的顏色值，以及具有相同顏色值的行數(shù)。這種壓縮編碼稱為行程編碼(runlengthencoding，RLE)，具有相同顏色并且是連續(xù)的像素?cái)?shù)目稱為行程長(zhǎng)度。

4.3RLE編碼

例如對(duì)下面一行圖像數(shù)據(jù)：用RLE編碼方法得到的代碼為：80315084180。代碼中用黑體表示的數(shù)字是行程長(zhǎng)度，黑體字后面的數(shù)字代表像素的顏色值。

4.3RLE編碼4.3RLE編碼

RLE是一種無(wú)損壓縮技術(shù)。尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。然而，RLE對(duì)顏色豐富的自然圖像就顯得力不從心。4.4詞典編碼

一、詞典編碼的思想

詞典編碼(dictionaryencoding)的根據(jù)是數(shù)據(jù)本身包含有重復(fù)代碼這個(gè)特性。它可分為兩類：

4.4詞典編碼第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過(guò)，然后用已經(jīng)出現(xiàn)過(guò)的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過(guò)的字符串的“指針”。“詞典”是指用以前處理過(guò)的數(shù)據(jù)來(lái)表示編碼過(guò)程中遇到的重復(fù)部分。如LZ77和LZSS算法。

4.4詞典編碼第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語(yǔ)詞典(dictionaryofthephrases)”，短語(yǔ)可以是任意字符的組合。編碼數(shù)據(jù)過(guò)程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語(yǔ)”時(shí)，編碼器就輸出這個(gè)詞典中的短語(yǔ)的“索引號(hào)”，而不是短語(yǔ)本身。如LZW壓縮編碼。

4.4詞典編碼二、LZ77算法

算法中用到的幾個(gè)術(shù)語(yǔ)：

(1)輸入數(shù)據(jù)流(inputstream)：要被壓縮的字符序列。

(2)字符(character)：輸入數(shù)據(jù)流中的基本單元。

(3)編碼位置(codingposition)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開(kāi)始字符。

(4)前向緩沖存儲(chǔ)器(Lookaheadbuffer)：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。

4.4詞典編碼(5)窗口(window)：指包含W個(gè)字符的窗口，字符是從編碼位置開(kāi)始向后數(shù)也就是最后處理的字符數(shù)。

(6)指針(pointer)：指向窗口中的匹配串且含長(zhǎng)度的指針。

4.4詞典編碼LZ77編碼算法的核心是查找從前向緩沖存儲(chǔ)器開(kāi)始的最長(zhǎng)的匹配串。編碼算法的具體執(zhí)行步驟如下：(1)把編碼位置設(shè)置到輸入數(shù)據(jù)流的開(kāi)始位置。(2)查找窗口中最長(zhǎng)的匹配串。(3)以“(Pointer,Length)Characters”的格式輸出，其中Pointer是指向窗口中匹配串的指針，Length表示匹配字符的長(zhǎng)度，Characters是前向緩沖存儲(chǔ)器中的不匹配的第1個(gè)字符。(4)如果前向緩沖存儲(chǔ)器不是空的，則把編碼位置和窗口向前移(Length+1)個(gè)字符，然后返回到步驟2。4.4詞典編碼

位置123456789字符AABCBBABC步驟位置匹配串字符輸出11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)C4.4詞典編碼三、LZSS算法

LZSS算法的思想是如果匹配串的長(zhǎng)度比指針本身的長(zhǎng)度長(zhǎng)就輸出指針，否則就輸出真實(shí)字符。由于輸出的壓縮數(shù)據(jù)流中包含有指針和字符本身，為了區(qū)分它們就需要有額外的標(biāo)志位，即ID位。4.4詞典編碼LZSS編碼算法的具體執(zhí)行步驟如下：(1)把編碼位置置于輸入數(shù)據(jù)流的開(kāi)始位置。(2)在前向緩沖存儲(chǔ)器中查找與窗口中最長(zhǎng)的匹配串

①Pointer

：=匹配串指針。

②Length：=匹配串長(zhǎng)度。(3)判斷匹配串長(zhǎng)度Length是否大于等于最小匹配串長(zhǎng)度(Length

MIN_LENGTH)，

如果“是”：輸出指針，然后把編碼位置向前移動(dòng)Length個(gè)字符。

如果“否”：輸出前向緩沖存儲(chǔ)器中的第1個(gè)字符，然后把編碼位置向前移動(dòng)一個(gè)字符。(4)如果前向緩沖存儲(chǔ)器不是空的，就返回到步驟2。4.4詞典編碼步驟位置匹配串輸出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC位置123456789字符AABBCBBAABC10114.4詞典編碼四、LZ78算法

(1)字符流(Charstream)：要被編碼的數(shù)據(jù)序列。

(2)字符(Character)：字符流中的基本數(shù)據(jù)單元。

(3)前綴(Prefix)：在一個(gè)字符之前的字符序列。(4)綴?符串(String)：前綴＋字符。(5)碼字(Codeword)：碼字流中的基本數(shù)據(jù)單元，代表詞典中的一串字符。(6)碼字流(Codestream)：碼字和字符組成的序列，是編碼器的輸出。4.4詞典編碼(7)詞典(Dictionary)：綴-符串表。按照詞典中的索引號(hào)對(duì)每條綴?符串(String)指定一個(gè)碼字(Codeword)。

(8)當(dāng)前前綴(Currentprefix)：在編碼算法中使用，指當(dāng)前正在處理的前綴，用符號(hào)P表示。

(9)當(dāng)前字符(Currentcharacter)：在編碼算法中使用，指當(dāng)前前綴之后的字符，用符號(hào)C表示。(10)當(dāng)前碼字(Currentcodeword)：在譯碼算法中使用，指當(dāng)前處理的碼字，用W表示當(dāng)前碼字，String.W表示當(dāng)前碼字的綴?符串。4.4詞典編碼1、編碼算法

LZ78的編碼思想是不斷地從字符流中提取新的綴?符串(String)，通俗地理解為新“詞條”，然后用“代號(hào)”也就是碼字(Codeword)表示這個(gè)“詞條”。這樣一來(lái)，對(duì)字符流的編碼就變成了用碼字(Codeword)去替換字符流(Charstream)，生成碼字流(Codestream)，從而達(dá)到壓縮數(shù)據(jù)的目的。4.4詞典編碼步驟1：在開(kāi)始時(shí)，詞典和當(dāng)前前綴P都是空的。步驟2：當(dāng)前字符C：=字符流中的下一個(gè)字符。步驟3：判斷P+C是否在詞典中：

(1)如果“是”：用C擴(kuò)展P，讓P：=P+C；

(2)如果“否”：

①輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字和當(dāng)前字符C；

②把字符串P+C添加到詞典中。

③令P：=空值。

(3)判斷字符流中是否還有字符需要編碼

①如果“是”：返回到步驟2。

②如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。

2、譯碼算法

具體算法如下：步驟1：在開(kāi)始時(shí)詞典是空的。步驟2：當(dāng)前碼字W：=碼字流中的下一個(gè)碼字。步驟3：當(dāng)前字符C：=緊隨碼字之后的字符。步驟4：把當(dāng)前碼字的綴?符串(string.W)輸出到字符流(Charstream)，然后輸出字符C。步驟5：把string.W+C添加到詞典中。步驟6：判斷碼字流中是否還有碼字要譯

(1)如果“是”，就返回到步驟2。

(2)如果“否”，則結(jié)束。4.4詞典編碼4.4詞典編碼位置123456789字符ABBCBCABA步驟位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)4.4詞典編碼五、LZW算法

在LZW算法中使用的術(shù)語(yǔ)與LZ78使用的相同，僅增加了一個(gè)術(shù)語(yǔ)—前綴根(Root)，它是由單個(gè)字符串組成的綴?符串(String)。在編碼原理上，LZW與LZ78相比有如下差別：①開(kāi)始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。②每個(gè)編碼步驟開(kāi)始時(shí)都使用一字符前綴(one-characterprefix)，因此在詞典中搜索的第1個(gè)綴?符串有兩個(gè)字符。

4.4詞典編碼1、編碼算法碼字(Codeword)前綴(Prefix)1

……193A194B……255

……1305abcdefxyF01234……詞典

4.4詞典編碼LZW編碼算法步驟步驟1：開(kāi)始時(shí)的詞典包含所有可能的根(Root)，而當(dāng)前前綴P為字符流中的第一個(gè)字符；

步驟2：當(dāng)前字符(C)：=字符流中的下一個(gè)字符；

步驟3：判斷綴?符串P+C是否在詞典中

(1)如果“是”：P：=P+C //(用C擴(kuò)展P)；

(2)如果“否”

①把代表當(dāng)前前綴P的碼字輸出到碼字流;

②把綴?符串P+C添加到詞典;

③令P：=C//(現(xiàn)在的P僅包含一個(gè)字符C);

4.4詞典編碼步驟4：判斷字符流中是否還有字符要編碼

(1)如果“是”，就返回到步驟2；

(2)如果“否”

①把代表當(dāng)前前綴P的碼字輸出到碼字流;

②結(jié)束。

4.4詞典編碼2、譯碼算法

LZW譯碼算法中還用到另外兩個(gè)術(shù)語(yǔ)：①當(dāng)前碼字(Currentcodeword)：指當(dāng)前正在處理的碼字，用cW表示，用string.cW表示當(dāng)前綴?符串；②先前碼字(Previouscode