JavaScript 中处理压缩位的最有效方法

Question

我从未做过压缩，但对 Huffman encoding 很感兴趣。他们将其显示为前几个字母的简单演示编码：

A     0
E     10
P     110
space 1110
D     11110
T     111110
L     111111

你在其他地方看到的标准霍夫曼编码有一组不同的代码，但这对这道题来说无关紧要。我想知道的是如何最有效地操作 JavaScript 中的这些位。据说你应该以 8、16 或 32 为单位处理事物，但实际上没有别的，因为这就是整数和值在计算机体系结构中的存储方式。所以我的理解是你应该一次读取输入的 8 位块。我不太确定该怎么做，但我认为如果你这样做的话它会起作用：

var bytes = new Uint8Array(array)
var byte1 = bytes[0]
var byte2 = bytes[1]
...

这似乎是访问数据的最有效方式。但是我正在考虑另一种选择，我想澄清一下。您可以将输入转换为二进制文本字符串，即 1 和 0 的字符串，如

var string = integerOrByteArray.toString(2)

但据我所知，将任何内容转换为字符串都会影响性能。所以看来你应该尽可能避免转换为字符串。

所以如果是这样的话，那么我们就剩下第一种方法Uint8Array（或Uint32Array，等等）。我想知道您随后如何将值拆分为组成部分 efficiently/ideally。所以如果我们有这个....

010110
AEP

.....我们做了我们的整数事情，然后我们可能会加载一些 8 位整数，如下之一：

所以这就像，我们需要加入（可能）任何可能属于最后 8 位块的前面数据，然后将其余部分拆分为字符。我的问题基本上是推荐的方法是什么。我可以想出一些方法，但到目前为止它们看起来都相当复杂。

Answer 1

这其实是和哈夫曼解压的"rest"相互作用的。您在这里究竟需要什么取决于您是打算进行基于 table 的高效解码，还是逐位树遍历。不解码就不能拆分输入，因为你只有在解码它代表什么符号后才能找到代码的长度。解码后，分割没有太多意义，所以我们最终得到的只是一个霍夫曼解码器，而不是位串分割器。

对于逐位树遍历，您所需要的只是某种方法来访问字节数组中的任何特定位（给定其索引）。您还可以使用以下技术，块大小为 1 位。

为了更有效的解码，您需要一个缓冲区，您可以从中提取一个比特块，只要您预定义的最大代码长度，比如说 15 比特左右^[1].具体取决于您的代码打包成字节的顺序，即字节是填充 lsb-to-msb 还是 msb-to-lsb，以及您希望在缓冲区变量中保留这些位的位置。例如，这里我将缓冲区中的位保留在缓冲区的 lsb 附近，并假设如果代码被拆分为两个字节，那么它位于第一个字节的 lsb 和第二个字节的 msb^[2]（未测试）：

var rawindex = 0;
var buffer = 0;
var nbits = 0;
var done = false;
var blockmask = (1 << MAX_CODELEN) - 1;
while (!done) {
    // refill buffer
    while (nbits < MAX_CODELEN && rawindex < data.length) {
        buffer = (buffer << 8) | data[rawindex++];
        nbits += 8;
    }
    if (nbits < MAX_CODELEN) {
        // this can happen at the end of the data
        buffer <<= MAX_CODELEN - nbits;
        nbits = MAX_CODELEN;
    }
    // get block from buffer
    var block = (buffer >> (nbits - MAX_CODELEN)) & blockmask;
    // decode by table lookup
    var sym = table[block];
    // drop only bits that really belong to the symbol
    nbits -= bitlengthOf(sym);
    ...
    // use the symbol somehow
}

这显示了最简单的基于 table 的解码策略，只是一个简单的查找。 symbol/length 对可以是一个对象或存储在两个单独的 Uint8Array 中或编码到单个 Uint16Array 中，诸如此类。构建 table 很简单，例如在伪代码中：

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

变体

从 lsb 向上将代码打包成字节会改变位流。要在缓冲区中重组代码，位需要从缓冲区的高侧进入并从底部离开：

// refill step
buffer |= data[rawindex++] << nbits;
nbits += 8;
...
// get block to decode
var block = buffer & blockmask;
// decode by table lookup
var sym = table[block];
// drop bits
buffer >>= getlengthOf(sym);

table也不同，现在填充在table索引的高位，分散属于单个符号的条目而不是将它们放在连续的范围内（未测试，显示位压缩 table 条目，代码长度为 5 位）：

// for each symbol/code:
var paddingCount = MAX_CODELEN - codeLen;
for (var padding = 0; padding < (1 << paddingCount); padding++)
    table[(padding << codelen) | code] = (symbol << 5) + codeLen;

[1]：最大代码长度过长使得解码table非常大，MAX_CODELEN > 25 有溢出缓冲区的风险。有很多解决方法，但超长符号无论如何都不是很有用。

[2]：这不是 DELFATE 所做的。

Answer 2

你已经有了一个很好的阅读位答案。

为了完整起见，如果你也想研究压缩，这里有一个（未经测试的）输出函数，可能有助于一些想法：

let remainder = 0; 
let remainderBits = 0;  // number of bits held in remainder

function putHuffman( 
    code,       // non-negative huffman code
    nBits) {    // bit length of code

    if( remainderBits) {
        code = code * (2 ** remainderBits) + remainder;
        nBits += remainderBits;
    }
    while( nBits >= 8) {
        putOctet( code % 256);
        code /= 256;
        nBits -=8;
    }
    remainder = code;
    remainderBits = nBits;
}

function putOctet( byte) {
    // add byte to the output stream
}

它可以转换为使用位移运算符，但目前在一个代码中最多允许约 46 位 - 如果添加 7 个剩余位，位计数将达到 53，这是双浮点数中尾数值的最大位精度.

当然 JavaScript 不太适合密集型位运算，因为它缺少整数数据类型 - 使用浮点乘法似乎并不比左移慢很多，如果它确实更慢的话。

JavaScript 中处理压缩位的最有效方法

The most efficient way to deal with bits for compression in JavaScript

javascript

binary

encoding

bit-manipulation

huffman-code

变体