-
LZW算法
鎖定
LZW算法又叫“串表壓縮算法”就是通過建立一個字符串表，用較短的代碼來表示較長的字符串來實現壓縮。 LZW壓縮算法是Unisys的專利，有效期到2003年，所以對它的使用已經沒有限制了
- 中文名
- LZW算法
- 外文名
- Lempel-Ziv-Welch Encoding
- 別 名
- 串表壓縮算法
- 有效期
- 2003年
- 專 利
- Unisys
- 簡 稱
- LZW 的壓縮算法
LZW算法簡介
字符串和編碼的對應關係是在壓縮過程中動態生成的，並且隱含在壓縮數據中，解壓的時候根據表來進行恢復，算是一種無損壓縮.
根據 Lempel-Ziv-Welch Encoding ，簡稱 LZW 的壓縮算法，用任何一種語言來實現它.
LZW壓縮算法
[1]
的基本概念：LZW壓縮有三個重要的對象：數據流（CharStream）、編碼流（CodeStream）和編譯表（String Table）。在編碼時，數據流是輸入對象（文本文件的據序列），編碼流就是輸出對象（經過壓縮運算的編碼數據）；在解碼時，編碼流則是輸入對象，數據流是輸出對象；而編譯表是在編碼和解碼時都須要用藉助的對象。
字符（Character）：最基礎的數據元素，在文本文件中就是一個字節，在光柵數據中就是一個像素的顏色在指定的顏色列表中的索引值；
字符串（String）：由幾個連續的字符組成；
前綴（Prefix）：也是一個字符串，不過通常用在另一個字符的前面，而且它的長度可以為0；
根（Root）：一個長度的字符串；
編碼（Code）：一個數字，按照固定長度（編碼長度）從編碼流中取出，編譯表的映射值；圖案：一個字符串，按不定長度從數據流中讀出，映射到編譯表條目.
LZW壓縮算法的基本原理：提取原始文本文件數據中的不同字符，基於這些字符創建一個編譯表，然後用編譯表中的字符的索引來替代原始文本文件數據中的相應字符，減少原始數據大小。看起來和調色板圖象的實現原理差不多，但是應該注意到的是，我們這裏的編譯表不是事先創建好的，而是根據原始文件數據動態創建的，解碼時還要從已編碼的數據中還原出原來的編譯表.
LZW算法算法
LZW壓縮算法
LZW算法流程圖
LZW字典中的字符串具有前綴性，即 ωK∈T=＞；ω
T。
LZW算法流程：
步驟1： 開始時的詞典包含所有可能的根(Root)，而當前前綴P是空的；
步驟2： 當前字符(C) ：=字符流中的下一個字符；
步驟3： 判斷綴-符串P+C是否在詞典中
(1) 如果“是”：P ：= P+C // (用C擴展P) ；
(2) 如果“否”
① 把代表當前前綴P的碼字輸出到碼字流;
② 把綴-符串P+C添加到詞典;
③ 令P ：= C //(現在的P僅包含一個字符C);
步驟4： 判斷碼字流中是否還有碼字要譯
(1) 如果“是”，就返回到步驟2；
(2) 如果“否”
① 把代表當前前綴P的碼字輸出到碼字流;
② 結束。
LZW解壓算法
具體解壓步驟如下：
(1)譯碼開始時Dictionary包含所有的根。
(2)讀入在編碼數據流中的第一個碼字 cW(它表示一個Root)。
(3)輸出String.cW到字符數據流Charstream。
(4)使pW=cW 。
(5)讀入編碼數 據流 的下一個碼字cW 。
(6)目前在字典中有String.cW嗎?
YES：(1)將String．cW輸出給字符數據流；
(2)使P=String.pW；
(3)使C=String.cW的第一個字符；
(4)將字符 串P+C添 加進Dictionray。
NO ：(1)使P=String.pW ；
(2)使C=String.pW的第一個字符；
(3)將字符串P+C輸出到字符數據流並將其添加進Dictionray(現在它與cW相一致)。
(7)在編碼數據 流中還有Codeword嗎?
YES：返回(4)繼 續進行 譯碼 。
NO：結束譯碼 。
LZW算法特點
LZW碼能有效利用字符出現頻率冗餘度進行壓縮，且字典是自適應生成的，但通常不能有效地利用位置冗餘度。
具體特點如下：
(3)除了用於圖像數據處理以外，LZW壓縮技術還被用於文本程序等數據壓縮領域。
(4)LZW壓縮技術有很多變體，例如常見的ARC、RKARC、PKZIP高效壓縮程序。
(5)對於任意寬度和像素位長度的圖像，都具有穩定的壓縮過程。壓縮和解壓縮速度較快。
(6)對機器硬件條件要求不高，在 Intel 80386的計算機上即可進行壓縮和解壓縮。
- 參考資料
-
- 1. 深度講解 LZW壓縮算法 ．watchstor[引用日期2013-01-10]
