Compression

濃縮資料

如何簡明扼要的記載資料、傳述訊息呢?

縮短資料長度,減少交流時間,減少儲存空間,好處多多。

Compress / Decompress

「壓縮」是濃縮資料,「解壓縮」是回復資料。觀念類似先前提及的「編碼」與「解碼」。

              compress
Thank you! -------------> 3Q!
           <-------------
             decompress

                 compress
200000000美金 -------------> 兩億鎂
              <-------------
                decompress

文字、聲音、圖像、動作、感受,通通可以壓縮。

資料先壓縮、再解壓縮,如果還是跟原本資料一模一樣,就叫做「無失真壓縮lossless compression」;如果不一樣就叫做「失真壓縮lossy compression」。

用電腦處理資料,首重精準無誤。以下僅介紹無失真壓縮。

二元碼壓縮

二元碼(二進位字串)縮短成另一個二元碼。

                              compress   
001100111100101010100001   ------------->   10110101
                           <-------------
                             decompress  

文字壓縮

例如Doctor縮寫成Dr.、公共汽車簡稱為公車。

vs.      versus
lol      laugh out loudly
RTFM     read the fucking manual
afaik    as far as I known
¥        Japanese Yen

文字壓縮得視作二元碼壓縮!文字儲存於電腦當中,本質上就是ASCII或UTF-8二元碼。

語言壓縮

長話短說的壓縮,一般認為是文學的範疇。

原文       |壓縮     |失真壓縮|言簡意賅
如果你沒勇氣陪我到|若你畏懼陪我到|不愛我 |再見
明天的明天的明天 |大後天    |    |
倒不如就忘了就斷了|不如忘盡   |就忘了我|
寂寞的昨天的昨天 |寂寞的前天  |    |

資訊壓縮

古代人將壓縮和編碼視為相同,一般認為是文字學的範疇。

資訊壓縮是把抽象的資訊信息變成實際的碼。設立一種編碼方式,讓碼的長度越短越好,以三言兩語詮釋大千世界。

打個比方,白話文是不太理想的壓縮、文言文是更理想的壓縮;北京話是不太理想的壓縮、山東話是更理想的壓縮。

北京話      |台灣話    |閩南話   |四川話  |山東話
甲:是誰在樓下啊?|甲:誰在下面?|甲:啥咪郎?|甲:喇國?|甲:誰?
乙:是我在這兒唄!|乙:我在這裡!|乙:喜哇啦!|乙:使握!|乙:俺!
甲:你在做什麼咧?|甲:你在幹嘛?|甲:衝啥悔?|甲:昨傻?|甲:啥?
乙:我在這小便吶!|乙:我在小便!|乙:棒溜啦!|乙:潦瞭!|乙:尿!

除了文字可以當作碼,圖示、手語、表情也都可以當作碼。

Symbol / Code

資料通常很長。大家習慣逐段處理,符合電腦運作特性。

一段資料構成一個「符號」,再進一步變成簡短的「碼」。常見段落設定成符號,相同的符號對應相同的碼,有利於辨認。

制定符號:尚無最佳演算法,仍有研究空間。經典演算法是Lempel-Ziv Compression。

制定碼:已有最佳演算法,讓碼的總長度達到最小值!經典演算法是Arithmetic Compression、Huffman Compression。

兩者相互配合,產生了各式各樣的演算法:DEFLATEgzipbzip2zopflibrotli。有興趣的讀者請自行學習。

編碼與壓縮的差別:編碼時,符碼是公定的,符號長度是一個字元,碼長度是整數個byte;壓縮時,符碼是自訂的,長度不定。

【註:因為逐段處理,所以沒有活用到文字先後順序。】

何謂好的壓縮?

預先計算符碼,才能順利壓縮。符碼資訊,必須連同壓縮結果一併儲存,才能順利解壓縮。

所謂好的壓縮,就是讓「壓縮後長度」加「符碼資訊長度」少於「壓縮前長度」。

順帶一提,由於必須額外儲存符碼資訊,即便使用世上最好的壓縮演算法,檔案也可能越壓越大!比方說,已經壓縮過的資料再壓縮一遍,很容易產生這種情形。

Dictionary Compression

