LZ77壓縮算法原理的理解-創(chuàng)新互聯(lián)

LZ77壓縮算法原理的理解

10年積累的做網(wǎng)站、網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)制作后付款的網(wǎng)站建設(shè)流程，更有杜集免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

數(shù)據(jù)壓縮是一個(gè)減小數(shù)據(jù)存儲(chǔ)空間的過(guò)程，目前被應(yīng)用在軟件工程的各個(gè)地方，了解其一些原理，方便我們更好的甄選壓縮方案。

壓縮方案有很多種，常見(jiàn)的就是有損和無(wú)損壓縮?；舴蚵幋a和LZ77(Lempel-Ziv-1977)都是無(wú)損壓縮，其中霍夫曼是采用最小冗余編碼的算法進(jìn)行壓縮，而LZ77是采用字典的方式進(jìn)行壓縮。關(guān)于霍夫曼編碼的算法，網(wǎng)上有很多對(duì)其詳細(xì)的講解，我們本篇幅不在細(xì)說(shuō)，主要圖解一下LZ77壓縮算法的方式，看看其有哪些優(yōu)缺點(diǎn)。

信息熵

數(shù)據(jù)為何是可以壓縮的，因?yàn)閿?shù)據(jù)都會(huì)表現(xiàn)出一定的特性，稱為熵。絕大多數(shù)的數(shù)據(jù)所表現(xiàn)出來(lái)的容量往往大于其熵所建議的最佳容量。比如所有的數(shù)據(jù)都會(huì)有一定的冗余性，我們可以把冗余的數(shù)據(jù)采用更少的位對(duì)頻繁出現(xiàn)的字符進(jìn)行標(biāo)記，也可以基于數(shù)據(jù)的一些特性基于字典編碼，代替重復(fù)多余的短語(yǔ)。

  LZ77算法原理

LZ77壓縮算法采用字典的方式進(jìn)行壓縮，是一個(gè)簡(jiǎn)單但十分高效的數(shù)據(jù)壓縮算法。其方式就是把數(shù)據(jù)中一些可以組織成短語(yǔ)(最長(zhǎng)字符)的字符加入字典，然后再有相同字符出現(xiàn)采用標(biāo)記來(lái)代替字典中的短語(yǔ)，如此通過(guò)標(biāo)記代替多數(shù)重復(fù)出現(xiàn)的方式以進(jìn)行壓縮。要理解這種算法，我們先了解3個(gè)關(guān)鍵詞:短語(yǔ)字典，滑動(dòng)窗口和向前緩沖區(qū)。

關(guān)鍵詞：

1.前向緩沖區(qū)

每次讀取數(shù)據(jù)的時(shí)候，先把一部分?jǐn)?shù)據(jù)預(yù)載入前向緩沖區(qū)。為移入滑動(dòng)窗口做準(zhǔn)備

2.滑動(dòng)窗口

一旦數(shù)據(jù)通過(guò)緩沖區(qū)，那么它將移動(dòng)到滑動(dòng)窗口中，并變成字典的一部分。

3.短語(yǔ)字典

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

LZ77的主要算法邏輯就是，先通過(guò)前向緩沖區(qū)預(yù)讀數(shù)據(jù)，然后再向滑動(dòng)窗口移入（滑動(dòng)窗口有一定的長(zhǎng)度），不斷的尋找能與字典中短語(yǔ)匹配的最長(zhǎng)短語(yǔ)，然后通過(guò)標(biāo)記符標(biāo)記。我們還以字符ABD為例子，看如下圖:

目前從前向緩沖區(qū)中可以和滑動(dòng)窗口中可以匹配的最長(zhǎng)短語(yǔ)就是（A,B）,然后向前移動(dòng)的時(shí)候再次遇到（A,B）的時(shí)候采用標(biāo)記符代替。

壓縮

