資料結構中高度受限的霍夫曼樹

高度受限或深度受限霍夫曼樹的示意圖如下所示

樹深度限制是一個非平凡的問題，大多數現實世界的霍夫曼實現都必須處理這個問題。

霍夫曼構造不會限制高度或深度。如果限制了，它就不可能“最優”。誠然，霍夫曼樹的最大深度受斐波那契數列限制，但這仍然留有比所需更大的深度的空間。

限制霍夫曼樹深度的理由是什麼？快速的霍夫曼解碼器實現查詢表。可以實現多個表級別以減輕記憶體成本，但是像 Huff0 這樣非常快速的解碼器為了簡單和速度而使用單個表。在這種情況下，表大小被視為樹深度的直接乘積 (表大小 = 1 << 樹深度)。

為了提高速度和記憶體管理，必須選擇一個限制：解碼錶為 8 KB，這很好地適合英特爾的 L1 快取，並且如有需要，還留有一些空間可以與其他表組合。

對於壓縮字面量來說，12 位通常太短了，至少根據最優霍夫曼構造是這樣。

因此，構造深度受限的樹是一個需要解決的實際問題。

自 20 世紀 60 年代以來，人們就開始研究深度受限的霍夫曼樹，因此有很多文獻可用。

Arnab Chakraborty

更新於：2020年1月7日

504 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習