概述
之前在聽(tīng)到數(shù)據(jù)壓縮的時(shí)候, 想著肯定是某些高深莫測(cè)的算法, 能夠完成數(shù)據(jù)的壓縮這種事情, 最近看了看, 嗯, 至少咱還是能看懂的.
無(wú)損壓縮
眾所周知, 不管你是exe, word, txt, dmg等等, 在存儲(chǔ)上都是以二進(jìn)制進(jìn)行存儲(chǔ)的, 所以, 在討論壓縮時(shí), 忽略文件格式即可, 只要將其看做一串?dāng)?shù)字即可.
方案一
開(kāi)始了, 上數(shù)字串: 11111111111111111111.
如果讓你向別人口述這個(gè)字符串, 你會(huì)如何講, "1111...1111". 我估計(jì)就算你這么講, 人家聽(tīng)半天也沒(méi)聽(tīng)明白你說(shuō)的到底是幾個(gè)1. 但是, 如果你這么說(shuō)的話, 就不一樣了: "20個(gè)1". 人家一聽(tīng)就明白了.
你以為這種方式用不到? 天真, 如果是一張黑白照片, 上面的每一個(gè)像素點(diǎn), 非黑即白, 連續(xù)的相同內(nèi)容必然有很多, 如此處理之后, 自然也會(huì)小的多. 當(dāng)然, 這也存在這一定的局限性, 重復(fù)內(nèi)容中間不能被隔開(kāi).
這是一種壓縮的方式, 處理重復(fù)數(shù)據(jù).
方案二
再上一個(gè)數(shù)字串:
123456-78-123456-987-12345678
從我在這個(gè)字符串中打的波折號(hào)標(biāo)記, 大概就能猜到該如何處理了吧. 后面的內(nèi)容與前面的相同, 即重復(fù)數(shù)據(jù). 那就可以去前面抄啊. 此數(shù)字串的處理方式如下: 123456 78 (返回8個(gè), 復(fù)制6個(gè)) 987 (返回17個(gè), 復(fù)制8個(gè)) 當(dāng)然, 真正壓縮后的數(shù)字串后沒(méi)有這一坨中文, 以一個(gè)標(biāo)志編碼來(lái)表示, 咱就假設(shè)是r(return) 和 c (copy)吧. 那上面的數(shù)字串就變成了這樣: 123456-78-r8c6-987-r17c8
這里有個(gè)很有意思的地方, 回憶一下方案一的20個(gè)1. 用這種copy 方式也能表示: 1r1c19. 往回?cái)?shù)1個(gè), 復(fù)制19個(gè), 雖然前面只有一個(gè)數(shù)字, 但是隨著復(fù)制, 長(zhǎng)度是會(huì)變化的, 復(fù)制一個(gè), 長(zhǎng)度就對(duì)應(yīng)變長(zhǎng), 就又可以復(fù)制新的一位了, 以此類推. 如何, 有意思吧.
這也是一種壓縮的思路, 向前復(fù)制數(shù)據(jù).
方案三
這里為了方便說(shuō), 需要引用一下字母了.
看這個(gè)字符串: aaaaaaaaaaaaabc.
每個(gè)字母為了存儲(chǔ)都需要進(jìn)行編碼, ASCII 編碼下: a(97), b(98), c(99). 每個(gè)字母兩位數(shù), 那這個(gè)長(zhǎng)度15的字符串就需要: 15*2=30位數(shù)字表示. 想必已經(jīng)發(fā)現(xiàn)了, 此字符串字母 a 大量出現(xiàn), 如果字母 a 能夠用一位數(shù)字表示, 那整體長(zhǎng)度就小得多了. 那我用9來(lái)表示 a 不就行了?
并不是, 如果你不做特殊標(biāo)志的話, 計(jì)算機(jī)并不能分辨出98 應(yīng)該是 9和8, 還是98. 所以, 需要有個(gè)標(biāo)志, 比如, 以7開(kāi)頭的, 說(shuō)明是1位編碼, 以2開(kāi)頭的都是三位編碼等等.
這個(gè)就厲害了, 是不是看出了什么, 沒(méi)有錯(cuò), 正是大名鼎鼎的哈夫曼編碼. 將使用頻率更高的內(nèi)容使用更短的編碼表示, 代價(jià)就是用較長(zhǎng)的編碼表示頻率較低的內(nèi)容. 對(duì)于哈夫曼編碼就不多說(shuō)了, 這玩意能單獨(dú)寫(xiě)一篇.
你以為哈夫曼編碼只能用來(lái)壓縮文本文檔? no. 它只需要是一個(gè)二進(jìn)制串即可. 畢竟文本文檔寫(xiě)到磁盤(pán)中也不過(guò)是二進(jìn)制串. 你可以將二進(jìn)制文件中的每塊(比如2個(gè)字節(jié))想象為上面的字母, 就可以直接使用哈夫曼編碼進(jìn)行處理了.
ZIP 壓縮格式
zip 壓縮文件是日常使用中較為常見(jiàn)的壓縮格式了, 它就是使用了上面的方案二和方案三進(jìn)行壓縮處理的結(jié)果. 其壓縮步驟如下:
- 將文件使用方案二將大部分重復(fù)內(nèi)容去掉.
- 將步驟一的處理結(jié)果, 通過(guò)哈夫曼編碼進(jìn)行處理, 用較短的編碼表示頻率較高的內(nèi)容. 當(dāng)然, 在這個(gè)步驟需要生成并記錄一個(gè)編碼對(duì)照表, 畢竟每個(gè)文件的高頻率內(nèi)容是不同的.
- 將步驟二中的結(jié)果直接輸出保存到zip文件中, 包括編碼表(畢竟還要解壓嘛). 完成
據(jù)說(shuō), 在步驟二上會(huì)有些優(yōu)化處理, 將文件分為多個(gè)不同的小塊, 針對(duì)不同的小塊單獨(dú)進(jìn)行編碼, 以此實(shí)現(xiàn)不同文件的高效壓縮.
其他
當(dāng)然, 不僅僅是文件的 zip 壓縮, 包括在很多網(wǎng)絡(luò)傳輸中, 為了減少傳輸?shù)陌w積, 也會(huì)將文件進(jìn)行壓縮后再發(fā)送.
有損壓縮
上面的無(wú)損壓縮, 在將壓縮文件解壓后, 能夠完全恢復(fù)壓縮前的文件. 雖然已經(jīng)很好了, 但是有損壓縮的壓縮文件要比它小很多, 當(dāng)然代價(jià)就是無(wú)法還原. 不要以為沒(méi)有用哦. 還記得在線看視頻時(shí), 會(huì)根據(jù)當(dāng)前網(wǎng)速, 選擇標(biāo)清 高清 超清 等格式, 清晰度越低, 對(duì)應(yīng)消耗的流量就越少.
對(duì)于有損壓縮 就需要針對(duì)不同的文件進(jìn)行不同的處理了. 咱也沒(méi)有看, 咱也不敢說(shuō). 就簡(jiǎn)單舉個(gè)例子.
圖片壓縮
比如一張 1080*1080 分辨率的圖片, 為了記住圖片上的每個(gè)像素點(diǎn), 就需要 1080*1080 個(gè)內(nèi)容來(lái)保存. 這里, 如果將相鄰的兩個(gè)像素點(diǎn), 統(tǒng)一使用左側(cè)的保存, 將右側(cè)的丟掉, 也就是每?jī)闪邢袼貋G掉一列, 整體的大小就減少一倍了. 當(dāng)然, 相對(duì)應(yīng)的, 圖片的清晰度也會(huì)下降.
當(dāng)然, 這種直接丟棄的方式有些粗暴了, jpeg的壓縮方式據(jù)說(shuō)不錯(cuò), 不過(guò)我還沒(méi)有看. 至于其他的視頻啊, 音頻啊, 都有吧. 嗯, 我想.
總結(jié)
在數(shù)據(jù)的無(wú)損壓縮上, 思想基本就是減少重復(fù)的數(shù)據(jù), 不管是重復(fù)數(shù)據(jù)復(fù)制, 還是哈夫曼編碼都可以說(shuō)是圍繞著這個(gè)思想來(lái)的.
在看過(guò)壓縮編碼之后, 讓我想起了之前看到的糾錯(cuò)碼. 糾錯(cuò)碼是怎么處理的? 往原來(lái)的數(shù)據(jù)中添加內(nèi)容, 通過(guò)數(shù)據(jù)冗余來(lái)進(jìn)行糾錯(cuò), 而壓縮呢? 將源文件中的數(shù)據(jù)通過(guò)轉(zhuǎn)換使得其體積減小. 有點(diǎn)意思, 就像一個(gè)事情的正反兩面, 沒(méi)有孰是孰非, 就看你怎么去用它了.
