一点一点地读哈夫曼压缩

Question

我正在编写一个实现Huffman压缩的python程序。但是，我似乎只能逐字节地读/写bin文件，而不是一点一点地读/写。有没有解决这个问题的方法？逐字节处理不会破坏压缩的目的，因为需要额外的填充。另外，如果有人能告诉我关于Huffman压缩在这个逐字节问题上的应用，那就太好了。w

Answer 1

将代码分层。有一个底层io层，可以一次或通过缓冲来完成所有文件的读写操作。在上面有一层，逐位处理哈夫曼码位流。在

Answer 2

一种只需读取字节的潜在方法是直接在解码例程中进行缓冲。这与基于表的解码很好地结合在一起，而且没有执行逐位IO的开销（通过抽象层隐藏这些信息并不会使其消失，只需在地毯下擦掉它）。在

在最简单的情况下，基于表的解码需要一个位流的“窗口”，其大小为¹最大可能的代码（顺便说一下，这类事情是许多使用哈夫曼压缩的格式指定的最大代码长度不是超长的很大一部分原因），这可以通过移动向右缓冲，直到大小正确：

window = buffer >> (maxCodeLen - bitsInBuffer)

因为这样可以消除多余的位，所以在没有足够的位时，可以安全地向缓冲区追加比严格需要的更多的位：

^{pr2}$

因此字节IO就足够了。实际上，如果你愿意的话，你可以读稍微大一点的块（比如一次读两个字节）。顺便说一句，这里有一点复杂：如果一个文件的所有字节都已被读取，而缓冲区中没有足够的位（这是一种合法的情况，可能发生在有效的比特流中），你只需要填充“padding”（基本上是左移，而不在新的位中使用ORing）。在

解码本身可能如下所示：

^{3}$

这一切都很简单，困难的部分是构造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)

顺便说一下，这些代码都没有经过测试，只是粗略地展示一下它是如何完成的。它还假设以一种特殊的方式将位流打包成字节，第一位在字节的顶部。在

---

1:有些多级解码策略可以使用一个较小的窗口，如果码长没有限制的话，可能需要这个窗口。在

2：例如，放气最多15位