python - 将位串转换为字节(霍夫曼编码)

Question

在为解压而编写的huffman编码中，必须将一个比特流与多个值（无前缀）进行比较。我正在尝试用python实现一个huffman编码解码器，这是我将比特流转换成ascii值的代码。

c = ''
l = 0
x = 1
stime = time.time()
while l<len(string):
    if string[l:l+x] in table:
        c+=table[string[l:l+x]]
        l+=x
        x = 1
    else:
        x+=1

我该怎么做才能使这个循环更有效？

Answer 1

快速：
首先，确保您已经构建了一个规范的Huffman代码，其中较短的代码在数值上先于较长的代码这很容易做到，首先将哈夫曼代码描述为每个符号的位数。然后将哈夫曼码按符号顺序赋给最短码，再按符号顺序赋给下一个最短码，依此类推例如。

Symbol   Bits
  A        2
  B        4
  C        3
  D        3
  E        2
  F        3
  G        4

按位排序，保留按符号排序：

Symbol   Bits
  A        2
  E        2
  C        3
  D        3
  F        3
  B        4
  G        4

分配哈夫曼代码，从零开始：

Symbol   Bits    Code
  A        2     00
  E        2     01
  C        3     100
  D        3     101
  F        3     110
  B        4     1110
  G        4     1111

这种规范的方法提供了一种从压缩器向解压器传输哈夫曼代码的紧凑方法，因为您不必发送实际的代码或树——只需发送每个符号的代码长度。然后代码可以在另一端如上所述构建。
现在我们创建解码表、符号表和代码索引表：

Bits    Start     Index
  2    0000 (0)     0
  3    1000 (8)     2
  4    1110 (14)    5

现在要解码，您可以从2到4位循环，看看您的代码是否小于下一位大小的起始代码。我们从流中提取四个位并调用它Symbol[] = "AECDFBG"（如果流中没有更多的四个位，只需附加零位即可填充它）。在伪代码中，使用nyb代替循环，if表示下移位：

if nyb < Start[Bits are 3] (= 8) then
    output Symbol[Index[Bits are 2] (= 0) + (nyb - Start[Bits are 2] (= 0)) >> 2]
    remove top two bits from bitstream
else if nyb < Start[Bits are 4] (= 14) then
    output Symbol[Index[Bits are 3] (= 2) + (nyb - Start[Bits are 3] (= 8)) >> 1]
    remove top three bits from bitstream
else (must be four bits)
    output Symbol[Index[Bits are 4] (= 5) + (nyb - Start[Bits are 4] (= 14))]
    remove top four bits from bitstream

应该很容易看出如何将其转换为循环，从最短的代码长度转换为第二长的代码长度，如果您没有找到它，那么它一定是最长的代码长度。
更快：
构建一个长度为2**（最长代码的长度）的查找表。表中的每个条目都包含代码中的位数和产生的符号您可以将比特流中的许多位用作索引同样，如果比特流没有剩下那么多比特，那么用零填充。然后，您只需从该索引项中输出符号，并从位流中移除该索引项中的位数（该位数可能小于为索引提取的位数，请确保将未使用的位数保留在位流中）。重复，现在从剩余的位流中提取第一个未使用的位。
在下一个复杂的层次上，您可以做zlib所做的事情如果最长的代码相对较长（在zlib中可以是15位），那么与下面的方法相比，生成表所需的时间可能不足以支付解码所节省的时间。有一个两级表，其中第一级表最多包含>>位，其中n小于最长代码。（在zlib中，对于15位代码，最佳选择是n）然后，如果代码小于或等于n == 9位，则表条目提供符号和位数，然后按上述步骤继续如果代码大于n位，则转到处理剩余位的n位值的子表，如上所述。该表条目指示要为子表提取多少位，并定义子表的大小，称之为n从流中删除顶部的k位，然后拉取下一个n位，并将其用作子表的索引。然后得到代码中的符号和剩余位数，并按照单级表中的步骤进行操作注意k不一定是每个子表的最长代码的长度，因为该子表可能只包含较短的代码。只有最后一个或几个子表的n+k等于最长代码的长度。
这可能相当快，因为通过哈夫曼代码的构造，较短的代码更有可能。大多数情况下，你会在第一层得到符号，只是偶尔需要去第二层。要在主表和所有子表中填写的表条目总数可能远远小于包含整个代码长度的大表中的条目数这样就减少了准备解码的时间。
如果您有更长的哈夫曼码（例如32位），则可以有更多级别的子表确定子表的最佳断点需要一些实验，这将取决于新代码的发送频率和表的构建频率。