我已经在Windows下使用纯霍夫曼代码实现了a simple compressor。但是我对如何快速解码压缩文件了解不多,我的错误算法是:

枚举代​​码表中的所有霍夫曼代码,然后将其与压缩文件中的位进行比较,结果令人震惊:解压缩3MB文件需要6个小时。

您能提供一种效率更高的算法吗?我应该使用Hash之类的东西吗?

更新:
根据 friend 林的建议,我用状态表实现了the decoder。我认为这种方法应该比6秒钟内3MB的穿越霍夫曼树更好。

谢谢。

最佳答案

优化二叉树方法的一种方法是使用查找表。您可以对表格进行排列,以便可以直接查找特定的编码位模式,以允许任何代码的最大位宽。
由于大多数代码未使用最大最大宽度,因此它们包含在表中的多个位置-每个未使用位的组合都包含一个位置。该表指示要从输入以及解码输出中丢弃多少位。
如果最长的代码太长,则该表是不切实际的,一种折衷方法是使用较小的固定宽度下标查找树。例如,您可以使用256个项目的表来处理一个字节。如果输入代码超过8位,则表条目指示解码不完整,并将您定向到处理下一个最多8位的表。较大的表会以内存换取速度-256个项目可能太小。
我相信这种通用方法称为“前缀表”,这是BobMcGees引用的代码正在做的事情。可能的区别是某些压缩算法要求在解压缩期间更新前缀表-简单的霍夫曼不需要这样做。 IIRC,我第一次在关于位图图形文件格式的书中看到它,其中包括GIF,这是在专利 panic 发生前的一段时间。
从二叉树模型中预先计算完整的查找表,等效的哈希表或小表树应该很容易。二进制树仍然是代码工作方式的关键表示(心理模型)-此查找表只是实现它的一种优化方法。

09-10 07:33
查看更多