Dictionary Compression

用於制定符號。

常見單字、常見字根,當作符號。其餘部分則是一種字元當作一種符號。宛如查字典,通常以Trie作為字典的資料結構。時間複雜度O(N)。

text   | symbol
------ | ------
the    |   0
that   |   1
ing    |   2
is     |   3
ness   |   4
ion    |   5
less   |   6
ed     |   7
a      |   8
b      |   9
c      |   10
:      :   :
text       | symbol       int main() {
---------- | ------           int n = 1 + 1;
int        |   i              return 0;
main()     |   m          }
{          |   {                 ↓
           |   s          ims{
           |   t          tine1p1;
 +         |   p          tr
 =         |   a          }
return 0;  |   r                ↓
}          |   }          ims{⤶tine1p1;⤶tr⤶}
          |   ⤶          
:          :   :

Antidictionary Compression

http://www.stringology.org/DataCompression/dca/index_en.html

Lempel-Ziv Compression

Lempel-Ziv Compression

用於制定符號。有多種變形,共同精神是:

依序讀取字元。遇到生字,就加入字典,然後從零開始加長單字;遇到熟字,就繼續加長單字。

這個演算法基本上沒有什麼道理,但是效果卻不錯。也許裡面有什麼神奇的數學性質,不過我不清楚。

LZ77 / LZ78 / LZW

http://my.stust.edu.tw/sys/read_attach.php?id=58496

LZMA

http://en.wikipedia.org/wiki/LZMA

LZO

http://en.wikipedia.org/wiki/Lempel–Ziv–Oberhumer

Run-length Compression

Run-length Compression

用於制定符號。

aaaabbcabcbbbaaaa ---> a4b2c1a1b1c1b3a4

連續重複符號,精簡成兩個符號。時間複雜度O(N)。

先實施「Burrows-Wheeler Transform」讓相同符號盡量靠在一起,再實施Run-length Compression,可以提升壓縮效果。

UVa 11541 12547 ICPC 3867

Arithmetic Compression(Under Construction!)

Arithmetic Compression(Range Coding)

用於制定碼。

Compress

預先統計符號出現次數,才能順利地壓縮。

依序讀取符號,不斷切割區間,最後得到一個分數。分數換成二進位表示法,小數部分就是碼。

區間寬度設定為1。浮點數運算,遭遇精確度問題。

區間寬度設定為大數。大數運算,遭遇效率問題,況且我們無法預測數字需要多大。

區間寬度設定成整數。整數運算,沒有問題。概念上是從大數取一小段高位數來計算。除不盡就算了,不補零不再除。當位數幾乎用罄、無法分辨符號,才替換下一段高位數。

因為計算過程不夠精準,所以壓縮效果稍微差了一點,不過無傷大雅。時間複雜度O(N)。

Decompress

碼和符號出現次數必須一併儲存,才能順利地解壓縮。

依序讀碼,判斷位於哪個區間。時間複雜度O(N)。

符號長度固定為一個字元的版本。

不輸出二元碼、而是輸出可見符號的版本。

Information

照理來說應該要為大家介紹什麼是「訊息」,不過還是算了。

想讓「壓縮後長度」最短:符號出現次數越多,壓縮後訊息越少,令兩者成反比。訊息套用二進位表示法,即得二元碼。

consider symbol sequence: abaacadb

  min P(abaacadb)                             P() is information
=> min P(a) ⋅ P(b) ⋅ ... ⋅ P(d) ⋅ P(b)         independent events
=> min log₂(P(a) ⋅ P(b) ⋅ ... ⋅ P(d) ⋅ P(b))   binary code length

objective is minimum when P(a) : P(b) : ... = 1/#(a) : 1/#(b) : ...

由於只知道訊息比例,不知道訊息確切大小,取巧的方式是利用符號出現次數比例,取其小數做為二元碼。

符號出現次數越多,比例越大,小數位數越少,碼長越短。

symbol  count  ratio  binary  code  length  info ratio
------  -----  -----  ------  ----  ------  ----------
a       4      4/8    0.1     1     1       8/4
b       2      2/8    0.01    01    2       8/2
c       1      1/8    0.001   001   3       8/1
d       1      1/8    0.001   001   3       8/1

