Huffman Compression - 霍夫曼压缩

主要思想：放弃文本文件的普通保存方式：不再使用7位或8位二进制数表示每一个字符，而是用较少的比特表示出现频率最高的字符，用较多的比特表示出现频率低的字符。

使用变长编码来表示字符串，势必会导致编解码时码字的唯一性问题，因此需要一种编解码方式唯一的前缀码，而表示前缀码的一种简单方式就是使用单词查找树，其中最优前缀码即为Huffman首创。

以符号F, O, R, G, E, T为例，其出现的频次如以下表格所示。

Symbol F O R G E T
Frequence 2 3 4 4 5 7
Code 000 001 100 101 01 11

则对各符号进行霍夫曼编码的动态演示如下图所示。基本步骤是将出现频率由小到大排列，组成子树后频率相加作为整体再和其他未加入二叉树中的节点频率比较。加权路径长为节点的频率乘以树的深度。

Huffman

Python 实现

  1. """
  2. Use serveral ways to compress string `everyday is awesome!`
  3. 1. use simple bits to replace ASCII value
  4. 2. use huffman coding
  5. """
  6. import heapq
  7. import collections
  10. def get_rate(compressed_binary, uncompressed_bits):
  11.     return len(compressed_binary) * 100 / uncompressed_bits
  13. class SimpleCompression:
  14.     def __init__(self, string):
  15.         self.symbols = set(string)
  16.         self.bit_len = 1
  17.         while 2**self.bit_len < len(self.symbols):
  18.             self.bit_len += 1
  19.         self.string = string
  21.         self.s2b = {}
  22.         self.b2s = {}
  23.         i = 0
  24.         for s in self.symbols:
  25.             b = bin(i)[2:]
  26.             if len(b) < self.bit_len:
  27.                 b = (self.bit_len - len(b)) * '0' + b
  28.             self.s2b[s] = b
  29.             self.b2s[b] = s
  30.             i += 1
  32.     def compress(self):
  33.         bits = ''
  34.         for s in self.string:
  35.             bits += self.s2b[s]
  36.         return bits
  38.     def uncompress(self, bits):
  39.         string = ''
  40.         for i in xrange(0, len(bits), self.bit_len):
  41.             string += self.b2s[bits[i:i + self.bit_len]]
  42.         return string
  45. class HuffmanCompression:
  46.     class Trie:
  47.         def __init__(self, val, char=''):
  48.             self.val = val
  49.             self.char = char
  50.             self.coding = ''
  51.             self.left = self.right = None
  53.         def __cmp__(self, other):
  54.             return self.val - other.val
  56.     def __init__(self, string):
  57.         self.string = string
  58.         counter = collections.Counter(string)
  59.         heap = []
  60.         for char, cnt in counter.items():
  61.             heapq.heappush(heap, HuffmanCompression.Trie(cnt, char))
  63.         while len(heap) != 1:
  64.             left = heapq.heappop(heap)
  65.             right = heapq.heappop(heap)
  66.             trie = HuffmanCompression.Trie(left.val + right.val)
  67.             trie.left, trie.right = left, right
  68.             heapq.heappush(heap, trie)
  70.         self.root = heap[0]
  71.         self.s2b = {}
  72.         self.bfs_encode(self.root, self.s2b)
  74.     def bfs_encode(self, root, s2b):
  75.         queue = collections.deque()
  76.         queue.append(root)
  77.         while queue:
  78.             node = queue.popleft()
  79.             if node.char:
  80.                 s2b[node.char] = node.coding
  81.                 continue
  82.             if node.left:
  83.                 node.left.coding = node.coding + '0'
  84.                 queue.append(node.left)
  85.             if node.right:
  86.                 node.right.coding = node.coding + '1'
  87.                 queue.append(node.right)
  89.     def compress(self):
  90.         bits = ''
  91.         for char in self.string:
  92.             bits += self.s2b[char]
  93.         return bits
  95.     def uncompress(self, bits):
  96.         string = ''
  97.         root = self.root
  98.         for bit in bits:
  99.             if bit == '0':
  100.                 root = root.left
  101.             else:
  102.                 root = root.right
  103.             if root.char:
  104.                 string += root.char
  105.                 root = self.root
  106.         return string
  109. if __name__ == '__main__':
  110.     s = 'everyday is awesome!'
  111.     # ASCII
  112.     bits = len(s) * 8
  113.     print('Total bits: %d' % bits)
  115.     # simple compression
  116.     sc = SimpleCompression(s)
  117.     compressed = sc.compress()
  118.     print('Compressed binary: ' + compressed)
  119.     print('Uncompressed: ' + sc.uncompress(compressed))
  120.     print(sc.s2b)
  121.     print('Simple Compression-compress rate: %d%%' % get_rate(compressed, bits))
  123.     print('===================')
  124.     # huffman compression
  125.     hc = HuffmanCompression(s)
  126.     compressed = hc.compress()
  127.     print('Compressed binary: ' + compressed)
  128.     print('Uncompressed: ' + hc.uncompress(compressed))
  129.     print(hc.s2b)
  130.     print('Huffman Compression-compress rate: %d%%' % get_rate(compressed, bits))
  133. """
  134. Total bits: 160
  135. Compressed binary: 00101011001010001100001100001100000101000111000100001010001001110110010100101001
  136. Uncompressed: everyday is awesome!
  137. {'a': '0000', ' ': '0001', 'e': '0010', 'd': '0011', 'i': '0100', 'm': '0101', 'o': '0110', 's': '0111', 'r': '1000', '!': '1001', 'w': '1010', 'v': '1011', 'y': '1100'}
  138. Simple Compression-compress rate: 50%
  139. ===================
  140. Compressed binary: 011001011011110011010111111000010000111000111111010011110100011011010001
  141. Uncompressed: everyday is awesome!
  142. {'!': '0001', ' ': '001', 'e': '01', 'd': '11010', 'i': '0000', 'm': '11011', 'o': '1000', 's': '1110', 'r': '1011', 'a': '1111', 'w': '1010', 'v': '1001', 'y': '1100'}
  143. Huffman Compression-compress rate: 45%
  144. """

源码分析

简单压缩： 根据字符串出现的字符，将ASCII替换成更短的表示形式
霍夫曼压缩： 根据字符串出现频率，构建Trie树， 对每个tree node进行定义，使得频率越高的字符离root节点越近

有关霍夫曼编码的具体步骤可参考 Huffman 编码压缩算法 | 酷 壳 - CoolShell.cn 和 霍夫曼编码 - 维基百科，自由的百科全书，清晰易懂。