當前位置:成語大全網 - 英語詞典 - lz78算法的分類

lz78算法的分類

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類似。