lz78算法

LZ77 算法針對過去的數據進行處理，而 LZ78 算法卻是針對後來的數據進行處理。LZ78 通過對輸入快取數據進行預先掃描與它維護的字典中的數據進行匹配來實現這個功能，在找到字典中不能匹配的數據之前它掃描進所有的數據，這時它將輸出數據在字典中的位置、匹配的長度以及找不到匹配的數據，並且將結果數據添加到字典中。
儘管在最初得到流行，但是後來 LZ78 的普及逐漸衰減，這可能是由於在剛 LZ78 出現的一些年份，一部分 LZ78 算法獲得了美國專利保護。最流行的 LZ78 壓縮形式是 LZW 算法，這個算法是 Terry Welch 所開發的一個 LZ78 變體。
在算法中用到的幾個術語和符號：
(1) 字元流(Charstream)：要被編碼的數據序列。
(2) 字元(Character)：字元流中的基本數據單元。
(3) 前綴(Prefix)： 在一個字元之前的字元序列。
(4) 綴-符串(String)：前綴＋字元。
(5) 碼字(Code word)：碼字流中的基本數據單元，代表詞典中的一串字元。
(6) 碼字流(Codestream)： 碼字和字元組成的序列，是編碼器的輸出。
(7) 詞典(Dictionary)： 綴-符串表。按照詞典中的索引號對每條綴-符串(String)指定一個碼字(Code word)。
(8) 當前前綴(Current prefix)：在編碼算法中使用，指當前正在處理的前綴，用符號P表示。
(9) 當前字元(Current character)：在編碼算法中使用，指當前前綴之後的字元，用符號C表示。
(10) 當前碼字(Current code word)： 在解碼算法中使用，指當前處理的碼字，用W表示當前碼字，String.W表示當前碼字的綴-符串。
　1. 編碼算法
LZ78的編碼思想是不斷地從字元流中提取新的綴-符串(String)，通俗地理解為新“詞條”，然後用“代號”也就是碼字(Code word)表示這個“詞條”。這樣一來，對字元流的編碼就變成了用碼字(Code word)去替換字元流(Charstream)，生成碼字流(Codestream)，從而達到壓縮數據的目的。
在編碼開始時詞典是空的，不包含任何綴-符串(string)。在這種情況下編碼器就輸出一個表示空字元串的特殊碼字(例如“0”)和字元流中 (Charstream)的第一個字元C，並把這個字元C添加到詞典中作為一個由一個字元組成的綴-符串(string)。在編碼過程中，如果出現類似的 情況，也照此辦理。在詞典中已經包含某些綴-符串(String)之後，如果“當前前綴P +當前字元C”已經在詞典中，就用字元C來擴展這個前綴，這樣的擴展操作一直重複到獲得一個在詞典中沒有的綴-符串(String)為止。此時就輸出表示 當前前綴P的碼字(Code word)和字元C，並把P+C添加到詞典中作為前綴(Prefix)，然後開始處理字元流(Charstream)中的下一個前綴。
LZ78編碼器的輸出是碼字-字元(W,C)對，每次輸出一對到碼字流中，與碼字W相對應的綴-符串(String)用字元C進行擴展生成新的綴-符串(String)，然後添加到詞典中。LZ78編碼的具體算法如下：
步驟1： 在開始時，詞典和當前前綴P都是空的。
步驟2： 當前字元C ：=字元流中的下一個字元。
步驟3： 判斷P+C是否在詞典中：
(1) 如果“是”：用C擴展P，讓P ：= P+C ；
(2) 如果“否”：
① 輸出與當前前綴P相對應的碼字和當前字元C；
② 把字元串P+C 添加到詞典中。
③ 令P ：=空值。
(3) 判斷字元流中是否還有字元需要編碼
① 如果“是”：返回到步驟2。
② 如果“否”：若當前前綴P不是空的，輸出相應於當前前綴P的碼字，然後結束編碼。
2. 解碼算法
在解碼開始時解碼詞典是空的，它將在解碼過程中從碼字流中重構。每當從碼字流中讀入一對碼字-字元(W,C)對時，碼字就參考已經在詞典中的綴-符串，然後把當前碼字的綴-符串string.W 和字元C輸出到字元流(Charstream)，而把當前綴-符串(string.W+C)添加到詞典中。在解碼結束之後，重構的詞典與編碼時生成的詞典完全相同。LZ78解碼的具體算法如下：
步驟1： 在開始時詞典是空的。
步驟2： 當前碼字W ：=碼字流中的下一個碼字。
步驟3： 當前字元C ：= 緊隨碼字之後的字元。
步驟4： 把當前碼字的綴-符串(string.W)輸出到字元流(Charstream)，然後輸出字元C。
步驟5： 把string.W+C添加到詞典中。
步驟6： 判斷碼字流中是否還有碼字要譯
(1) 如果“是”，就返回到步驟2。
(2) 如果“否”，則結束。
[例4.6] 編碼字元串如表4-13所示，編碼過程如表4-14所示。現說明如下：
(1) “步驟”欄表示編碼步驟。
(2) “位置”欄表示在輸入數據中的當前位置。
(3) “詞典”欄表示添加到詞典中的綴-符串，綴-符串的索引等於“步驟”序號。
(4) “輸出”欄以(當前碼字W, 當前字元C)簡化為(W, C)的形式輸出。
表：編碼字元串
位置 1 2 3 4 5 6 7 8 9
字元 A B B C B C A B A
表：編碼過程
步驟 位置 詞典 輸出
1 1A (0,A)
2 2 B (0,B)
3 3 BC (2,C)
4 5 BCA (3,A)
5 8 BA (2,A)
與LZ77相比，LZ78的最大優點是在每個編碼步驟中減少了綴-符串(String)比較的數目，而壓縮率與LZ77類似。