可視化解釋壓縮演算法的工作原理

最新 02-12

編譯：nEoYe，英文：unwttng

http://blog.jobbole.com/113505/

壓縮技術在生活中無處不在，硬碟上存儲數據、發送電視信號、網頁傳輸、流媒體、電子遊戲……現代計算幾乎沒有一個重要領域不使用壓縮技術。

那麼壓縮技術到底是什麼？

無論你使用過很多年的電腦壓縮軟體還是從沒想過這個問題，本文將嘗試解釋，當你壓縮一個文件或傳輸一段視頻時，其中的數據到底發生了什麼變化。我們將探尋這些重要問題的答案，在此過程中，也許會提出一些新的問題。

讓我們來一一解答吧！

GIF

基礎知識

在研究壓縮技術和數字信息之前，這裡有一段通俗易懂的壓縮技術介紹。讓我們來看看下方的英文字母：

看看我們用來表現這個單詞（Tree）的字元，加起來一共是 4 個：

看起來還行。如果我們用漢字會發生什麼？

天哪！只用了一個字元！我們有改變它要傳達的意思和任何信息么？並沒有。但是，我們降低了75%的網頁空間，來表達「tree」的含義。那麼我們到底做了什麼？

沒什麼神奇的 —— 我們只是用另一種方式去表達了這個含義。我們選擇了一種不同的、更加高效的信息表現方式。Spoiler：接下來是本文最重要的部分，請仔細閱讀。

那麼，如果是像素級的圖片呢？

你肯定會覺得驚訝，如何將上面的例子應用於嚴謹的數字圖像數據呢？讓我們來看一下最近很流行的一類數據 —— 圖片。現階段，讓我們先從簡單的像素級圖片入手，而不是一上來就嘗試去壓縮一張高解析度的 Instagram 圖片或其他類似的複雜圖片。

不怎麼好看對嗎？因為這是我自己畫的。上面是一個 10*10 的網格，每一種顏色都可以用『B』、『Y』和『G』中的一個字元來表示。

我們怎麼用數字化的方式表示上面的圖像？以原始的方式存儲這張圖片的文件可能包含下面的內容：

我們所做的只是從左到右，從上到下，為每個像素寫下了代表其顏色的字元。正如你預期的那樣，總共會有 100 個字元。我們假設這 100 個字元會佔用硬碟上的 100 個位元組。這種存儲方式，定義了一個合理的存儲文件大小上限。任何其他存儲方式，只要其文件大小大於上述方法，都是無意義的，或者嘗試去存儲除了圖片數據之外的信息（比如元數據或其他數據）。我想你們應該能認同我的這種觀點。

在你往下看之前，開動下你的大腦。如果我讓你用少於 100 個字元來表示這張圖片，你會怎麼做呢？喝一杯茶，仔細想一想，我等著你。

想到什麼方法了嗎？很好，我也想到了一個。

我準備將我的方法命名為行程長度壓縮演算法（RLE）。開玩笑的啦，這個方法不是我想出來的，也不是我命名的。至少從六十年代起，它已經成為了一種基本的壓縮技術。我打賭，你們之中有些人剛剛才想出這種方法。

我們將行程長度壓縮演算法應用於上面的圖片。在上方，我們寫了很多一連串的相同顏色字元。讓我們從那些『B』字元下手。那麼我們能夠壓縮這些重複的字元么？

當然可以！拋棄下面這種方式：

取而代之：

看起來有戲。通過縮寫這一長串相同字元，我們將 17 個字元減少到了 3 個。順便說下，我們將這些重複的字元串稱之為runs。所以行程長度壓縮演算法是通過記下runs的長度，而不是記下每一個字元，對數據進行壓縮編碼。這種壓縮方式並沒有信息丟失。能夠解析前一個文件的程序，稍微修改下，就能解析我們的新文件格式。2 者解析出來的圖片應該是一樣的。

下面的實時 demo 展示了原始圖像和它的 2 種存儲編碼方式：原始版本和行程長度壓縮編碼版。

通過點擊任意像素點，你可以改變其顏色，下方的存儲字元也會隨之變化。

隨著你不斷改變原始圖像的像素顏色，你會發現我們能夠壓縮的比例和圖片本身有關。如果整張圖片只有一種顏色，或者顏色的連續區域很長，我們可以得到很小的輸出。使用行程長度壓縮演算法能夠得到的最小存儲大小是 4 位元組：

