LZ77壓縮算法原理的理解
LZ77壓縮算法原理的理解
數(shù)據(jù)壓縮是一個減小數(shù)據(jù)存儲空間的過程,目前被應(yīng)用在軟件工程的各個地方,了解其一些原理,方便我們更好的甄選壓縮方案。
壓縮方案有很多種,常見的就是有損和無損壓縮?;舴蚵幋a和LZ77(Lempel-Ziv-1977)都是無損壓縮,其中霍夫曼是采用最小冗余編碼的算法進行壓縮,而LZ77是采用字典的方式進行壓縮。關(guān)于霍夫曼編碼的算法,網(wǎng)上有很多對其詳細的講解,我們本篇幅不在細說,主要圖解一下LZ77壓縮算法的方式,看看其有哪些優(yōu)缺點。
信息熵
數(shù)據(jù)為何是可以壓縮的,因為數(shù)據(jù)都會表現(xiàn)出一定的特性,稱為熵。絕大多數(shù)的數(shù)據(jù)所表現(xiàn)出來的容量往往大于其熵所建議的最佳容量。比如所有的數(shù)據(jù)都會有一定的冗余性,我們可以把冗余的數(shù)據(jù)采用更少的位對頻繁出現(xiàn)的字符進行標記,也可以基于數(shù)據(jù)的一些特性基于字典編碼,代替重復(fù)多余的短語。
LZ77算法原理
LZ77壓縮算法采用字典的方式進行壓縮,是一個簡單但十分高效的數(shù)據(jù)壓縮算法。其方式就是把數(shù)據(jù)中一些可以組織成短語(最長字符)的字符加入字典,然后再有相同字符出現(xiàn)采用標記來代替字典中的短語,如此通過標記代替多數(shù)重復(fù)出現(xiàn)的方式以進行壓縮。要理解這種算法,我們先了解3個關(guān)鍵詞:短語字典,滑動窗口和向前緩沖區(qū)。
關(guān)鍵詞:
1.前向緩沖區(qū)
每次讀取數(shù)據(jù)的時候,先把一部分數(shù)據(jù)預(yù)載入前向緩沖區(qū)。為移入滑動窗口做準備
2.滑動窗口
一旦數(shù)據(jù)通過緩沖區(qū),那么它將移動到滑動窗口中,并變成字典的一部分。
3.短語字典
從字符序列S1...Sn,組成n個短語。比如字符(A,B,D) ,可以組合的短語為{(A),(A,B),(A,B,D),(B),(B,D),(D)},如果這些字符在滑動窗口里面,就可以記為當前的短語字典,因為滑動窗口不斷的向前滑動,所以短語字典也是不斷的變化。
LZ77的主要算法邏輯就是,先通過前向緩沖區(qū)預(yù)讀數(shù)據(jù),然后再向滑動窗口移入(滑動窗口有一定的長度),不斷的尋找能與字典中短語匹配的最長短語,然后通過標記符標記。我們還以字符ABD為例子,看如下圖:
目前從前向緩沖區(qū)中可以和滑動窗口中可以匹配的最長短語就是(A,B),然后向前移動的時候再次遇到(A,B)的時候采用標記符代替。
壓縮
當壓縮數(shù)據(jù)的時候,前向緩沖區(qū)與移動窗口之間在做短語匹配的是后會存在2種情況:
- 找不到匹配時:將未匹配的符號編碼成符號標記(多數(shù)都是字符本身)
- 找到匹配時:將其最長的匹配編碼成短語標記。
- 短語標記包含三部分信息:(滑動窗口中的偏移量(從匹配開始的地方計算)、匹配中的符號個數(shù)、匹配結(jié)束后的前向緩沖區(qū)中的第一個符號)。
一旦把n個符號編碼并生成響應(yīng)的標記,就將這n個符號從滑動窗口的一端移出,并用前向緩沖區(qū)中同樣數(shù)量的符號來代替它們,如此,滑動窗口中始終有最新的短語。
我們采用圖例來看:
1、開始
2、滑動窗口中沒有數(shù)據(jù),所以沒有匹配到短語,將字符A標記為A
3、滑動窗口中有A,沒有從緩沖區(qū)中字符(BABC)中匹配到短語,依然把B標記為B
4、緩沖區(qū)字符(ABCB)在滑動窗口的位移6位置找到AB,成功匹配到短語AB,將AB編碼為(6,2,C)
5、緩沖區(qū)字符(BABA)在滑動窗口位移4的位置匹配到短語BAB,將BAB編碼為(4,3,A)
6、緩沖區(qū)字符(BCAD)在滑動窗口位移2的位置匹配到短語BC,將BC編碼為(2,2,A)
7、緩沖區(qū)字符D,在滑動窗口中沒有找到匹配短語,標記為D
8、緩沖區(qū)中沒有數(shù)據(jù)進入了,結(jié)束
解壓
解壓類似于壓縮的逆向過程,通過解碼標記和保持滑動窗口中的符號來更新解壓數(shù)據(jù)。
當解碼字符標記:將標記編碼成字符拷貝到滑動窗口中
解碼短語標記:在滑動窗口中查找響應(yīng)偏移量,同時找到指定長短的短語進行替換。
我們還是采用圖例來看下:
1、開始
2、符號標記A解碼
3、符號標記B解碼
4、短語標記(6,2,C)解碼
5、短語標記(4,3,A)解碼
6、短語標記(2,2,A)解碼
7、符號標記D解碼
優(yōu)缺點
大多數(shù)情況下LZ77壓縮算法的壓縮比相當高,當然了也和你選擇滑動窗口大小,以及前向緩沖區(qū)大小,以及數(shù)據(jù)熵有關(guān)系。其壓縮過程是比較耗時的,因為要花費很多時間尋找滑動窗口中的短語匹配,不過解壓過程會很快,因為每個標記都明確告知在哪個位置可以讀取了。
以上就是LZ77壓縮算法原理的理解,如有疑問請留言或者到本站社區(qū)交流討論,感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
相關(guān)文章
C/C++中棧(stack)&堆(heap)詳解及其作用介紹
這篇文章主要介紹了C/C++中棧(stack)&堆(heap)詳解及其作用,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-09-09C語言通過深度優(yōu)先搜索來解電梯問題和N皇后問題的示例
深度優(yōu)先搜索即是對一個新發(fā)現(xiàn)的節(jié)點上如果還關(guān)聯(lián)未探測到的邊,就沿此邊探測下去,直到發(fā)現(xiàn)從原點可達的所有點為止,這里我們就來展示C語言通過深度優(yōu)先搜索來解電梯問題和N皇后問題的示例2016-06-06