為了避免碼重複,比例求前綴和。

symbol  count  ratio  total  binary  code
------  -----  -----  -----  ------  ----
a       4      4/8    4/8    0.1     1   
b       2      2/8    6/8    0.11    11  
c       1      1/8    7/8    0.111   111 
d       1      1/8    8/8    1.0     0   

最後一個前綴和是1,二元碼是0,順序不漂亮。因此讓第一個前綴和是0。

symbol  count  ratio  total  binary  code
------  -----  -----  -----  ------  ----
a       4      4/8    0/8    0.0     0   
b       2      2/8    4/8    0.1     1   
c       1      1/8    6/8    0.11    11  
d       1      1/8    7/8    0.111   111 

比例可能除不盡。解法是保留足夠位數,足以分辨符號即可。

symbol  count  ratio  total  binary       code
------  -----  -----  -----  -----------  ----
a       1      1/6    0/6    0.0          0   
b       1      1/6    1/6    0.001010...  001 
c       2      2/6    2/6    0.01010...   01  
d       2      2/6    4/6    0.1010...    1   

最後講個八卦。此演算法是最好的壓縮演算法,然而此演算法最初是IBM公司的專利,大眾不得使用,造成許多遺憾。比如演算法課本,不得已改為介紹Huffman Compression。比如JPEG圖片、MPEG影片的標準規格,不得已改為採用Huffman Compression。

一旦習以為常,就難以回頭了。儘管現在專利已經過期,人人都能使用Arithmetic Compression;然而Huffman Compression卻依然荼毒著大家,成為歷史共業。

Timus 1307

Adaptive Arithmetic Compression

Adaptive Arithmetic Compression

adaptive是隨時視情況調整。dynamic是隨時改變過去輸入資料。online是隨時處理當前輸入資料。不要混淆囉。

壓縮、解壓縮的過程當中,不預先計算符號數量,而是即時更新符號數量。因此壓縮效果不如原始的Arithmetic Compression來得好。使用「Sequence」資料結構,時間複雜度O(NlogN)。

External Memory Algorithm。適合I/O速度很慢、資料量很大的情況。例如網路傳輸,一邊等待下載、一邊解壓縮,爭取時效。

Huffman Compression

Huffman Compression

用於制定碼。

Code Table

符號與碼的對應表,稱作「碼表」。

symbol  | code  | code length
------- | ----- | -----------
a       | 011   | 3
b       | 0011  | 4
c       | 11111 | 5

考慮abbacacc
a出現3次、b出現2次、c出現3次
壓縮後長度:3⋅3 + 4⋅2 + 5⋅3 = 9 + 8 + 15 = 32
碼表長度:3 + 4 + 5 = 12

替每種符號制定獨一無二的碼,碼長皆是整數,資料壓縮後可以明確區分符碼。

先前碼長是分數,此處碼長是整數。關係宛如Fractional Knapsack Problem和0/1 Knapsack Problem。因此壓縮效果不如Arithmetic Compression來得好。

現在要讓「壓縮後長度」與「碼表長度」都盡量短。

Code Tree

碼表的所有碼,存入Trie資料結構,得到「碼樹」。

二元碼的情況下,碼樹是二元樹:左樹枝是0、右樹枝是1。符號位於節點上;從樹根往符號的路線是其二元碼。

在二元樹上面安排各個符號的位置,就能產生一組二元碼,並且保證每個碼都相異。

一個碼千萬不能是另一個碼的開頭,以免解壓縮產生歧義。放到Code Tree上面來看就是:一個節點千萬不能是另一個節點的祖先。想解決這個問題,只要讓符號全部集中於樹葉!

Code Tree的樹葉深度總和,就是「碼表長度」。

碼長即樹葉深度。減少碼長即減少樹葉深度。碼長不斷減少,符號不斷挪往樹根,又要避免成為其他符號的祖先,最後符號都在樹葉,Code Tree形成滿二元樹。

調整滿二元樹的形狀,可以改變碼表長度。Code Tree長得越像完美二元樹,碼表長度就越短。

滿二元樹(full binary tree):
每個節點只有零個或兩個小孩的二元樹。

