Bo2SS

直觀了解哈夫曼樹和哈夫曼編碼，證明哈夫曼編碼是最優的變長編碼

課程內容#

前置知識#

• 什麼是編碼
  • 最先聽到編碼是在什麼地方？ASCII 碼
    • 'a' = (97)10 = (0110 0001)2
    • '0' = (48)10 = (0011 0000)2
    • 8 位二進制編碼，一字節
  • 注意：在計算機中，任何信息都是用二進制存儲的
  • 編碼的作用：人類字符到計算機字符的映射
• 舉例：編碼長度帶來的影響
  • 計算機中有一段信息："aa00"，其ASCII 編碼為：01100001 01100001 00110000 00110000
  • 此時，將該信息從一台計算機傳輸到另外一台計算機
    • 在網絡中，最小的傳輸單位是比特位 [bit]，所以 "aa00" 需要傳輸 32 個 bit
  • 假設：某計算機的網速是 32bit/s，則用時為：1s
  • 👇
  • 轉換到特殊場景：只有 a、b、0、1 四種字符需要傳輸
  • 則可設計新的編碼方式 [海賊班編碼 - 定長編碼]
    • 用 2 位二進制區分它們 ——a: 00，b: 01，0: 10，1: 11
  • 此時，"aa00" 的表示只需要 8 個 bit
  • 所以，在網速不變的情況下，當前傳輸的用時只需：0.25s
  • [PS] 相比騰訊會議，Zoom 的編碼解碼更精細化，所以相同網速下 Zoom 體驗更好

定長與變長編碼#

• 定長編碼 —— 對於每個字符，編碼長度相同
  • ASCII 碼和特定場景下的海賊班編碼，都屬於定長編碼
  • [PS] UTF-8— 變長編碼；UTF-16— 是定長編碼 [自學]
• 變長編碼 —— 對於每個字符，編碼長度不相同
• 變長編碼，一定不差於定長編碼
  • 定長編碼，是變長編碼的特例
• 【引申理解】
  • 變長編碼可以就是定長編碼
  • 變長編碼需針對特定場景做優化 [傳輸字符的出現概率是需要提前統計好的]
  • 編碼可以看成是一種協議，提前規定好了，而不能是動態變化的
  • 編解碼需保持一致

變長編碼的應用場景#

• 特定場景
  • 只有四種字符：ab01
  • 每個字符出現的概率不同 ——a: 0.8，b: 0.05；0: 0.1；1: 0.05
• 平均編碼長度
  • avg(l) = ∑ li × pi
  • li：第 i 種字符的，編碼長度
  • pi：第 i 種字符的，出現概率
  • 實際上就是編碼長度的期望值
  • 舉例
    • 假設平均編碼長度為 1.16，則傳輸 100 個字符，需要傳輸 116 個比特位 [估算]
    • 海賊班編碼 [見上] 的平均編碼長度：avg (l) = 2 × ∑ pi = 2
      • 定長編碼的平均編碼長度就是定長
• 新・海賊班編碼
  • a：1
  • b：01 [注意：不能以 1 開頭，因為解碼時會和 a 衝突，❌前綴重疊]
  • 0：000
  • 1：001
  • 此時，平均編碼長度：1 * 0.8 + 2 * 0.05 + 3 * 0.1 + 3 * 0.05 = 1.35
  • 所以，傳輸 100 個字符，只需傳輸 135 個比特位 [估算]
• [PS] 概率越大的字符對應越短的編碼長度

哈夫曼編碼#

1. 先統計得到每一種字符的概率
2. 將 n 個字符，建立成一棵哈夫曼樹
3. 每一個字符都落在葉子結點上 [不會前綴重疊]
4. 按照左 0、右 1 的形式，將編碼讀取出來

• 建樹舉例
  • 
  • 建樹過程口诀：每次拿出概率最小的兩個字符作為結點，合成一棵子樹 [產生新的結點]
  • ⭐因為所有字符都落在葉子結點上，所以沒有任何一個編碼是其它字符的編碼前綴
    • 沒有衝突
  • 此時，平均編碼長度位為 1 * 0.8 + 3 * 0.05 + 2 * 0.1 + 3 * 0.05 = 1.3
• 結論：哈夫曼編碼是最優的變長編碼 [下面給出證明]
• [PS]
  • 主要關注長度，01 的左右不太關注
    • 若要關注，則考慮 0、1 的傳輸成本誰更高
  • 哈夫曼樹不唯一，概率相等的時候順序隨意
  • 哈夫曼編碼也可退化為定長編碼 [同理，比如編碼 4 個等概率 (0.25) 的字符]

證明哈夫曼最優#

[變長編碼中的大哥，最優指的是平均編碼長度最小]