當(dāng)壓縮數(shù)據(jù)的時(shí)候，前向緩沖區(qū)與移動(dòng)窗口之間在做短語(yǔ)匹配的是后會(huì)存在2種情況:

• 找不到匹配時(shí)：將未匹配的符號(hào)編碼成符號(hào)標(biāo)記（多數(shù)都是字符本身）
• 找到匹配時(shí):將其最長(zhǎng)的匹配編碼成短語(yǔ)標(biāo)記。
• 短語(yǔ)標(biāo)記包含三部分信息:（滑動(dòng)窗口中的偏移量（從匹配開(kāi)始的地方計(jì)算）、匹配中的符號(hào)個(gè)數(shù)、匹配結(jié)束后的前向緩沖區(qū)中的第一個(gè)符號(hào)）。

一旦把n個(gè)符號(hào)編碼并生成響應(yīng)的標(biāo)記，就將這n個(gè)符號(hào)從滑動(dòng)窗口的一端移出，并用前向緩沖區(qū)中同樣數(shù)量的符號(hào)來(lái)代替它們，如此，滑動(dòng)窗口中始終有最新的短語(yǔ)。

我們采用圖例來(lái)看:

1、開(kāi)始

2、滑動(dòng)窗口中沒(méi)有數(shù)據(jù)，所以沒(méi)有匹配到短語(yǔ)，將字符A標(biāo)記為A

3、滑動(dòng)窗口中有A,沒(méi)有從緩沖區(qū)中字符（BABC）中匹配到短語(yǔ)，依然把B標(biāo)記為B

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

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

6、緩沖區(qū)字符（BCAD）在滑動(dòng)窗口位移2的位置匹配到短語(yǔ)BC，將BC編碼為（2,2,A）

7、緩沖區(qū)字符D,在滑動(dòng)窗口中沒(méi)有找到匹配短語(yǔ)，標(biāo)記為D

8、緩沖區(qū)中沒(méi)有數(shù)據(jù)進(jìn)入了，結(jié)束

 解壓

解壓類似于壓縮的逆向過(guò)程，通過(guò)解碼標(biāo)記和保持滑動(dòng)窗口中的符號(hào)來(lái)更新解壓數(shù)據(jù)。

當(dāng)解碼字符標(biāo)記:將標(biāo)記編碼成字符拷貝到滑動(dòng)窗口中

解碼短語(yǔ)標(biāo)記:在滑動(dòng)窗口中查找響應(yīng)偏移量，同時(shí)找到指定長(zhǎng)短的短語(yǔ)進(jìn)行替換。

我們還是采用圖例來(lái)看下:

1、開(kāi)始

2、符號(hào)標(biāo)記A解碼

3、符號(hào)標(biāo)記B解碼

4、短語(yǔ)標(biāo)記(6,2,C)解碼

5、短語(yǔ)標(biāo)記(4,3,A)解碼

6、短語(yǔ)標(biāo)記(2,2,A)解碼

7、符號(hào)標(biāo)記D解碼

 優(yōu)缺點(diǎn)

大多數(shù)情況下LZ77壓縮算法的壓縮比相當(dāng)高，當(dāng)然了也和你選擇滑動(dòng)窗口大小，以及前向緩沖區(qū)大小，以及數(shù)據(jù)熵有關(guān)系。其壓縮過(guò)程是比較耗時(shí)的，因?yàn)橐ㄙM(fèi)很多時(shí)間尋找滑動(dòng)窗口中的短語(yǔ)匹配，不過(guò)解壓過(guò)程會(huì)很快，因?yàn)槊總€(gè)標(biāo)記都明確告知在哪個(gè)位置可以讀取了。

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.bm7419.com，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享題目：LZ77壓縮算法原理的理解-創(chuàng)新互聯(lián)
分享地址：http://www.bm7419.com/article22/dgcsjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、響應(yīng)式網(wǎng)站、企業(yè)網(wǎng)站制作、用戶體驗(yàn)、商城網(wǎng)站、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)