哈夫曼编码的编码和解码函数,
时间: 2023-07-19 13:11:35 浏览: 46
好的,下面是哈夫曼编码的编码和解码函数的 Python 代码示例:
```python
# 定义哈夫曼树节点类
class Node:
def __init__(self, freq, char=None):
self.freq = freq
self.char = char
self.left = None
self.right = None
# 构建哈夫曼树
def build_huffman_tree(freq_dict):
nodes = [Node(freq_dict[char], char) for char in freq_dict]
while len(nodes) > 1:
nodes.sort(key=lambda x: x.freq)
left = nodes.pop(0)
right = nodes.pop(0)
parent = Node(left.freq + right.freq)
parent.left = left
parent.right = right
nodes.append(parent)
return nodes[0]
# 生成哈夫曼编码表
def build_code_table(node, prefix="", code_table={}):
if node.char:
code_table[node.char] = prefix
else:
build_code_table(node.left, prefix + "0", code_table)
build_code_table(node.right, prefix + "1", code_table)
return code_table
# 哈夫曼编码
def encode(text, code_table):
encoded_text = ""
for char in text:
encoded_text += code_table[char]
return encoded_text
# 哈夫曼解码
def decode(encoded_text, node):
decoded_text = ""
current_node = node
for bit in encoded_text:
if bit == "0":
current_node = current_node.left
else:
current_node = current_node.right
if current_node.char:
decoded_text += current_node.char
current_node = node
return decoded_text
```
其中,`build_huffman_tree` 函数用于构建哈夫曼树,`build_code_table` 函数用于生成哈夫曼编码表,`encode` 函数用于将文本字符串进行编码,`decode` 函数用于将编码后的字符串进行解码。使用时,先通过 `build_huffman_tree` 函数构建哈夫曼树,再通过 `build_code_table` 函数生成哈夫曼编码表,最后使用 `encode` 函数对文本进行编码,或使用 `decode` 函数对编码后的字符串进行解码。