構建霍夫曼樹時如何選擇優先級？

Question

假設我的人物和他們的頻率如下：

Char Freq. 
a  1 
b  2 
c  3 
d  4 
e  5 
f  6 
g  7 
h  8 

在構建一棵樹，在步驟2中，我們有這樣的：

[3]  [3] [4] [5] [6] [7] [8] 
/\  c  d  e  f  g  h 
/ \ 
[1] [2] 
a  b 

現在，因爲我們有兩個三分球，我們如何才能確定他們的優先權？

在哈夫曼編碼這被認爲是：

[3] [3]  [4] [5] [6] [7] [8] 
c /\  d  e  f  g  h 
    / \ 
    [1] [2] 
    a  b 

爲什麼？

Answer 1

我會採取更大的優先權（較短的代碼）。這將符合霍夫曼樹的基本原則：即時結果的優先級/較短代碼和更多解析的較低優先級。

Answer 2

有什麼區別？忽略d通過h的時刻，在第一種情況下，你會得到

a = 00 
b = 01 
c = 1 

，並在第二種情況下，

a = 10 
b = 11 
c = 0 

只要c是在最終的樹的高度相同，它的代碼將具有相同的長度。

Answer 3

你的情況並不有趣。將0和1分配給分支是任意的，因此您勾選的選項會導致相同的代碼，即相同的代碼長度。

然而，有一些有趣的情況下，您面臨三個或更多具有相同總頻率和不同形狀的組的選擇。任何選擇都將導致相同的總體最優性，即在提供的頻率下對提供的符號進行編碼的總比特數完全相同。然而，這些選擇會導致具有不同位長度組合的不同形狀樹。然後可以根據需要選擇這種選擇來到達更深或更淺的樹木。