完美二元樹(perfect binary tree):
每片樹葉深度都一致的二元樹。亦是滿二元樹。

UVa 283 644

Code Tree的權重,刻意定義為「壓縮後長度」。

符號出現次數填入樹葉,做為權重。樹葉深度乘上權重,然後加總,定義為Code Tree的權重。

計算Code Tree的權重(Incremental Method)

深度相同的樹葉,可以一併累計權重,再一併乘上深度。逐層累計權重,就得到整棵樹的權重。

計算Code Tree的權重(Recursive Method)

滿二元樹每個內部節點都有兩個小孩。滿二元樹的最深的樹葉,一定有兩片樹葉互為兄弟。

刪除最深、互為兄弟的兩片樹葉,遞迴縮小問題。兩片樹葉權重相加,作為新樹葉的權重,進一步得到遞迴公式:

遞迴式:
原樹權重 = 新樹權重 + 左樹葉權重 + 右樹葉權重

化作一般式:
原樹權重 = 第一次刪除的左樹葉權重 + 第一次刪除的右樹葉權重 +
       第二次刪除的左樹葉權重 + 第二次刪除的右樹葉權重 +
                 ⋮
       第N-1次刪除的左樹葉權重 + 第N-1次刪除的右樹葉權重

Optimal Code Tree:降低壓縮後長度

Code Tree是哪一種形狀,權重才會最小呢?

根據方才的公式,Code Tree的權重取決於每次刪除的那兩片樹葉。每次刪除的那兩片樹葉權重越小,Code Tree權重就越小。

換句話說,優先聚合權重最小的兩個節點,最小的相加之後還是最小的,如此遞推下去,Code Tree權重就達到最小值,得到Optimal Code Tree。

以Priority Queue存放節點,就能迅速找出權重最小的兩個節點。總共2N-1個push,2N-2個pop,時間複雜度O(NlogN)。N是一開始的樹葉數目,也就是符號數目。

Optimal Code Tree:降低碼表長度

優先聚合碼長總和最小的兩個節點。

Compress

預先統計符號出現次數,預先建立碼表,才能順利地壓縮。

依序掃描符號,查碼表,將符號換成碼。時間複雜度O(N)。

Decompress

碼和碼表必須一併儲存,才能順利地解壓縮。

依序掃碼,同時從樹根開始往下走訪Code Tree。一旦走到樹葉,就將碼換成符號、回到樹根。時間複雜度O(N)。

UVa 240 10954 ICPC 5179 4122

Adaptive Huffman Compression

Adaptive Huffman Compression

不預先建立Optimal Code Tree。即時調整Code Tree的形狀,維持是Optimal Code Tree。

讀入一個符號,符號出現次數加一,Optimal Code Tree對應的樹葉權重加一,該樹葉的祖先們權重也都要跟著加一。

當有需要重新調整Optimal Code Tree的形狀,也就是指其中有一個節點權重加一之後,權重剛好超越了另一個節點的權重(換句話說,這些節點本來權重相同),導致另一個節點必須先聚合,權重加一的節點必須晚一點才能聚合,改變了Optimal Code Tree的形狀。

Code Tree排序所有樹葉

深度相同的樹葉互相對調,Code Tree權重不變。

權重小、位置淺的樹葉,權重大、位置深的樹葉,兩者對調,可讓Code Tree權重變小。

換句話說,權重小的樹葉儘量挪往深處,權重大的樹葉儘量挪往淺處,可讓Code Tree權重變小。

進一步來說,所有樹葉依照權重由小到大排序之後,依序由深到淺安排位置、同一層則隨意安排位置(或者是刻意由左到右安排位置),可讓Code Tree權重達到區域極小值。

Optimal Code Tree排序所有節點

Optimal Code Tree則是全部節點都能如此排序。建立Optimal Code Tree時,每次都是聚合權重最小的兩個節點,因而造就了排序的性質。

節點依照權重排序之後,就很容易搜尋了,能夠快速找到權重相同的節點們。

調整Optimal Code Tree

http://www.stringology.org/DataCompression/fgk/index_en.html

http://www.stringology.org/DataCompression/ahv/index_en.html

