最佳壓縮霍夫曼樹

Question

我正在編碼一個霍夫曼串壓縮器，我想確認我正在用我的樹做最佳壓縮。

我用這樣的樹：

而是這個還挺樹：

我認爲，在10個單字符，這是不可能的壓縮上8位..

第一個圖像真的是最佳的嗎？

Answer 1

最基本的想法是添加兩個最小的節點，創建一個新的節點，該節點的值是其2個子節點的總和。

尊重此規則直到樹根保證產生的樹將是最優。

因此，你有沒有控制關於樹的形狀：它完全取決於字符的概率分佈。如果概率分佈看起來像斐波那契數列，它可能最終會變成一棵退化的樹（每級有一個分支）。

因此，使用預先設定的最大深度創建霍夫曼樹更復雜，並且需要打破始終添加2個最小節點的通常規則。由此產生的樹顯然不是最優的。