【正文】 亦即 AB、 BB、 AB、 A及 AB等文字?jǐn)?shù)據(jù)分別會(huì)先被編碼成 1 00及 10等十個(gè)比特，然后再存入內(nèi)存，其省下的儲(chǔ)存空間高達(dá) 86%。之后，如果一次以兩個(gè)比特的方式來讀取數(shù)據(jù)，然后通過同樣的字典進(jìn)行譯碼，則內(nèi)存所儲(chǔ)存的數(shù)據(jù) 1011100010很快地就會(huì)被解讀出原來的文字?jǐn)?shù)據(jù)為 ABBBABAAB。 第 4章 熵保持編碼 表 419 計(jì) 算 機(jī) 字 典 第 4章 熵保持編碼 通過上面的例子可以看到，與 Huffman碼正好形成鮮明對(duì)比的是： LZ碼及后來的改進(jìn)算法都是將變長的輸入符號(hào)串映射成定長 (或長度可預(yù)測 )的碼字。 LZ碼按照幾乎相等的出現(xiàn)概率編排輸入符號(hào)串，從而使頻繁出現(xiàn)的符號(hào)的串將比不常出現(xiàn)符號(hào)的串包含更多的符號(hào)。例如在一張將英文字母和符號(hào)串編碼成 12位碼字的壓縮字符串表中 (如表 420所示 )，不常用的字母如 Z，獨(dú)占一個(gè) 12位碼字；而常用的符號(hào)如空格 (表 420中用“空”表示 )和零，則以不同長度的長串表示(實(shí)用中字符串長度可大于 30)。如果輸入一個(gè)長串，就會(huì)被替換成一個(gè) 12位碼字，此時(shí)壓縮比自然很高。實(shí)際上，表 420也就是 LZ碼使用的字典，所以 LZ碼也是基于字典的壓縮編碼算法。 第 4章 熵保持編碼 表 420 一種 LZ編碼的字典 第 4章 熵保持編碼 LZW算法 由 1984年提出的 LZW算法，是 LZ系列碼中應(yīng)用最廣、變形最多的 LZ碼。 LZ碼系列算法的共同點(diǎn)是：分解輸入流，使其成為長度各異的“短語”，并把它們存入“短語字典”，并給每個(gè)“短語”賦予一個(gè)碼字 (通常就是短語的字典索引 )。只要短語的碼字長度小于短語的長度，就達(dá)到了壓縮的目的。 LZW編碼算法獨(dú)特的地方是先建立初始字典，再將輸入流分解為短語詞條，這個(gè)短語若不在初始字典內(nèi)，就將其存入字典，這些新詞條和初始字典共同構(gòu)成編碼器的字典。初始字典由信源符號(hào)集構(gòu)成，每個(gè)符號(hào)是一個(gè)詞條。比如在英文文本的壓縮中，可以將擴(kuò)展的 ASCII碼作為初始字典，使其成為字典的前 256項(xiàng)，這樣的初始字典足以應(yīng)付普通的英文文本壓縮。 第 4章 熵保持編碼 LZW算法將輸入字符串映射成定長 (通常為 12位 )的碼字。LZW碼表 (字典 )具有所謂的“前綴性” ——表中任何一個(gè)字符串的前綴字符串也在表中。這也就是說，如果由某個(gè)字符串 S和某個(gè)單字符 c所組成的字符串 Sc在表中，則 S也在表中，其中 c叫前綴串 S的擴(kuò)展字符。 對(duì)碼表作出這樣的說明后，編碼前可以將其初始化以包含所有的單字符。在壓縮過程中，碼表里面存放著編碼器在壓縮過程中已經(jīng)遇到的字符串，它動(dòng)態(tài)反映消息的統(tǒng)計(jì)特性。LZW使用的是“貪婪”分析算法，即依次檢查各個(gè)字符，直到碰到碼表中沒有的字符串或者掃描完全部字符。除初始化碼表外，其他碼表項(xiàng)也是通過這種方法加入進(jìn)碼表中的。LZW編碼算法流程如圖 49所示。 第 4章 熵保持編碼 圖 49 LZW編碼算法流程 第 4章 熵保持編碼 【 例 412】 試對(duì)一個(gè)最簡單的 2字符串“ ABBBABAAB”作 LZW編碼。 【 解 】 根據(jù)圖 49給出的 LZW編碼算法流程，可以得到如下的編碼步驟： 步驟 0：將 A及 B字符存入字典里，也就是 A及 B字符之后分別會(huì)被編碼成索引值 1及 2；并讀入第一字符 A，前綴串S=A。 步驟 1：讀入下一個(gè)字符 c=B，串 Sc=AB不在碼表中，輸出串 S=A在字典里的索引值 1；并將新的字符串 AB存入字典里，其索引值等于 3；最后置 S=B。 步驟 2：讀入下一個(gè)字符 c=B，串 Sc=BB不在碼表中，輸出串 S=B在字典里的索引值 2；并將新的字符串 BB存入字典里，其索引值等于 4；最后置 S=B。 第 4章 熵保持編碼 步驟 3：讀入下一個(gè)字符 c=B，串 Sc=BB已經(jīng)在碼表中，置 S=BB。 步驟 4：讀入下一個(gè)字符 c=A，串 Sc=BBA不在碼表中，輸出串 S=BB在字典里的索引值 4；并將新的字符串 BBA存入字典里，其索引值等于 5；最后置 S=A。 步驟 5：讀入下一個(gè)字符 c=B，串 Sc=AB已經(jīng)在碼表中，置 S=AB。 步驟 6：讀入下一個(gè)字符 c=A，串 Sc=ABA不在碼表中，輸出串 S=AB在字典里的索引值 3；并將新的字符串 ABA存入字典里，其索引值等于 6；最后置 S=A。 步驟 7：讀入下一個(gè)字符 c=A，串 Sc=AA不在碼表中，輸出串 S=A在字典里的索引值 1；并將新的字符串 AA存入字典里，其索引值等于 7；最后置 S=A。 第 4章 熵保持編碼 步驟 8：讀入下一個(gè)字符 c=B，串 Sc=AB已經(jīng)在碼表中，置 S=AB。 步驟 9：讀入下一個(gè)字符 c= f ，輸入已經(jīng)窮盡，輸出串S=AB在字典里的索引值 3，編碼結(jié)束。 該過程如表 421所示。 第 4章 熵保持編碼 表 421 字符串“ ABBBABAAB”的 LZW編碼過程 第 4章 熵保持編碼 LZW的解碼過程如下： 步驟 1：首先建立初始化碼表 (字典 )，它由信源的全部符號(hào)集構(gòu)成 (編碼器和解碼器的初始化碼表要完全一樣 )。 步驟 2：依序解碼接收到的碼字 (字典索引值 )，如果可以根據(jù)目前字典里的內(nèi)容進(jìn)行譯碼，則譯碼出相對(duì)應(yīng)的詞條I。同時(shí)將 Ic存入解碼字典中，此時(shí) c未知，它是下一個(gè)從字典中讀取的詞條的首個(gè)字符。再輸入下一個(gè)碼字，從字典取回詞條 J， J的首字符對(duì)應(yīng)上一步未知字符 c，此時(shí) Ic完全已知。 第 4章 熵保持編碼 步驟 3：假如目前碼字譯碼出的字符串為 S2(=cS3)，且上一個(gè)收到的碼字被譯碼成字符串 S1，則將新的字符串 (S1c)存入字典里，并對(duì)應(yīng)新的索引值。如果 S3未知，則譯碼出新的字符串為 S1c。 步驟 4：重復(fù)步驟 2和 3，則自動(dòng)重建了解碼表，并輸出原始信源序列。 第 4章 熵保持編碼 【 例 413】 試對(duì)上例進(jìn)行 LZW解碼，其接收碼字為 3。 【 解 】 根據(jù)上述的 LZW解的算法流程，可以得到如下的解碼步驟： 步驟 0：建立解碼器的初始化碼表 (字典 )。 步驟 1：讀入第 1個(gè)接收碼字 1，從字典中取出 I=A，將串 A輸出，并在解碼字典中添加新的項(xiàng) Ax，索引值為 3。 步驟 2：讀入第 2個(gè)接收碼字 2，從字典中取出 I=B，將串 B輸出，同時(shí)更新字典中的項(xiàng) Ax為 AB，并在字典中添加新的項(xiàng) Bx，索引值為 4。 第 4章 熵保持編碼 步驟 3：讀入第 3個(gè)接收碼字 4，從字典中取出 I=Bx，由于 x未知，上一步輸出字符串 S1=B， I的首字符為 B，輸出字符串 BB，更新字典中的項(xiàng) Bx為 BB，并在字典中添加新的項(xiàng)BBx，索引值為 5。 步驟 4：讀入第 4個(gè)接收碼字 3，從字典中取出 I=AB，將串 AB輸出，同時(shí)更新字典中的項(xiàng) BBx為 BBA，并在字典中添加新的項(xiàng) ABx，索引值為 6。 步驟 5：讀入第 5個(gè)接收碼字 1，從字典中取出 I=A，將串 A輸出，同時(shí)更新字典中的項(xiàng) ABx為 ABA，并在字典中添加新的項(xiàng) Ax，索引值為 7。 步驟 6：讀入第 6個(gè)接收碼字 3，從字典中取出 I=AB，將串 AB輸出，同時(shí)更新字典中的項(xiàng) Ax為 AA，解碼結(jié)束。 具體譯碼過程及結(jié)果如表 422所示。 第 4章 熵保持編碼 表 422 接收符號(hào)“ 1， 2， 4， 3， 1， 3”的 LZW解碼過程