節點權重要加一之前,就先與權重相同的節點交換位置,盡量換到最上層、最右端的位置,也就是盡量換到最靠近次大權重值的位置;這個交換不會影響Optimal Code Tree的權重、仍是Optimal Code Tree。如此一來,權重加一之後,不需要改變Code Tree的形狀,仍是Optimal Code Tree;而且所有節點依然是排序好的。

別忘記該樹葉的祖先們,權重也都要加一。採用遞增法,一步一步處理:樹葉權重加一之後,再處理父親權重加一的問題。

我不清楚如何得到碼表長度最短的Optimal Code Tree。

Hu-Tucker Compression

Alphabetic Code Tree

符號必須由小到大、從左往右排列。

特色是:符號的大小順序,就是碼的大小順序。符號比大小,就是碼比大小──可以直接使用壓縮之後的資料比大小。

有一好就有一壞,壓縮效果比起Huffman Compression就遜色了一點。

Alphabetic Code Tree的權重

與Code Tree的權重定義相同。

計算Code Tree的權重(更玄的Recursive Method)

先前計算Code Tree的權重,是刪除深度相同、互為兄弟的兩片樹葉;關注節點之間的高度關係、父子關係。

其實還有另外一種計算方式,是改為刪除深度相同、但是不一定要互為兄弟的兩片樹葉;改為關注高度關係、無視父子關係。最後得到類似的遞迴公式:

遞迴式:
原節點集合 = 新節點集合 + 一片樹葉權重 + 另一片樹葉權重

化作一般式:
原樹權重 = 第一次刪除的樹葉權重 + 第一次刪除的另一片樹葉權重 +
       第二次刪除的樹葉權重 + 第二次刪除的另一片樹葉權重 +
                 ⋮
       第N-1次刪除的樹葉權重 + 第N-1次刪除的另一片樹葉權重

Optimal Alphabetic Code Tree

http://www.cs.rit.edu/~std3246/thesis/node10.html

http://cseweb.ucsd.edu/classes/wi06/cse202/notes-feb09.pdf

優先聚合權重最小的兩個節點,Alphabetic Code Tree的權重就會達到最小值,就和Optimal Code Tree一樣。

但是Alphabetic Code Tree限定了樹葉的左右順序,所以每次聚合的兩個節點,如果剛好都是樹葉的話,就只能是相鄰的樹葉──如此才能維持符號的左右順序。

只有樹葉必須擔心符號順序問題;樹葉一旦經過聚合之後,就不必再擔心順序問題,也不再隔開其他樹葉。

一、統計各個符號的出現次數。
二、一開始有N個樹葉(節點),權重設定成符號出現次數。
  現在以bottom-up方式建立Optimal Alphabetic Code Tree:
 甲、兩個權重最小的節點(不能是被隔離的兩片樹葉),相加得到新節點的權重。
   此時確立了這兩個節點的深度相同(不見得互為兄弟),
   同時確立了新節點深度比它們淺一層(不見得是它們的父親)。
 乙、聚合N-1次就得到樹根了,不過只能確立所有節點的高度關係。
   得到Optimal Alphabetic Code Tree的權重。
 丙、以top-down方式,按照高度關係,確立所有節點的父子關係。
   即形成Optimal Alphabetic Code Tree。

時間複雜度為O(NlogN)。不過實作比較複雜。

【待補程式碼】

相似的樹

這三棵樹非常相似,都是「深度」乘上「符號出現次數」,令總和最小。

Optimal Binary Search Tree
所有節點都有符號出現次數,節點的位置必須按照大小排列順序。O(N²)。

Optimal Alphabetic Binary Code Tree
只有樹葉擁有符號出現次數,樹葉的位置必須按照大小排列順序。O(NlogN)。

Optimal Binary Code Tree
只有樹葉擁有符號出現次數,樹葉的位置順序隨意。O(NlogN)。

實務上,符號種類數目通常很少,亦可運用OBST的O(N²)演算法,求得OABT;程式碼結構簡單,執行時間也比較短。

UVa 12057 PKU 1738

延伸閱讀:Garcia-Wachs Algorithm

http://www.math.tau.ac.il/~haimk/seminar00/dana-MCBT.ppt

演算法簡單很多,但是證明也複雜很多。