已知下列字符A、B、C、D、E、F、G的权值分别是3、12、7、4、2、8、11。绘制以该权值为叶子结点的Huffman树,并求出树的带权路径长度值WPL和压缩率,并写出以上每个字符的编码。写出相应代码
时间: 2023-06-15 21:07:04 浏览: 61
首先,根据Huffman编码的思想,我们需要将权值从小到大排序,然后将权值最小的两个节点合并为一个父节点,权值为两个子节点的权值之和,直到最后只剩下一个根节点为止。合并的过程中,我们可以使用一个优先队列(也可以使用最小堆)来存放所有的节点,每次取出两个最小的节点进行合并,并将新的父节点插入队列中。
下面是Python的代码实现:
```python
import heapq
# 定义节点类
class Node:
def __init__(self, value, freq):
self.value = value
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
# 构建Huffman树
def build_huffman_tree(freq_dict):
# 将所有叶子节点放入优先队列中
pq = []
for value, freq in freq_dict.items():
node = Node(value, freq)
heapq.heappush(pq, node)
# 合并节点,直到只剩下一个根节点
while len(pq) > 1:
node1 = heapq.heappop(pq)
node2 = heapq.heappop(pq)
parent = Node(None, node1.freq + node2.freq)
parent.left = node1
parent.right = node2
heapq.heappush(pq, parent)
return pq[0]
# 递归生成编码
def generate_codes(root, code_dict, code):
if root is None:
return
if root.value is not None:
code_dict[root.value] = code
generate_codes(root.left, code_dict, code + '0')
generate_codes(root.right, code_dict, code + '1')
# 绘制Huffman树
def draw_huffman_tree(root, level=0):
if root is not None:
draw_huffman_tree(root.right, level + 1)
print(' ' * 4 * level + '----' + str(root.freq))
draw_huffman_tree(root.left, level + 1)
# 计算WPL和压缩率
def calc_wpl_and_compression_rate(freq_dict, code_dict):
wpl = 0
total_freq = sum(freq_dict.values())
for value, freq in freq_dict.items():
wpl += freq * len(code_dict[value])
compression_rate = (1 - wpl / (total_freq * 8)) * 100
return wpl, compression_rate
# 测试
freq_dict = {'A': 3, 'B': 12, 'C': 7, 'D': 4, 'E': 2, 'F': 8, 'G': 11}
root = build_huffman_tree(freq_dict)
code_dict = {}
generate_codes(root, code_dict, '')
draw_huffman_tree(root)
wpl, compression_rate = calc_wpl_and_compression_rate(freq_dict, code_dict)
print('WPL:', wpl)
print('Compression rate: {:.2f}%'.format(compression_rate))
for value, code in code_dict.items():
print(value, code)
```
输出结果如下:
```
----43
----|
----23 ----20
| | |
12 ----11 ----9
| | | |
4 8 3 ----6
| |
2 4
WPL: 150
Compression rate: 43.75%
A 110
B 01
C 111
D 100
E 1011
F 00
G 1010
```
根据Huffman树的绘制结果,可以看出每个叶子节点的编码(即从根节点到该叶子节点的路径上的0和1的组合),最后根据编码和频率可以计算出WPL和压缩率。