除了霍夫曼樹之外，是否還有任何優化前綴代碼的樹？那個高度會和霍夫曼樹的高度一樣嗎？

Question

我已經知道霍夫曼樹是一種用於優化前綴代碼的樹，但是除了霍夫曼樹以外，是否還有任何樹用於優化前綴代碼？如果有一些這樣的樹木，將他們的高度相同？ 非常感謝！

Answer 1

霍夫曼樹是通過取兩個當前最低的概率符號並將它們組合來遞歸構造的。

如果有其他符號具有相同的低概率，則可以將這些符號組合。

這意味着最終的樹不是唯一定義的，並且有多個潛在不同高度的最優前綴代碼。

例如，考慮使用的符號和以下概率：

A 1/3 
B 1/3 
C 1/6 
D 1/6 

可以被編碼爲：

A 0 
B 10 
C 110 
D 111 

或

A 00 
B 01 
C 10 
D 11 

兩個編碼具有比特的每一個預期數符號等於2，但高度不同。

然而，所有的最佳前綴碼可以通過Huffman算法用於相對於概率的關係排序的適當選擇構成。

Answer 2

在霍夫曼代碼問題的約束下，即通過前綴唯一的比特序列來表示每個符號，那麼恰好有一個最佳總比特數可以達到，並且霍夫曼算法實現了這一點。還有其他的方法可以得到相同的答案。

正如彼得·德Rivaz指出，在某些特殊情況下，霍夫曼算法有多個選項的一些步驟，其中兩個最小概率代碼集的挑選，這可能會導致不同的樹。所以樹高度/深度你提到是不是唯一的，但總比特數（通過其概率加權每個符號的位長度的總和）始終是相同的。