歡迎光臨
每天分享高質量文章

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

(點擊上方藍字,快速關註我們)


編譯: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,請隨時與你的朋友分享。


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

關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