为什么霍夫曼编码的文本比实际文本大？

Question

我试图了解霍夫曼编码的工作原理，它应该压缩数据以占用比实际文本更少的内存，但是当我编码时

"Text to be encoded"

其中有 18 个字符，我得到的结果是

"100100110100101110101011111000001110011011110010101100011"

我是否应该将这些结果位除以 8 因为字符有 8 位？

Answer 1

您应该比较相同单位（位与压缩后的字符如前文所示），例如

before: "Text to be encoded" == 18 * 8 bits = 144 bits
                             == 18 * 7 bits = 126 bits (in case of 7-bit characters)
after:  100100110100101110101011111000001110011011110010101100011 = 57 bits

所以你有 144（或 126）位之前和之后的 57 位压缩。或者

before: "Text to be encoded" == 18 characters
after:   10010011 
         01001011
         10101011
         11100000
         11100110
         11110010
         10110001
         00000001 /* the last chunk is padded */ == 8 characters

所以压缩前有 18 个 ascii 字符，压缩后只有 8 个字节字符。如果字符应该是 7-bit（0..127 范围 Ascii table）我们在压缩后有 9 个字符：

after:  1001001 'I'
        1010010 'R'
        1110101 'u'
        0111110 '>'
        0000111 '[=12=]x07'
        0011011 '[=12=]x1B'
        1100101 'e'
        0110001 'l'
        0000001 '[=12=]x01'

为什么霍夫曼编码的文本比实际文本大？

Why is huffman encoded text bigger than actual text?

algorithm

huffman-code