1

在用于解压缩的霍夫曼编码中，您必须将比特流与多个值进行比较（无前缀）。我正在尝试在 python 中实现一个霍夫曼编码器解码器，这是我将比特流转换为 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

我能做些什么来使这个循环更有效率？

4

2 回答 2

1

如果您准备花更多时间建表，则可以加快解码速度，因为您可以构建一组表，以便一次处理一个字节的比特流，而不必移动或屏蔽输入流挑选出个别位。

您想构建一组表，以便解码字节流如下所示：

state = 0
for (input in inputBytes)
  output += outputTable[state][input]
  state = stateTable[state][input]

这里的输出将是一个可变长度的 ascii 值字符串。状态必须记住来自前一个字节或尚未转换为输出数据的字节的所有信息。构建这些表的一种方法是将状态 0 设为初始状态 - 当您即将读取输入数据的第一个字节时。然后，对于每个字节，尽可能多地解码并使用它来生成 outputTable[0][byte]。现在查看字节末尾的所有未使用位的字符串。对于这些字符串中的每一个，您都需要分配一个新状态，并且您需要为每个状态、所有可能的字节进行相同类型的表构建。当你这样做时，你也会在解码后得到一串未使用的位串。如果这些是位串，您已经分配了状态，您可以忽略它们并继续。如果不，你需要分配更多的状态。最终，您将构建表来处理所有可能的状态。

于 2012-09-03T04:57:15.270 回答
1

快速地：

首先，确保您已经构建了一个规范的霍夫曼代码，其中较短的代码在数字上位于较长的代码之前。这很容易通过首先将您的霍夫曼代码描述为每个符号的位数来轻松完成。然后将霍夫曼代码分配给符号顺序中的最短代码，然后按符号顺序分配下一个最短代码，依此类推。例如

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

这种规范的方法提供了一种将霍夫曼代码从压缩器传输到解压缩器的紧凑方法，因为您不必发送实际代码或树——只需发送每个符号的代码长度。然后可以在另一端像上面那样构建代码。

现在我们创建解码表、符号表Symbol[] = "AECDFBG"和代码索引表：

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

现在要解码，您可以从 2 位循环到 4 位，并查看您的代码是否小于下一位大小的起始代码。我们从流中提取四个位并调用它nyb（如果流中没有四个位，只需附加零位以填充它）。if在使用's 而不是循环的伪代码中，>>意味着向下移位：

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位。n（在 zlib 中，最佳选择n == 9是 15 位代码。）然后，如果代码是n位或更少，则表条目提供符号和位数，然后按上述方法进行操作。如果代码多于n位，那么您将转到一个子表n-处理剩余位的位值，同样如上。该表条目指示要为子表提取多少位，并定义该子表的大小，称为它k。您从流中删除最高n位并提取下一位k并将其用作子表的索引。然后你得到代码中的符号和剩余位数，并像在单级表中一样继续。请注意，这n+k不一定是每个子表的最长代码的长度，因为该子表可能只涵盖较短的代码。只有最后一个或几个子表n+k的长度等于最长代码的长度。

这可能非常快，因为通过构建霍夫曼代码，更短的代码更有可能。大多数时候你会在第一级获得符号，只是偶尔需要进入第二级。主表和所有子表中要填写的表项总数可能远小于覆盖整个代码长度的大表中的表项数。然后减少了准备解码所花费的时间。

如果您有更长的霍夫曼代码（例如 32 位），您可以有更多级别的子表。确定子表的最佳断点需要进行一些实验，这取决于发送新代码的频率以及必须构建表的频率。

于 2012-09-03T17:46:05.627 回答