一点一点地阅读霍夫曼压缩

Question

我正在编写一个实现霍夫曼压缩的 python 程序。但是，我似乎只能逐字节而不是逐位读取/写入bin文件。这个问题有什么解决方法吗？逐字节处理不会破坏压缩的目的，因为需要额外的填充。另外，如果有人能启发我关于哈夫曼压缩在这个逐字节问题上的应用，那就太好了。 w

Answer 1

分层你的代码。有一个底层 io 层，它可以一次或缓冲地执行所有文件读取和写入整个文件。在逐位处理霍夫曼码比特流的层之上有一层。

Answer 2

一种只需要读取字节的潜在方法是直接在解码例程中进行缓冲。这与 table-based 解码结合得很好，并且没有执行 bit-by-bit IO 的开销（用抽象层隐藏它不会让它消失，只是将它擦在地毯下）。

在最简单的情况下，基于table的解码需要"window"比特流，其大小与¹最大可能的代码一样大（顺便说一下这种事情是许多使用霍夫曼压缩的格式指定不是超长的最大代码长度的很大一部分原因²)，这可以通过移动缓冲区来创建向右，直到它具有正确的大小：

window = buffer >> (maxCodeLen - bitsInBuffer)

因为这无论如何都会去除多余的位，所以在没有足够的情况下，可以安全地向缓冲区追加 比严格必需的更多 位：

while bitsInBuffer < maxCodeLen:
    buffer = (buffer << 8) | readByte()
    bitsInBuffer += 8

因此byte-IO就足够了。实际上，如果您愿意，您可以读取稍大的块（例如，当时两个字节）。顺便说一句，这里有点复杂：如果文件的所有字节都已被读取并且缓冲区中没有足够的位（这是有效比特流可能发生的合法条件），您只需要填充 "padding"（基本上是左移，没有在新位中进行 ORing）。

解码本身可能如下所示：

# this line does the actual decoding
(symbol, length) = table[window]
# remove that code from the buffer
bitsInBuffer -= length
buffer = buffer & ((1 << bitsInBuffer) - 1)
# use decoded symbol

这一切都很简单，难的是构建table。一种方法（不是很好的方法，而是一种简单的方法）是获取从 0 到并包括 (1 << maxCodeLen) - 1 的每个整数，并使用 bit-by-bit tree-walking 解码其中的第一个符号你习惯的方式。一种更快的方法是获取每个 symbol/code 对并使用它来填充 table:

的正确条目

# for each symbol/code do this:
bottomSize = maxCodeLen - codeLen
topBits = code << bottomSize
for bottom in range(0, (1 << bottomSize) - 1):
    table[topBits | bottom] = (symbol, codeLen)

顺便说一句 none 这段代码已经过测试，它只是粗略地展示了它是如何完成的。它还假设了一种将比特流打包成字节的特定方式，第一位在字节的顶部。

1：一些multi-stage解码策略可以使用更小的window，如果代码长度没有限制，这可能是必需的。

2：例如 Deflate 最多 15 位

一点一点地阅读霍夫曼压缩

Reading bit by bit for Huffman Compression

python

algorithm

compression

huffman-code