擅长:python、mysql、java
<p>一种只需读取字节的潜在方法是直接在解码例程中进行缓冲。这与基于表的解码很好地结合在一起,而且没有执行逐位IO的开销(通过抽象层隐藏这些信息并不会使其消失,只需在地毯下擦掉它)。在</p>
<p>在最简单的情况下,基于表的解码需要一个位流的“窗口”,其大小为<sup>1</sup>最大可能的代码(顺便说一下,这类事情是许多使用哈夫曼压缩的格式指定的最大代码长度不是超长的很大一部分原因),这可以通过移动向右缓冲,直到大小正确:</p>
<pre><code>window = buffer >> (maxCodeLen - bitsInBuffer)
</code></pre>
<p>因为这样可以消除多余的位,所以在没有足够的位时,可以安全地向缓冲区追加比严格需要的更多的<em>位:</p>
^{pr2}$
<p>因此字节IO就足够了。实际上,如果你愿意的话,你可以读稍微大一点的块(比如一次读两个字节)。顺便说一句,这里有一点复杂:如果一个文件的所有字节都已被读取,而缓冲区中没有足够的位(这是一种合法的情况,可能发生在有效的比特流中),你只需要填充“padding”(基本上是左移,而不在新的位中使用ORing)。在</p>
<p>解码本身可能如下所示:</p>
^{3}$
<p>这一切都很简单,困难的部分是构造<code>table</code>。用一种很简单的方式来解码一个整数,但不是每一个都用。一种更快的方法是获取每个符号/代码对并使用它来填充表中的正确条目:</p>
<pre><code># 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)
</code></pre>
<p>顺便说一下,这些代码都没有经过测试,只是粗略地展示一下它是如何完成的。它还假设以一种特殊的方式将位流打包成字节,第一位在字节的顶部。在</p>
<hr/>
<p>1:有些多级解码策略可以使用一个较小的窗口,如果码长没有限制的话,可能需要这个窗口。在</p>
<p>2:例如,放气最多15位</p>