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