LZ77壓縮算法原理的理解

數據壓縮是一個減小數據存儲空間的過程，目前被應用在軟件工程的各個地方，了解其一些原理，方便我們更好的甄選壓縮方案。

壓縮方案有很多種，常見的就是有損和無損壓縮。霍夫曼編碼和LZ77(Lempel-Ziv-1977)都是無損壓縮，其中霍夫曼是采用最小冗余編碼的算法進行壓縮，而LZ77是采用字典的方式進行壓縮。關于霍夫曼編碼的算法，網上有很多對其詳細的講解，我們本篇幅不在細說，主要圖解一下LZ77壓縮算法的方式，看看其有哪些優缺點。

 信息熵

數據為何是可以壓縮的，因為數據都會表現出一定的特性，稱為熵。絕大多數的數據所表現出來的容量往往大于其熵所建議的最佳容量。比如所有的數據都會有一定的冗余性，我們可以把冗余的數據采用更少的位對頻繁出現的字符進行標記，也可以基于數據的一些特性基于字典編碼，代替重復多余的短語。

  LZ77算法原理

LZ77壓縮算法采用字典的方式進行壓縮，是一個簡單但十分高效的數據壓縮算法。其方式就是把數據中一些可以組織成短語(最長字符)的字符加入字典，然后再有相同字符出現采用標記來代替字典中的短語，如此通過標記代替多數重復出現的方式以進行壓縮。要理解這種算法，我們先了解3個關鍵詞:短語字典，滑動窗口和向前緩沖區。

關鍵詞：

1.前向緩沖區

每次讀取數據的時候，先把一部分數據預載入前向緩沖區。為移入滑動窗口做準備

2.滑動窗口

一旦數據通過緩沖區，那么它將移動到滑動窗口中，并變成字典的一部分。

3.短語字典

從字符序列S1...Sn，組成n個短語。比如字符(A,B,D) ,可以組合的短語為{(A),(A,B),(A,B,D),(B),(B,D),(D)},如果這些字符在滑動窗口里面，就可以記為當前的短語字典，因為滑動窗口不斷的向前滑動，所以短語字典也是不斷的變化。

LZ77的主要算法邏輯就是，先通過前向緩沖區預讀數據，然后再向滑動窗口移入（滑動窗口有一定的長度），不斷的尋找能與字典中短語匹配的最長短語，然后通過標記符標記。我們還以字符ABD為例子，看如下圖:

目前從前向緩沖區中可以和滑動窗口中可以匹配的最長短語就是（A,B）,然后向前移動的時候再次遇到（A,B）的時候采用標記符代替。

壓縮

當壓縮數據的時候，前向緩沖區與移動窗口之間在做短語匹配的是后會存在2種情況:

• 找不到匹配時：將未匹配的符號編碼成符號標記（多數都是字符本身）
• 找到匹配時:將其最長的匹配編碼成短語標記。
• 短語標記包含三部分信息:（滑動窗口中的偏移量（從匹配開始的地方計算）、匹配中的符號個數、匹配結束后的前向緩沖區中的第一個符號）。

 一旦把n個符號編碼并生成響應的標記，就將這n個符號從滑動窗口的一端移出，并用前向緩沖區中同樣數量的符號來代替它們，如此，滑動窗口中始終有最新的短語。

我們采用圖例來看:

 1、開始

2、滑動窗口中沒有數據，所以沒有匹配到短語，將字符A標記為A

3、滑動窗口中有A,沒有從緩沖區中字符（BABC）中匹配到短語，依然把B標記為B

4、緩沖區字符（ABCB）在滑動窗口的位移6位置找到AB,成功匹配到短語AB,將AB編碼為(6,2,C)

5、緩沖區字符（BABA）在滑動窗口位移4的位置匹配到短語BAB,將BAB編碼為(4,3,A)

6、緩沖區字符（BCAD）在滑動窗口位移2的位置匹配到短語BC，將BC編碼為（2,2,A）

7、緩沖區字符D,在滑動窗口中沒有找到匹配短語，標記為D

8、緩沖區中沒有數據進入了，結束

 解壓

解壓類似于壓縮的逆向過程，通過解碼標記和保持滑動窗口中的符號來更新解壓數據。

當解碼字符標記:將標記編碼成字符拷貝到滑動窗口中

解碼短語標記:在滑動窗口中查找響應偏移量，同時找到指定長短的短語進行替換。

我們還是采用圖例來看下:

1、開始

2、符號標記A解碼

3、符號標記B解碼

4、短語標記(6,2,C)解碼

5、短語標記(4,3,A)解碼

6、短語標記(2,2,A)解碼

7、符號標記D解碼

 優缺點

大多數情況下LZ77壓縮算法的壓縮比相當高，當然了也和你選擇滑動窗口大小，以及前向緩沖區大小，以及數據熵有關系。其壓縮過程是比較耗時的，因為要花費很多時間尋找滑動窗口中的短語匹配，不過解壓過程會很快，因為每個標記都明確告知在哪個位置可以讀取了。

以上就是LZ77壓縮算法原理的理解，如有疑問請留言或者到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！