JPEG 中的正規化哈夫曼編碼

作者：由黃兢成發表于曲藝時間：2019-07-03

各小節：

概述

自適應的哈夫曼編碼

正規化哈夫曼編碼（Canonical Huffman Code）

JPEG 檔案格式

DHT 資料例子

Show me the code

編碼過程

哈夫曼查詢表

概述

哈夫曼（Huffman）壓縮是個經典的演算法，在網上可以找到很多文章。將資料拆分成一個個符號（Symbol，符號可以是字元或者位元組），統計每個符號出現的頻率，根據頻率構建出二叉樹。之後根據二叉樹，為每個符號值分配二進位制位編碼，頻率越高，編碼的二進位制位越短，從而實現壓縮。

要想正確解碼，除了要儲存編碼後的二進位制位，還需要儲存編碼樹資訊。這樣解碼器才能知道符號值和編碼值的對應關係。

注: 此文“編碼樹”一詞，不一定真的是二叉樹，其實是指“符號值和編碼值的對應關係”。只是“編碼樹”一詞簡短些，但有點不夠精確，特此註明。

可以有很多方法儲存編碼資訊。比如依次儲存（符號值，頻率值），可以還原出二叉樹，也就還原出編碼資訊。或者依次儲存（原始值，編碼值），或者將二叉樹序列化。但這些方法不夠高效。

假如儲存編碼樹本身就佔太多資料，對於小量資料的壓縮，壓縮後總資料量反而會更大，就得不償失了。

要真正應用哈夫曼壓縮，其中一個關鍵的問題，就是如何用盡量少的資料儲存編碼樹資訊。很多講述哈夫曼編碼的文章都忽略了這個問題。

自適應的哈夫曼編碼

最節省資料的儲存方式，就是根本不儲存。

一種方式，是編碼器和解碼器，使用事先約定好的編碼樹。編碼樹資訊直接嵌在編碼器和解碼器的原始碼當中，這樣壓縮資料中就不需要再儲存。比如英文文字，根據歷史文獻，事先統計出各字母的頻率，以後就用這個約定好的頻率表壓縮和解壓英文小說。但這種方式只能針對特定的資料，並不具有通用性。

另一種方式，是使用自適應的哈夫曼編碼。自適應編碼的大致流程如下：

init_model

（）

{

symbol

get_symbol

（

input

）

code

encode

（

symbol

）

write_code

（

code

，

ouput

）

update_model

（

symbol

）

}

while

（

！

isEnded

（

symbol

））；

首先初始化模型，之後獲取符號，編碼符號後再動態更新模型。自適應解碼的大致流程類似：

init_model

（）

{

code

get_code

（

input

）

symbol

decode

（

code

）

write_symbol

（

symbol

，

output

）

update_model

（

symbol

）

}

while

（

！

isEnded

（

code

））

在編碼解碼過程中，動態更新模型，也就不需要儲存模型。

對於自適應的哈夫曼編碼，這個模型就是哈夫曼編解碼所需的頻率二叉樹。使用自適應編碼，不需要儲存編碼樹資訊，但需要經常更新編碼樹，會導致時間開銷增大。

儲存哈夫曼編碼資訊，最常用的是使用正規化哈夫曼編碼。

正規化哈夫曼編碼（Canonical Huffman Code)

正規化哈夫曼編碼最早由 Schwartz（1964）提出，Canonical 這個詞是規範化，遵守一定標準的意思。正規化哈夫曼編碼，是哈夫曼編碼的一個子集。其基本思想，是對哈夫曼編碼施加某些強制約定，讓其遵守一些規則，之後根據規則，使用很少的資料便能重構出編碼樹。

為了完整，摘抄自維基百科範氏霍夫曼編碼

正規化霍夫曼編碼要求相同長度編碼必須是連續的，例如：長度為4的編碼0001，其他相同長度的編碼必須為0010、0011、0100。。。等等。為了儘可能降低儲存空間，編碼長度為

的第一個符號可以從編碼長度為

的最後一個符號所得知，即

$c_{j} = 2(c_{j-1} + 1)$

，例如：從長度為3的最後一個編碼100，可推知長度為4的第一個編碼為1010。最後，最小編碼長度的第一個編碼必須從0開始。正規化霍夫曼編碼透過這些原則，便可以從每個編碼還原整個霍夫曼編碼樹。

從中總結出三個規則：

最小編碼長度的第一個編碼必須從0開始。

相同長度編碼必須是連續的。

編碼長度為

的第一個符號可以從編碼長度為

的最後一個符號所得知，即

