在网上寻找自适应 Huffman 的资料,并不好找。终于找到了网友 王京写的《》,看了三两遍之后,终于明白。花了近一天的时间,终于实现代码。主要是程序中的几个 bug,实际写代码花的时间并不长。
文中说到 Quake 3 的实现中不是使用“编号”而是使用双向链表,于是我在程序中就使用了 std::list。测试性能的时候发现实在太慢,压缩一千条 URL 居然用了 5 秒多钟。后来直接使用固定的数组来实现,结果速度快了 10 倍左右。其实这个实现根本用不上 std::list,因为结点在双向链表中几乎只有在后面追回以及交换两个结点的值的操作,使用原生数组就可以实现。
程序中的 bug 主要出在位运算上,没有意识到有符号在 >> 时存在的问题。没有使用 unsigned 类型的数据,实在是不应该,在以前写的代码中肯定是使用的 unsigned 类型的。看来写程序的能力是退化了,唉。另外要注意的问题是,在结点在块中交换的时候,不能与父结点交换(这只有在 NYT 的父结点与 NYT 的兄弟结点之间发生)。
自适应 huffman 在少量数据下是很吃亏的,很可能根本不能压缩。大概要在一两百字节之后,才有更高的效率。最后测试时大概压缩速度是 260KB/s,在闪龙 2200+ 的机器上。
阅读(5502) | 评论(5) | 转发(0) |