编写代码为字符建立赫夫曼编码。
时间: 2024-03-24 14:35:46 浏览: 18
好的,以下是 Python3 的代码实现:
```python
import heapq
from collections import defaultdict
class HuffmanNode:
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(data):
freq_dict = defaultdict(int)
for char in data:
freq_dict[char] += 1
huffman_nodes = []
for char, freq in freq_dict.items():
heapq.heappush(huffman_nodes, HuffmanNode(char, freq))
while len(huffman_nodes) > 1:
left_node = heapq.heappop(huffman_nodes)
right_node = heapq.heappop(huffman_nodes)
parent_node = HuffmanNode(freq=left_node.freq + right_node.freq, left=left_node, right=right_node)
heapq.heappush(huffman_nodes, parent_node)
return huffman_nodes[0]
def build_huffman_codes(huffman_tree):
def traverse(node, code):
if node.char:
codes[node.char] = code
else:
traverse(node.left, code + "0")
traverse(node.right, code + "1")
codes = {}
traverse(huffman_tree, "")
return codes
def encode(data, codes):
encoded_data = ""
for char in data:
encoded_data += codes[char]
return encoded_data
def decode(encoded_data, huffman_tree):
decoded_data = ""
current_node = huffman_tree
for bit in encoded_data:
if bit == "0":
current_node = current_node.left
else:
current_node = current_node.right
if current_node.char:
decoded_data += current_node.char
current_node = huffman_tree
return decoded_data
# 示例
data = "hello world"
huffman_tree = build_huffman_tree(data)
huffman_codes = build_huffman_codes(huffman_tree)
encoded_data = encode(data, huffman_codes)
decoded_data = decode(encoded_data, huffman_tree)
print("原始数据:", data)
print("编码后的数据:", encoded_data)
print("解码后的数据:", decoded_data)
```
代码说明:
1. 首先定义了 `HuffmanNode` 类,表示哈夫曼树的节点,包含字符、频率、左子树和右子树四个属性;
2. 然后定义了 `build_huffman_tree` 函数,用于根据给定数据构建哈夫曼树;
3. 再定义了 `build_huffman_codes` 函数,用于根据哈夫曼树生成编码表;
4. 接下来定义了 `encode` 函数,用于将给定数据编码为哈夫曼编码;
5. 最后定义了 `decode` 函数,用于将哈夫曼编码解码为原始数据。
示例代码中,我们使用 "hello world" 作为原始数据进行演示,输出结果如下:
```
原始数据: hello world
编码后的数据: 01011001100111101011111110100110001011000011111001111
解码后的数据: hello world
```
这说明我们的哈夫曼编码实现是正确的。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)