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

(點選上方藍字，快速關註我們)

編譯：nEoYe，英文：unwttng

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

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

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

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

• 對被壓縮物件進行壓縮，意味著什麼？

• 如何能將標的物件變得比原來更小？

• 如何具體實現壓縮技術

讓我們來一一解答吧！

基礎知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

取而代之：

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

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

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

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

隨著你不斷改變原始影象的畫素顏色，你會發現我們能夠壓縮的比例和圖片本身有關。如果整張圖片只有一種顏色，或者顏色的連續區域很長，我們可以得到很小的輸出。使用行程長度壓縮演演算法能夠得到的最小儲存大小是 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 網站上將這個載入過程做成了一張動圖，並將它嵌入了進來，看出什麼問題了麼？）：

編註：微信動圖最大 2 MB，我們只能分割成兩張 GIF 圖了。https://giphy.com/gifs/l1J3QaZoHeNZ9JFU4

看起來很奇怪對麼？首先，他們載入了這張動圖的第一幀低清晰度圖片。接著，當更大的資料傳輸過來後，出現了動圖。但是還不完全，只有僅僅幾幀。然後，越來越多幀圖片被傳輸了過來，直到最後完全載入整張動圖。

這就是現代的流媒體壓縮技術：混合的壓縮策略幾乎完全是為了，以盡可能少的位元組（大小越小，時間也越短），提供給使用者流暢的內容。針對檔案的無失真壓縮技術，比如上面說到的 RLE，也有用武之地，而且它仍然是很多最好的桌面檔案壓縮工具的核心模組。但是，多虧了有失真壓縮，你才能在電視上流暢地觀看《權利的遊戲》。

資料壓縮無處不在

關於壓縮技術本文我們就先介紹到這裡，但這隻是冰山一角。

我們學習了壓縮技術的基本思想，從這些技術中得出了一條很重要的哲學道理：

影象，文字，影片，音樂 —— 任何資料都沒有唯一正確的表現形式。區別隻是在於有多少種表現資料的有效方式。

壓縮技術就是不斷尋找更加有效的方式來儲存你的資料，最強大的壓縮演演算法，對於任何資料，它都能找到一種高效的方法對其進行壓縮。

感謝閱讀，如果你認可我在文中製作的那些實時 demo，請隨時與你的朋友分享。

覺得本文有幫助？請分享給更多人

關註「演演算法愛好者」，修煉程式設計內功