$c_{j} = 2(c_{j-1} + 1)$

。

上面這些話，我每個字都看得懂，合起來卻根本不知道它在說什麼。

當不明白理論究竟在說什麼時，一個好方法是去分析具體的例子。JPEG 就用到了正規化哈夫曼編碼，我們繞點遠路，先去分析 JPEG 的哈夫曼編碼，再回頭弄懂這個演算法。

JPEG 檔案格式

JPEG 檔案格式，可以拆分成一個個分割槽。

SOI（Start of Image， 0xFF + 0xD8）

section 0

section 1

section 2

section 3

。。。。

section N

EOI（End of Image， 0xFF + 0xD9）

每個分割槽基本格式為：

0xFF + Tag（標記）

data length（資料長度）

data （具體資料）

當 Tag 為 0xC4，表示 DHT（Difine Huffman Table），用於儲存哈夫曼編碼表，就是上面說的正規化哈夫曼編碼。

DHT 資料例子

我摘抄了一段 DHT 資料，共有 57 個位元組，十六進位制如下。

ff c4 0 37 11 0 2 2 2 1

3 2 5 2 4 5 5 0 3 0

0 1 2 0 3 4 11 21 5 12

31 13 41 6 22 32 51 61 14 71

23 81 91 a1 15 42 b1 c1 d1 7

33 52 e1 f0 24 62 f1

最前面 5 個位元組跟編碼沒有關係，可以直接跳過。但為完整，也描述其含義。

這些資料前面 2 個位元組（ff c4）表示這段資料是 DHT， DHT 的 Tag 為 0xc4。

接下來 2 個位元組（0 37）表示資料長度，十六進位制的 0x37 就是十進位制的 55。總長度 57 減去前面 2 個位元組的 Tag，就等於長度 55。

接下來的 1 個位元組（11），高 4 位為 1，表示 AC（交流）哈夫曼表。低 4 位表示哈夫曼表的 ID，這裡 ID 為 1。

接下來就是關鍵資料了，用於儲存哈夫曼編碼表。

為了方便描述，我們用 Symbol（符號）這個詞表示編碼前的原始值，用 Code（編碼）表示哈夫曼編碼後的二進位制資料。哈夫曼編碼後是個二進位制位串，用 Code Length 來表示二進位制位數。下面的這批資料。

0 2 2 2 1

3 2 5 2 4 5 5 0 3 0

0 1 2 0 3 4 11 21 5 12

31 13 41 6 22 32 51 61 14 71

23 81 91 a1 15 42 b1 c1 d1 7

33 52 e1 f0 24 62 f1

其實描述了這個表格。

Code length | Number | Symbol

——————-+————+——————

1 bit | 0 |

2 bits | 2 | 0x01 0x02

3 bits | 2 | 0x00 0x03

4 bits | 2 | 0x04 0x11

5 bits | 1 | 0x21

6 bits | 3 | 0x05 0x12 0x31

7 bits | 2 | 0x13 0x41

8 bits | 5 | 0x06 0x22 0x32 0x51 0x61

9 bits | 2 | 0x14 0x71

10 bits | 4 | 0x23 0x81 0x91 0xa1

11 bits | 5 | 0x15 0x42 0xb1 0xc1 0xd1

12 bits | 5 | 0x07 0x33 0x52 0xe1 0xf0

13 bits | 0 |

14 bits | 3 | 0x24 0x62 0xf1

15 bits | 0 |

16 bits | 0 |

DHT 資料前 16 個數字描述 Code Length 的個數（Number），編碼後不可能是 0 Bit，就從 1 Bit 開始數。後面是具體的 Symbol 值，根據個數，依次填入表格項中。

這個表格值儲存了 Code 的位數，是在說，

0x01 0x02，編碼後的 Code 有 2 位。

0x00 0x03，編碼後的 Code 有 3 位。

0x04 0x11，編碼後的 Code 有 4 位。

但是就算我們知道了 Code 的位數，但還不知道 Code 本身啊？

前文說過，“正規化哈夫曼編碼，其基本思想，是對哈夫曼編碼施加某些強制約定，讓其遵守一些規則，之後根據規則，使用很少的資料便能重構出編碼樹”。現在輪到規則出場了。

規則 1

最小編碼長度的第一個編碼必須從 0 開始。

上表中，最短編碼長度為 2 Bits，從 0 開始。於是第 1 個 Symbol（0x01）編碼就為 00。

Symbol（十六進位制） | Code（二進位制）

————————-+————

0x01 | 00

規則 2

相同長度編碼必須是連續的。

