假设用于通信的电文仅由 8 个字母(ABCDEFGH)组成 , 字母在电文中出现的频率分别为 0.07 , 0.19 , 0.02 , 0.06 , 0.32 , 0.03 , 0.21 ,画出哈夫曼树

先根据出现频率构建哈夫曼树：  从根节点开始，左子树路径上的编码为0，右子树路径上的编码为1，则每个字符的编码值为： - a: 1111 - b: 00 - c: 1101 - d: 1100 - e: 10 - f: 01 - g: 11100 - h: 11101 平均码长 = Σ(每个字符出现的频率 * 对应编码长度) = (5*4 + 29*2 + 7*4 + 8*4 + 14*2 + 23*2 + 3*5 + 11*5) / 100 = 2.45 个比特。

### 设计哈夫曼编码并计算带权路径长度 WPL #### 字符集与概率分布 给定字符集为 `{a, b, c, d, e, f, g, h}`，假设它们对应的概率分布分别为 `{0.1, 0.15, 0.3, 0.05, 0.2, 0.05, 0.1, 0.05}`。为了简化计算，我们将这些概率转换为整数形式的频率值乘以某个倍数（例如 100），得到新的频率集合：`{10, 15, 30, 5, 20, 5, 10, 5}`。 --- ### 构建哈夫曼树的过程 #### 初始化阶段 将每个字符与其对应的频率作为一个单独的节点放入优先队列中，并按频率从小到大排序： 初始队列为 `[5(a), 5(b), 5(c), 5(d), 10(e), 10(f), 15(g), 20(h)]`[^4]。 #### 合并过程 通过不断取最小的两个节点合并成新节点的方式逐步构建哈夫曼树： 1. 取出频率最小的两个节点 `5(a)` 和 `5(b)`，合并为新节点 `10(ab)`。 更新后的队列为 `[5(c), 5(d), 10(e), 10(f), 10(ab), 15(g), 20(h)]`[^4]。 2. 取出频率最小的两个节点 `5(c)` 和 `5(d)`，合并为新节点 `10(cd)`。 更新后的队列为 `[10(e), 10(f), 10(ab), 10(cd), 15(g), 20(h)]`。 3. 取出频率最小的三个节点 `10(e)` 和 `10(f)`，合并为新节点 `20(ef)`。 更新后的队列为 `[10(ab), 10(cd), 15(g), 20(ef), 20(h)]`。 4. 取出频率最小的两个节点 `10(ab)` 和 `10(cd)`，合并为新节点 `20(abcd)`。 更新后的队列为 `[15(g), 20(ef), 20(abcd), 20(h)]`[^4]。 5. 取出频率最小的两个节点 `15(g)` 和 `20(ef)`，合并为新节点 `35(gef)`。 更新后的队列为 `[20(abcd), 20(h), 35(gef)]`[^4]。 6. 取出频率最小的两个节点 `20(abcd)` 和 `20(h)`，合并为新节点 `40(abcdefgh)`。 更新后的队列为 `[35(gef), 40(abcdefgh)]`[^4]。 7. 最后取出剩余的两个节点 `35(gef)` 和 `40(abcdefgh)`，合并为根节点 `75(root)`。 完成了整个哈夫曼树的构建[^4]。 --- ### 哈夫曼编码生成 根据构建好的哈夫曼树，从根节点出发遍历至各个叶子节点，在每条边上标记 `0` 或 `1`，从而获得每个字符的哈夫曼编码。具体结果如下： | 字符 | 编码 | |------|------------| | a | 000 | | b | 001 | | c | 010 | | d | 011 | | e | 10 | | f | 110 | | g | 1110 | | h | 1111 | --- ### 计算带权路径长度 (WPL) 带权路径长度 \( \text{WPL} \) 的定义为所有叶子节点的权重乘以其路径长度之和。根据上述编码表可得： - 字符 `a` 的路径长度为 3 → 贡献为 \( 10 \times 3 = 30 \)。 - 字符 `b` 的路径长度为 3 → 贡献为 \( 15 \times 3 = 45 \)。 - 字符 `c` 的路径长度为 3 → 贡献为 \( 30 \times 3 = 90 \)。 - 字符 `d` 的路径长度为 3 → 贡献为 \( 5 \times 3 = 15 \)[^4]。 - 字符 `e` 的路径长度为 2 → 贡献为 \( 20 \times 2 = 40 \)[^4]。 - 字符 `f` 的路径长度为 3 → 贡献为 \( 5 \times 3 = 15 \)[^4]。 - 字符 `g` 的路径长度为 4 → 贡献为 \( 10 \times 4 = 40 \)[^4]。 - 字符 `h` 的路径长度为 4 → 贡献为 \( 5 \times 4 = 20 \)[^4]。 因此，总带权路径长度 \( \text{WPL} \) 为： \[ \text{WPL} = 30 + 45 + 90 + 15 + 40 + 15 + 40 + 20 = 295. \] --- ### Python 实现代码示例 以下是基于上述逻辑的 Python 实现代码片段： ```python import heapq class Node: def __init__(self, char=None, freq=0, left=None, right=None): self.char = char self.freq = freq self.left = left self.right = right def __lt__(self, other): return self.freq < other.freq def build_huffman_tree(freq_map): heap = [] for char, freq in freq_map.items(): heapq.heappush(heap, Node(char, freq)) while len(heap) > 1: node1 = heapq.heappop(heap) node2 = heapq.heappop(heap) merged_node = Node(None, node1.freq + node2.freq, node1, node2) heapq.heappush(heap, merged_node) return heap[0] def generate_codes(node, current_code="", code_dict={}): if node is None: return if node.char is not None: code_dict[node.char] = current_code generate_codes(node.left, current_code + "0", code_dict) generate_codes(node.right, current_code + "1", code_dict) return code_dict freq_map = {'a': 10, 'b': 15, 'c': 30, 'd': 5, 'e': 20, 'f': 5, 'g': 10, 'h': 5} root = build_huffman_tree(freq_map) codes = generate_codes(root) print("Huffman Codes:", codes) wpl = sum([freq_map[char] * len(code) for char, code in codes.items()]) print("Weighted Path Length (WPL):", wpl) ``` --- ###