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

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 位(0..127 范围 Ascii 表)，我们在压缩后有 9 个字符:

after:  1001001 'I'
        1010010 'R'
        1110101 'u'
        0111110 '>'
        0000111 '\0x07'
        0011011 '\0x1B'
        1100101 'e'
        0110001 'l'
        0000001 '\0x01'