從哈夫曼編碼再出發：原理和現實
- 2020 年 8 月 19 日
- 筆記
title: 從哈夫曼編碼再出發：原理和現實
tags:
- 哈夫曼
- 編碼
- 投資
categories:
- 總結感悟
對於電腦科班出身的人來說，在大學階段幾乎都學過資訊理論和演算法這兩門課，資訊理論都會講到香農三大定理以及哈夫曼編碼，演算法課上會學習二叉樹，甚至哈弗曼樹。在介紹哈夫曼編碼之前，先介紹一下什麼是有效編碼，以及香農第一定理的內容。
一個好的有效編碼需要遵循兩個基本原則：
- 易辨識
- 有效性
那麼怎樣才能做到有效編碼呢？下面有一個問題：
用10根手指頭，能表達多少個數字？
常見的回答有以下兩種：
- 能表達10個數字，因為小孩子數數的時候就是掰著指頭數的。
- 能表達100個數字，因為我們平時能用一隻手就能做出10個形狀，也就是能數10個數，將兩隻手組合起來，一個表示十位，一個表示個位，就能表示從0到99共100個數字
第一個回答最直觀，第二個回答其實就利用了編碼的知識。
但是這依然不是最有效的編碼，如果我們考慮採用二進位，而不是十進位進行編碼，則能表示1024個不同的數字。
具體的做法是這樣的，把10個手指並排在一起，從左到右依次給手指編號，編碼為0~9。每一個手指頭都有伸出和收起兩種狀態。每一種狀態對應於一位二進位，十個手指頭就能表示10位二進位，也就是2的10次方，也就是1024種數字。
當然也有人覺得可以讓每個手指具有伸開、半伸開、收縮三個狀態，表示3的10次方也就是59049中數字。雖然這種想法也是正確的，但是過分強調有效性，而忽視了易辨識這個原則，凡事過猶不及。
常見的比較有效的編碼有阿拉伯數字，莫爾斯電碼以及電腦中根據電路狀態演化的二進位編碼。
一個有效的編碼是否就是最優編碼呢，答案當然是不一定。香農第一定理告訴我們編碼長度是有理論最小值的，摘錄資訊理論這本書中的公式如下：
編碼長度 ≥ 資訊熵(資訊量) / 每一個碼的資訊量
香農對此做出了嚴格的數學證明，同時還證明，只要編碼系統設計得足夠巧妙，上面的等號是成立的。
我們以二進位編碼為例來說明這個公式，為了預測世界盃冠軍，我們先對世界盃的32隻球隊編碼，那如何編碼才能使得編碼長度最短呢？對於這樣的n選1的問題，根據香農第一定理，32選1的資訊熵為log32=5比特（以2為底的對數），每個編碼的資訊量為1比特，根據公式最短編碼長度為5。如果編碼長度小於5，那麼傳遞出去的資訊就一定包含不確定性，也就是有損資訊、失真資訊。
至於資訊熵的計算為什麼是以2為底的對數，可以參考分治思想。
如果我們對經常出現的字母採用較短的編碼，對不常見的字母採用較長的編碼，根據常識，這樣是能夠降低編碼的整體長度的。在莫爾斯電碼中，我們會發現26個英文字母中的5個母音字母aeiou的編碼長度是最短的。如果對英文26個字母採用等長度的編碼，比如進行二進位編碼，需要log26，就是5比特資訊。而採用莫爾斯的編碼方式，平均只需要3比特，這樣效率就提升了很多。
在中國，北京和上海等重要城市的長途電話區位碼就是兩位，小城市就使用3位，比如北京是010，上海是021，而江蘇常州是0519（所有都忽略掉前面的0），這樣做的目的就是為了減少平均的編碼長度。
那怎樣才能找到最有效的二進位編碼呢？哈夫曼在《A Method for the Construction of Minimum-Redundancy Codes》這篇論文中發表了基於自底向上的有序頻率二叉樹的編碼方法，並很快證明了這個方法是最有效的。
關於哈夫曼樹的構建過程可以參加文末的參考中的Wikipedia鏈接，此處只做一個簡單描述：
假設我們要給一個英文單字“F O R G E T”進行哈夫曼編碼，而每個英文字母出現的頻率分別列在下圖中。
進行霍夫曼編碼前，我們先創建一個霍夫曼樹。
- 將每個英文字母依照出現頻率由小排到大，最小在左，如上圖。
- 每個字母都代表一個終端節點（葉節點），比較F.O.R.G.E.T六個字母中每個字母的出現頻率，將最小的兩個字母頻率相加合成一個新的節點。
- 比較5.R.G.E.T，發現R與G的頻率最小，故相加4+4=8。
- 比較5.8.E.T，發現5與E的頻率最小，故相加5+5=10。
- 比較8.10.T，發現8與T的頻率最小，故相加8+7=15。
- 最後剩10.15，沒有可以比較的對象，相加10+15=25。
最後產生的樹狀圖就是霍夫曼樹，如下圖。
給霍夫曼樹的所有左節點’0’與右節點’1’，從樹根至樹葉依序記錄所有字母的編碼，如下圖。
哈夫曼編碼從本質上講，是將最寶貴的資源（最短的編碼）給出現概率最大的資訊。我們可以在任何需要分配資源的工作中利用哈夫曼編碼的思想。
在風險投資領域，利用哈夫曼編碼原理投資就是一套比較有效的系統方法。假定你有一大筆錢可以用於風險投資，怎樣投資效果最好？下面有三種做法：
- 平均的投入到100個初創公司
- 利用自己的眼光投入到一家最可能的公司中
- 利用哈夫曼編碼進行投資
第一種方法，過於平均，基本上只能得到一個市場的平均回報。第二種方法，只投一家，其實這就是賭博，我的一些朋友購買股票時，會只買單只股票並且重倉，這種情況如果碰到了會有幾倍收入，但是大多數情況下都是血本無歸，這是極為糟糕的投資方式。第三種方法是利用哈夫曼編碼的原理，可以先把錢逐級投下去，每一次投資的公司呈指數減少，而金額倍增，這樣通常不會錯失上市的那家。大部分資金都集中到了最後的上市或被收購的企業中，這種投資回報要遠遠高於前兩種。
對於個人而言，利用哈夫曼編碼進行投資也是適用的。美國有名的私立學校哈克學校的前校長尼克諾夫博士說過，在孩子小時候，要讓他們嘗試各種不同的愛好，但是最終他們要在一個點上實現突破。他將這比作圓規畫圓，一方面有一個扎得很深的中心，另一方面有足夠廣的很淺的覆蓋面。
在工作中，一方面需要成為某個方面的專家，做到足夠的深入，比如在DevOps方面，另一方面也需要有足夠的覆蓋面，了解各個細分領域的設計思想，基本原理和簡單實用。
對於我而言，我會嘗試很多新的事情，不會去排斥，是因為不想失去機會，雖然結果是絕大部分失敗了，但是至少也嘗試過了，畢竟謀事在人成事在天。另一方面對於我花了一些精力，但是看樣子也成不了的事情，我是堅決做減法退場止損。這條同樣也適用於感情。
參考：
- wiki：//zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
- dahuffman：//github.com/soxofaan/dahuffman
- 哈夫曼樹的調整：//blog.csdn.net/fx677588/article/details/70767446
