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 1 A (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類似。