数据结构中高度受限的霍夫曼树

高度受限或深度受限霍夫曼树的示意图如下所示

树深度限制是一个非平凡的问题，大多数现实世界的霍夫曼实现都必须处理这个问题。

霍夫曼构造不会限制高度或深度。如果限制了，它就不可能“最优”。诚然，霍夫曼树的最大深度受斐波那契数列限制，但这仍然留有比所需更大的深度的空间。

限制霍夫曼树深度的理由是什么？快速的霍夫曼解码器实现查找表。可以实现多个表级别以减轻内存成本，但是像 Huff0 这样非常快速的解码器为了简单和速度而使用单个表。在这种情况下，表大小被视为树深度的直接乘积 (表大小 = 1 << 树深度)。

为了提高速度和内存管理，必须选择一个限制：解码表为 8 KB，这很好地适合英特尔的 L1 缓存，并且如有需要，还留有一些空间可以与其他表组合。

对于压缩字面量来说，12 位通常太短了，至少根据最优霍夫曼构造是这样。

因此，构造深度受限的树是一个需要解决的实际问题。

自 20 世纪 60 年代以来，人们就开始研究深度受限的霍夫曼树，因此有很多文献可用。

更新于：2020年1月7日

504 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告