當然，這個演算法在某些場景下也會表現的十分糟糕。實際上，用這個演算法壓縮出來的文件，可以比原始一個像素一個像素表示的方式都要大。你會發現，當需要表示『1B』或』1G』時，它會使用 2 個字元。如果在你的像素圖片中，每個顏色的連續長度只有 1 ，會發生什麼？

驚訝吧。

是時候學習些術語了。

壓縮率

如何衡量我們的壓縮演算法到底使數據縮小了多少？你可能已經猜到了 —— 計算數據壓縮前後的大小比。

比如，我們使用演算法將 100 位元組的像素圖片壓縮至 42 位元組，那麼我們計算出的壓縮率為 (100 / 42) ≈ 2.38。最好的情況是只有一種顏色的圖片，這種演算法的壓縮率高達 (100 / 4) = 25！然而，當該演算法作用於每個顏色的連續長度只有 1 的圖片上時，壓縮率只有 (100 / 200) = 0.5。Protip：壓縮率小於 1 簡直是糟糕透了。

我們可以看出，這種基礎 RLE 演算法的壓縮率對於輸入的數據結構十分敏感。對於這類簡單的演算法，這種現象很常見。該演算法對於數據的結構做了若干假設，如果要使該演算法能夠輸出理想結果，原始輸入數據中必須存在重複相鄰的相同位元組。一個更智能的 RLE 演算法實現可能會嘗試使用重複的子串來對數據進行壓縮編碼。

甚至我直接用英語文字描述這張圖片，壓縮率都比 2 要大！運用這種方法，可以將數據壓縮存儲成一種友好、簡潔的文件格式，相比第一次嘗試我們又邁出了一小步。

數據到底能被壓縮到多小？

這是一個很大很寬泛的問題。當然，人們認為，對於任何輸入數據，一個合理設計的壓縮演算法，應該至少能將數據壓縮那麼一點（這裡的一點點，既指口語上的，也表示學術上的）。

不幸的是，事情並沒有那麼簡單。假設我們有一個演算法 A，對於任何的輸入，能夠使壓縮率始終嚴格大於 1。對於某些輸入，壓縮率可以為 2.5；對於另一些輸入，壓縮率可能為 1.000000002。

如果這種演算法存在，我們可以無限迭代調用它。對於某個輸入，我們計算 A(A(A(data)))，對每一次的輸出不斷調用 A()。我們每調用一次，數據的大小至少會被壓縮一點點。不難看出，到最後，我們能將數據壓縮至 1 位元組，甚至 0 位元組？

這看起來不太現實。事實也確實如此。我們甚至不需要使用遞歸法去證明該演算法的可行性，試想下這種情況：有 9 個不同的文件，沒有任何方法能夠在不丟失數據的情況下，將這 9 個文件都壓縮至 3 位元組。

3 個位元組一共只能表示 8 種不同的數據：000、001、010、100、011、101、110、111。即使我們有某個十分強大的壓縮演算法，能夠將前 8 個文件分別壓縮成前面這 8 種位元組表示，第 9 個文件也只能壓縮為其中之一。對於該演算法，任意 8 個以上的未壓縮數據片段，都無法找到更多不同的 3 個位元組來表示。

這裡有一條重要的原則：對常見數據的壓縮，任何演算法的壓縮率都有嚴格的限制。你可以不斷地使用某個演算法對數據進行壓縮，直到無法將數據壓縮得更小，然後換種演算法繼續嘗試。這種做法也許會將數據壓縮得更小（實際上，很多線上的軟體都是這麼做的），但最終，你會遇到你永遠無法再次壓縮的數據。其實，你對不同的演算法的重複調用，到頭來又變成了另一種壓縮演算法。這條規則現在仍然適用。

柯氏複雜性

看到下面你也許會更加失望。對於壓縮率的大小，不僅僅在演算法上有著理論的限制 —— 數據本身的複雜度對其也會有很大的影響

讓我們來看下下面的 2 個字元串：

和：

2 者是完全相同的長度，但是，你可以很輕易地看出來，後者明顯要更加複雜。說的更具體點，使用 RLE 壓縮演算法，我們可以將第一個字元串壓縮至最多 3 個字元（「24a」）。