步驟：① 轉換平均編碼長度的表示；② 求解公式最優解

思維轉換#

• 
• 對於哈夫曼編碼過程，如果紅色結點對應了一個字符，則下面的 4 個葉子結點都要被砍掉
• 否則，就會發生衝突
• [從直覺上，也是事實] 哈夫曼編碼會覆蓋所有的葉子結點
• 假設有 4 個字符，其編碼結果如下 [紅色結點]
  • 
  • 可知，高度為 H [從 0 開始] 的樹，第 l 層的結點覆蓋的葉子結點數為 2 ^ (H - l)
    • 第 l 層的 l 其實代表的就是編碼長度
    • 越往上的結點覆蓋的結點數量越多，越往下的反之
• 👇
• 第 i 個字符的編碼長度 [左] 和對應結點所覆蓋的葉子結點數 [右] 之間存在映射，如下：
  • li → 2 ^ (H - li)

隱含的約束條件#

• 
• 對第二個式子的左右兩邊，同時除以 2 ^ H
• [PS] 哈夫曼樹的第二行式子一定是等號，但先不要著急

證明目標轉換#

• 使平均編碼長度 Σ pi * li 最小，li = -li'
• 約束來自於上面的樹形結構 [即隱含的約束條件]
• 
• 再令 Ⅰi = 2 ^ li'
• 即讓目標和約束都再做轉換
• 【轉換結果】
  • 目標：使 -(p1logⅠ1 + p2logⅠ2 + p3logⅠ3 + ... + pnlogⅠn) 最小
  • 約束：Ⅰ1 + Ⅰ2 + Ⅰ3 + ... + Ⅰn <= 1
• [PS]
  • 有點像熵？其實就是從熵的角度證明，還可以引出交叉熵的概念
  • 轉換是為了什麼？
    • 推導出約束條件的等號成立與目標最小的關係
    • 還有一個限制條件：概率和為 1

約束條件再縮小#

• 證明：當目標函數達到最小時，約束條件一定 = 1
• 反證法：即約束條件 < 1
  • 令 1 - ∑Ⅰi = Ⅰx'，其不為負 [看約束條件]
  • 
  • Ⅰx' 可以加到任意項上
  • 只要 Ⅰx' 不為 0，那麼目標函數就一定不是最小，還能小
  • 所以約束條件一定 = 1

求偏導等於 0 得極值#

• 
• 減少一個未知量：Ⅰn = 1 - Ⅱ
• 什麼時候目標達到最小值：求偏導
  • 求偏導可得左邊式子
  • 
  • 即得右上角式子，其成立時，目標可以達到最小值
  • 令 p1/Ⅰ1 = ... = k，又已知約束條件和概率和為 1 得兩個條件，可得 k = 1
  • ⭐所以 pi = Ⅰi

❗ 思考#

平均編碼長度與熵、交叉熵的關係

• pi = Ⅰi
  • Ⅰi 與編碼長度 li 相關，也就是概率和長度密切相關
    • 概率越大，編碼長度越短
  • 將等式代入，可得【熵】的公式
    • 其實，熵代表的是在一個系統中，要表示一些信息，所需的最小的平均表示單元
    • 同樣，也可以理解為平均編碼長度 [⭐思想連通]
    • 平均編碼長度越長 → 系統中的字符數量越多 → 系統的狀態越多 → 系統越混亂
    • 熵越大代表系統的編碼越混亂
  • 【交叉熵】
    • 把 pi 和 Ⅰi 都看成是一組概率
    • 其描述的是兩個概率向量的相似程度
• 其實證明還不是很嚴謹
  • 因為哈夫曼過程其實是離散的，而此證明過程是連續的
  • 如：pi = Ⅰi，通過 Ⅰi 算出的編碼長度 li 可能是小數，但編碼長度 li 實際上肯定是整數

代碼演示#

哈夫曼樹#

• 
• 
• 
• 結構基於樹
• 【關鍵操作】
  • 合併結點，可建立結點之間的關係 [數組與結點關係之間的轉換]
  • 找最小的 2 個概率 [可利用優先隊列優化]
  • 遞歸提取編碼 [只有葉結點才對應字符編碼]
  • 讀入數據時建議使用字符數組存儲字符，可減少出錯率

附加知識點#

• 計算機中，最基本 [最小] 的存儲單位是字節，最基本 [最小] 的數據表示單位是 bit 位

思考點#

• 哈夫曼是最優編碼的其它證明方式？
  • 058 哈夫曼算法的正確性證明——Coursera
  • 最簡單的哈夫曼樹是最優二叉樹證明方法—— 知乎

Tips#

• 數學知識決定計算機方向的上限