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