最近由于課程設計需要做解壓縮算法
1 導論
許多場合，開始時不知道要編碼資料的統計特性，也不一定允許你事先知道它們的統計特性。是以，人們提出了許許多多的資料壓縮方法，企圖用來對這些資料進行壓縮編碼，在實際編碼過程中以盡可能獲得最大的壓縮比。這些技術統稱為通用編碼技術。
字典編碼(dictionary encoding)技術（以下簡稱DE）就是屬于這一類，這種技術屬于無損壓縮技術。
- DE根據的是
資料本身包含有重複代碼
這個特性
例如文本檔案和光栅圖像就具有這種特性
1.1 分類
種類很多，歸納起來大緻有兩類
1.1.1 查找正在壓縮的字元序列是否在曆史輸入資料中出現過
用已經出現過的字元串替代重複部分，輸出僅僅是指向之前出現過的字元串的“指針”
-
這裡的“字典”指 用以前處理過的資料來表示編碼過程中遇到的重複部分
這類編碼的所有算法都是以
abraham lempel
jakob ziv
lz77
1.1.2 從輸入的資料中建立一個“短語字典(dictionary of the phrases)”
這種短語不一定是像“好好學習天天向上”和“你個糟老頭子壞得很我信你個鬼”這類具有具體含義的短語，它可以是任意字元的組合
編碼資料過程中當遇到已經在字典中出現的“短語”時，編碼器就輸出這個字典中的短語的“索引号”，而不是短語本身。
j.ziv
a.lempel
在1978年首次發表了這種編碼方法的文章
在他們的研究基礎上，
terry a.weltch
在1984年發表了改進這種編碼算法的文章，是以把這種編碼方法稱為
LZW(lempel-ziv walch)
壓縮編碼，首先在高速硬碟控制器上應用了這種算法
2 LZ77算法
2.1 常見術語
-
輸入資料流(input stream)
要被壓縮的字元序列
-
字元(character)
輸入資料流中的基本單元。
-
編碼位置(coding position)
輸入資料流中目前要編碼的字元位置，指前向緩沖存儲器中的開始字元
-
前向緩沖存儲器(Lookahead buffer)
存放從編碼位置到輸入資料流結束的字元序列的存儲器。
-
視窗(window)
包含W個字元的視窗，字元是從編碼位置開始向後數也就是最後處理的字元數
-
指針(pointer)
指向視窗中的比對串且含長度的指針
核心是查找從前向緩沖存儲器開始的最長的比對串
2.2 執行步驟
1.把編碼位置設定到輸入資料流的起始位
2.查找視窗中最長的比對串
3.以“(Pointer, Length) Characters”的格式輸出
其中Pointer是指向視窗中比對串的指針，Length表示比對字元的長度，Characters是前向緩沖存儲器中的不比對的第1個字元。
4.如果前向緩沖存儲器不是空的，則把編碼位置和視窗向前移(Length+1)個字元，然後傳回到步驟2
[例]
- “步驟” 編碼步驟
- “位置” 編碼位置，輸入資料流中的第1個字元為編碼位置1
- “比對串” 視窗中找到的最長的比對串
- “字元” 比對後在前向緩沖存儲器中的第1個字元
- “輸出” 以“(Back_chars, Chars_length) Explicit_character”格式輸出
- (Back_chars, Chars_length) 指向比對串的指針
告訴譯碼器在這個視窗中向後退Back_chars個字元然後拷貝Chars_length個字元到輸出
Explicit_character 真實字元
例如，表編碼過程的輸出(5,2) C告訴譯碼器回退5個字元，然後拷貝2個字元“AB”
但wikipedia認為，粗體字了解成
從編碼位置開始往回數Back_chars個字元，從該字元開始數起的字元串與接下來的Chars_length個字元完全相同
3 LZ78算法
3.1 術語和符号
-
字元流(Charstream)
要被編碼的資料序列
-
字元(Character)
字元流中的基本資料單元
-
字首(Prefix)
在一個字元之前的字元序列
-綴-符串(String)
字首＋字元
-
碼字(Code word)
碼字流中的基本資料單元，代表字典中的一串字元
-
碼字流(Codestream)
碼字和字元組成的序列，編碼器的輸出
-
字典(Dictionary)
綴-符串表。按照字典中的索引号對每條綴-符串(String)指定一個碼字(Code word)
-
目前字首(Current prefix)
在編碼算法中使用，指目前正在處理的字首，用符号P表示。
-
目前字元(Current character)
在編碼算法中使用，指目前字首之後的字元，用符号C表示。
-
目前碼字(Current code word)
在譯碼算法中使用，指目前處理的碼字，用W表示目前碼字，String.W表示目前碼字的綴-符串
3.2 編碼算法
不斷從字元流中提取新的綴-符串(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)，然後添加到字典中
具體算法步驟1
步驟1
在開始時，字典和目前字首P都是空的.
步驟2
目前字元C:=字元流中的下一個字元
步驟3
P+C 是否在字典中
(1) “是”
用C擴充P，讓P := P+C
(2) “否”
① 輸出與目前字首P相對應的碼字和目前字元C
② 把字元串P+C 添加到字典中
③ 令P:=空值
(3) 字元流中是否還有字元需要編碼
① “是” 傳回到步驟2
② “否” 若目前字首P非空，輸出相應于目前字首P的碼字，然後結束編碼
3.3 譯碼算法
在譯碼開始時譯碼字典為空，它将在譯碼過程中從碼字流中形成
每當從碼字流中讀入一對碼字-字元(W,C)對時，碼字就參考已經在字典中的綴-符串，然後把目前碼字的綴-符串string
W 和字元C輸出到字元流(Charstream)，而把當字首-符串(string.W+C)添加到字典中。在譯碼結束之後，重構的字典與編碼時生成的字典完全相同
具體算法
開始時字典空
目前碼字W :=碼字流中的下一個碼字
目前字元C := 緊随碼字之後的字元。
步驟4
把目前碼字的綴-符串(string.W)輸出到字元流(Charstream)，然後輸出字元C
步驟5
把string.W+C添加到字典中
步驟6
判斷碼字流中是否還有碼字要譯
(1) “是” 傳回到步驟2
(2) “否” 結束
例
●“步驟” 編碼步驟
●“位置” 在輸入資料中的目前位置
●“字典” 添加到字典中的綴-符串，綴-符串的索引等于“步驟”序号
●“輸出” 以(目前碼字W, 目前字元C)簡化為(W, C)的形式輸出
與LZ77相比，LZ78的最大優點是在每個編碼步驟中減少了綴-符串(String)比較的數目，而壓縮率與LZ77類似