第 2 個 Symbol（0x02）編碼長度也是 2 Bits。要連續，就是 00 + 1 = 01。於是

Symbol（十六進位制） | Code（二進位制）

————————-+————

0x01 | 00

0x02 | 01

規則 3

編碼長度為

的第一個符號可以從編碼長度為

的最後一個符號所得知，即

$c_{j} = 2(c_{j-1} + 1)$

。

這裡的

$c_{j} = 2(c_{j-1} + 1)$

就是

$(c_{j-1} + 1) << 1$

，乘以 2 相當於向左移位。

因為 2 bits 最後的 Code = 01，因此 3 Bits 第一個

（01 + 1） << 1

，就為

（10 << 1） = 100

。注意上面計算是二進位制。因此

Symbol（十六進位制） | Code（二進位制）

————————-+————

0x01 | 00

0x02 | 01

0x00 | 100

根據正規化哈夫曼編碼的規則，依次類推，還原出 Symbol 和 Code 的對應表。

Symbol（十六進位制） | Code（二進位制）

————————-+————

0x01 | 00

0x02 | 01

0x00 | 100

0x03 | 101

0x04 | 1100

0x11 | 1101

0x21 | 11100

0x05 | 111010

。。。 | 。。。

0xf0 | 111111111110

0x24 | 11111111111100

0x62 | 11111111111101

0xf1 | 11111111111110

有一個例外情況需要說明，13 Bits 最後一個 Symbol， 0xf0 的 Code 為 111111111110。但之後沒有 14 Bits，直接跳到 15 Bits。這時向左移位就不是移 1 位，而是移 2 位。規則 3 修正為

$c_{j} = (c_{j-k} + 1) << k$

。

於是 15 Bits 的第一個符號 0x24 的 Code 為（111111111110 + 1） << 2 = 11111111111100。

Show me the code

上面描述似乎很複雜，其實程式碼很簡單，核心程式碼就幾行。下面程式碼從 JPEG 的 DHT 中打印出 Symbol 和 Code 的對應關係，就是上面的表格。

#include

static

const

char

to_binary_str

（

int

code

，

int

n_bits

，

char

buf

［

］）

{

int

mask

（

n_bits

）；

for

（

int

；

n_bits

；

）

{

（

code

mask

）

{

buf

［

］

‘1’

；

}

else

{

buf

［

］

‘0’

；

}

mask

>>=

；

}

buf

［

n_bits

］

；

return

buf

；

}

int

main

（

int

argc

，

const

char

argv

［］）

{

// clang-format off

const

int

DHT

［］

{

0xff

，

0xc4

，

0x00

，

0x37

，

0x11

，

0x00

，

0x02

，

0x02

，

0x02

，

0x01

，

0x03

，

0x02

，

0x05

，

0x02

，

0x04

，

0x05

，

0x05

，

0x00

，

0x03

，

0x00

，

0x00

，

0x01

，

0x02

，

0x00

，

0x03

，

0x04

，

0x11

，

0x21

，

0x05

，

0x12

，

0x31

，

0x13

，

0x41

，

0x06

，

0x22

，

0x32

，

0x51

，

0x61

，

0x14

，

0x71

，

0x23

，

0x81

，

0x91

，

0xa1

，

0x15

，

0x42

，

0xb1

，

0xc1

，

0xd1

，

0x07

，

0x33

，

0x52

，

0xe1

，

0xf0

，

0x24

，

0x62

，

0xf1

，

}；

// clang-format on

const

int

numbers

DHT

；

const

int

symbols

numbers

；

char

buf

［

］；

int

code

；

for

（

int

；

）

{

int

num

numbers

［

］；

int

n_bits

；

for

（

int

；

num

；

）

{

int

symbol

symbols

；

printf

（

“0x%0。2x | %s

”

，

symbol

，

to_binary_str

（

code

，

n_bits

，

buf

））；

code

；

symbols

；

}

code

<<=

；

}

return

；

}

編碼過程

上面描述了正規化哈夫曼的解碼過程，用很少量的資料就還原出 Symbol 和 Code 的對應關係。理解了解碼過程，編碼過程就相對簡單了。下面例子見範氏霍夫曼編碼。

首先按照經典的哈夫曼編碼，得到一個對應關係

F：000

O：001

R：100

G：101

E：01

T：11

再按照編碼長度排序，這裡也按照字母排序了，其實只要按照長度排序就行了。

E：01

T：11

F：000

G：101

O：001

R：100

之後按照三個規則，重新給每個符號分配新的編碼。

