霍夫曼编码压缩算法 参考代码
时间: 2023-11-12 12:12:19 浏览: 32
以下是一个简单的 Python 实现:
```python
import heapq
import collections
def huffman_encoding(data):
# 计算字符出现次数
freq = collections.Counter(data)
# 构建 Huffman 树
heap = [[f, [c, ""]] for c, f in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
# 生成编码表
code = dict(heapq.heappop(heap)[1:])
# 编码数据
encoded_data = ""
for c in data:
encoded_data += code[c]
return encoded_data, code
def huffman_decoding(encoded_data, code):
# 反转编码表
reversed_code = {v: k for k, v in code.items()}
# 解码数据
current_code = ""
decoded_data = ""
for bit in encoded_data:
current_code += bit
if current_code in reversed_code:
decoded_data += reversed_code[current_code]
current_code = ""
return decoded_data
```
使用方法:
```python
data = "hello world"
encoded_data, code = huffman_encoding(data)
print(f"Encoded data: {encoded_data}")
decoded_data = huffman_decoding(encoded_data, code)
print(f"Decoded data: {decoded_data}")
```
输出:
```
Encoded data: 1000111011011110011110100110101001111100010
Decoded data: hello world
```