柯氏複雜性（一位蘇聯數學家 Andrey Nikolaevich Kolmogorov 的偉大發明）將上述內容闡述地很好。當然，一個事物的度量方式有很多種，柯氏複雜性是一種比較不錯的度量方式。數據的柯氏複雜性是指，通過計算機程序輸出的，能夠描述這個字元串的最短長度。

顯然，對於柯氏複雜性，任何字元串『S』的長度上界就是其本身。上述說法將演算法進行了一定的簡化，其實數據的柯氏複雜性還需加上整個程序的長度 —— 包括解釋器或編譯後的代碼。但是就本文討論的範圍來說，沒有必要。直接把它認為是你能生成的該數據的最短長度。

柯氏複雜性對於你選擇什麼編程語言並不是很敏感。程序語言的選擇只會對複雜度的一個常數因子產生影響。下面這句話很重要：無論你選擇什麼語言來描述數據，所帶來的長度變化是有限的。有些數據就是需要比一百萬個綠色像素點更多的空間來表示，怎麼也減少不了。

數據丟失

但是，別放棄希望。我們之前討論的都是無損壓縮。無損壓縮是指，通過壓縮之後的數據，能夠完全還原壓縮之前的原始數據。也就是說，如果 C 是我們的壓縮演算法，D 是相應的解壓縮演算法，D(C(x)) = x 對於任何輸入數據 x 永遠成立。

無損壓縮是十分有用的！當壓縮一些文獻或博文、稅收檔案、低解析度的像素圖片等類似的文本數據時，你肯定想要做到無損壓縮。對於這些數據，保證數據的精確和每個字元的順序，是很重要的。

但是也有其他選擇。有損壓縮是指，不保證壓縮的數據解壓之後與壓縮之前的數據完全一致。這種壓縮演算法十分常見。

有損壓縮應用十分廣泛。人類的感官對於一些微小錯誤或瑕疵是比較有容忍度的。數據丟失主要體現在壓縮圖片、音頻（或視頻）文件時。

需要例子嗎？請看下面 2 張奧巴馬的圖片。

第一張圖片是大小約為 335 千位元組的 PNG 文件（PNG 是一種無損圖片壓縮格式）。這將作為我們的參照物。

第二張圖片，是第一張圖片保存為 JPEG 格式的結果，這是一種會丟失許多數據的有損壓縮。第二張圖片的大小約為 22 千位元組，相比原始圖片，壓縮率約為 15，這麼大的壓縮率並不表示數據丟失會很嚴重。

你能看出這 2 張圖片的區別么？也許能看出一點點。如果你儘可能靠近你的屏幕，眯起眼睛，轉頭環視下這張圖片。接著你去看他的頭髮細節，一根一根地數頭髮，在沒有頭髮的地方你會發現一些模糊。關鍵點不在於第二張圖是不是一個完美的複製品，而在於它是不是足夠好用。當你通過互聯網傳輸數據時，十五倍的壓縮率比起一張毫無損失的 PNG 圖片更有價值。

但這並不是說在任何情況下，它都如此出色。為了達到這種壓縮效果，JPEG 必須丟掉很多數據，儘管同時它儘力避免丟失太多數據，但是你可以嘗試探索下它的極限。通過下面的實時 demo，你可以看出 JPEG 格式的圖片質量下限能到多少。同時在圖片清晰度變得無法容忍之前，注意看下圖片質量是多少。像我之前說的那樣，人類的視覺容忍度是很高的。

編註：英文原文此處有一個 Demo，本文無法再現，請在 https://unwttng.com/compression-decompressed 查看

像 Netflix 和 YouTube 上的視頻流服務，以及 Spotify 和 Soundcloud 上的音頻流服務，都是使用的有損壓縮。緩衝或延遲是一個用戶無法忍受的，所以在保證音視頻質量的同時，這些服務儘可能地去壓縮數據。你經常會看到數據的動態壓縮，一開始視頻會比較模糊，當檢測到你的網路速度可以接受更小的壓縮率時，視頻的清晰度會隨之提高。

看到下面這張來自 Giphy 網站上的動圖了么？數據的動態壓縮在這裡同樣適用。看看他們是如何處理網速慢的情況下的動圖載入（沒錯，我在 Giphy 網站上將這個載入過程做成了一張動圖，並將它嵌入了進來，看出什麼問題了么？）：

GIF