c - 在霍夫曼编码中如何处理这个问题？

Question

压缩字符的输入频率为，

A = 1
B = 2
C = 4
D = 8
E = 16
F = 32
G = 64
H = 128
I = 256
J = 512
K = 1024
L = 2048
M = 4096
N = 8192

霍夫曼编码算法是，

首先，我们必须选择两个频率最低的字符并实现一棵树，其父级是这两个字符频率的总和。 之后将 0 放入左 child ，将 1 放入右 child 。 然后最后选择每个字符的值作为二进制形式，选择这个从根开始，发现它是放在左边还是右边，然后如果放在左边加0，如果放在右边加1。

它形成一棵超过 8 层的树。我们不得不提的是8位的二进制。但对于此输入，该位与 8 交叉。我们要做什么？

Answer 1

如果对所有 256 个可能的值进行编码，有些值将由超过 8 位表示，这是正确的。但是编码后的字符串不会被解释为数组 ob 字节，而是解释为一系列位，可能占用多个字节，因此霍夫曼树的分支深度超过八层是可以的。

假设您有一个包含这些编码(以及其他编码)的​​霍夫曼树:

E          000               # 3 bits
X          0100000001        # 10 bits
NUL        001               #3 bits

现在，当您想要对字符串 EEXEEEX 进行编码时，您会得到:

E   E   X          E   E   E   X          NUL      # original text
000 000 0100000001 000 000 000 0100000001 001      # encoded bits

您现在将这一系列位组织成 8 个 block ，即字节:

eeeEEExx    xxxxxxxx    EEEeeeEE    Exxxxxxx    xxxNNN      # orig

00000001    00000001    00000000    00100000    00100100    # bits
enc[0]      enc[1]      enc[2]      enc[3]      enc[4]      # bytes

(四个子 block 只是为了方便阅读。最后两个零位是填充。)字节数组 enc 现在是您的编码字符串。

压缩是因为常用字符占用的空间小于一个字节。例如，前两个 E 适合单个字节。像这里的 X 这样不常见的字符有更长的编码，甚至可能跨越几个字节。

当然，您必须从当前字节中提取当前位才能遍历霍夫曼树。为此，您需要按位运算符。