完整二叉樹用於霍夫曼碼的優點是什麼？

我正在研究霍夫曼編碼字符流的位編碼，並且認爲最佳代碼將由完整的二叉樹表示，其中每個不同的字符由葉代表，並且所有內部節點包含恰好兩個孩子。完整二叉樹用於霍夫曼碼的優點是什麼？

我想知道爲什麼完整的二叉樹是最佳選擇嗎？換句話說，全二叉樹在這裏的優點是什麼？

2012-09-17 Geek

您可能想要閱讀[*此*]（http://xlinux.nist.gov/dads/HTML/optimalMerge.html） – alfasin

您是從哪裏閱讀的？ – Deestan

@deestan [算法導論]中的貪婪算法章節（http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall -2005 /） – Geek

這不是一種選擇，而是等價。

最佳霍夫曼代碼由一個有限狀態機解碼，其中

每個狀態具有正好兩個出口（下一個比特爲或）
每個狀態具有正好一個條目
所有包含輸出符號的狀態都是停止狀態，和
所有停止狀態都包含輸出符號

這等同於一個搜索樹，其中

所有內部節點具有恰好兩個孩子
所有節點都具有一個父
含有輸出符號的所有節點是葉節點，和
所有葉節點包含輸出符號

也有非最佳霍夫曼代碼，它們的停止狀態/葉節點不包含輸出符號。這種二叉樹不會是full。

來源

2012-09-17 08:12:01

你是什麼意思「每個州只有一個條目」。你也可以提供一張圖片，顯示霍夫曼碼解碼的全部四個要求，滿足一個完整的二叉樹。 – Geek

對於每個節點（除了開始），只有一個邊緣通向它（即沒有兩個輸入符號序列導致相同的狀態）。 –

二叉樹總是滿足前兩個（每個內部節點「二元」 - >兩個孩子，「樹」 - >自由循環）。 –

完整二叉樹用於霍夫曼碼的優點是什麼？

回答

相關問題