第一個符號的編碼方式是依照符號的編碼長度給予相同長度的‘0’值

對接下來的符號的編碼+1，保證接下來的編碼大小都大於之前

如果編碼較長，位元左移一位並補0

E：01 → 00 按照1。

T：11 → 01 依照2。

F：000 → 100 依照2。&3。

G：101 → 101 依照2。

O：001 → 110 依照2。

R：100 → 111 依照2。

經過給符號重新編碼後，就規範化了。之後只需要儲存 Symbol 的編碼長度，不用儲存 Code 本身。就大大節省了資料量。

哈夫曼編碼的關鍵在於，頻率越高，編碼的二進位制位越短，而具體的編碼到底是多少，其實是沒有所謂的。經過規範化後，正規化哈夫曼編碼的 Code 跟原來不同了，但長度保持一致，壓縮效率跟原來一樣。但卻可大大節省儲存編碼樹本身的資料量。

哈夫曼編碼後，二進位制位資料是連續的，中間沒有分隔符。需要保證各個符號編碼不會衝突，也就是說，不會存在某一個編碼是另一個編碼的字首。

正規化哈夫曼編碼規則 1，從 0 開始，保證有個起點。2、3 是遞增規則，描述瞭如何從前面的 code 得到後面的 code。有起點，有遞增規則，就可不斷地生成新的編碼（聯想到數學歸納法）。而 2、3 的遞增規則，也保證了規範後的編碼不會衝突，不會存在某一個編碼是另一個編碼的字首。

哈夫曼查詢表

哈夫曼解碼，還有一個細節可以討論。

得到了 symbol 和 code 的對照表，可以重新構造二叉樹，每次讀取一位來遍歷二叉樹。每次到達葉節點就解碼出一個 Symbol。但這種方式需要重新構造二叉樹，並且每次只能解碼一位。

其實不一定非要重新構造二叉樹，也可以將對照表依次儲存起來。比如

Symbol | Code | Bit Length

————-+————+——————-

0x01 | 00 | 2

0x02 | 01 | 2

0x00 | 100 | 3

0x03 | 101 | 3

0x04 | 11000 | 5

0x11 | 110010 | 6

0x21 | 110011 | 6

。。。 | 。。。 | 。。。

解碼的時候，依次嘗試表格中每一項。但這樣迴圈遍歷，對應表格越大，就會越慢。

哈夫曼快速解碼時，經常會使用查詢表（Lookup table）。

哈夫曼編碼有個特點，某一個編碼不可能是另一個編碼的字首。假如某一個 Symbol 的 Code 為 01，就不可能出現另一個 Symbol 的 Code 為 010。因為二進位制位資料是連續的，如果同時出現 Code 為 01 和 010，就會導致解碼混亂。哈夫曼編碼不可能出現這種情況。

利用這個特性，我們可以構建出查詢表。比如下面的對照表。

Symbol | Code | Bit Length

————-+————+——————-

A | 00 | 2

B | 01 | 2

C | 100 | 3

D | 101 | 3

根據對照表，字串 “ADBCD” 的編碼為

0010101100101

解碼是要從 Code 找到 Symbol，這裡最大的 Bit Length 為 3，我們去構造出 3 位的查詢表。3 位的表格有 2 ^ 3 = 8 項，如下。

Code | Symbol | Bit Length

——-+————+——————-

000 | A | 2

001 | A | 2

010 | B | 2

011 | B | 2

100 | C | 3

101 | D | 3

110 | 0xFF | 0

111 | 0xFF | 0

注意查詢表中，Code 為 000 和 001 都直接對應 Symbol A。這是因為 A 的 Code 為兩位的 00，不可能出現其他字首相同的編碼，就可以將 000 和 001 都分配給 A。其中 B 的情況類似。而 110 和 111 沒有對應的編碼， Bit Length 就為 0，表示找不到的情況。

另外注意到，查詢表中，Code 是按順序來排列的。實際程式中 Code 就相當於陣列的索引，可以直接定位，因此 Code 不需要真正儲存。

有了查詢表，我們來解碼

0010101100101

。

讀取 3 位為 001，使用 001 作為索引，定位到查詢表的項，知道真正的 Bit Length 為 2。於是解碼出 ‘A’，解碼器前進 2 位，剩餘

10101100101

。

讀取 3 位為 101，使用 101 作為索引，定位到查詢表的選項。於是解碼出 ‘D’，解碼器前進 3 位，剩餘

01100101

。

讀取 3 位為 011，解碼出 ‘B’，解碼器前進 2 位，剩餘

100101