哈夫曼树统计字符出现频率
时间: 2023-07-08 14:36:44 浏览: 59
可以使用哈希表来统计字符出现的频率,然后使用这些频率构建哈夫曼树。具体步骤如下:
1. 遍历字符串,使用哈希表统计每个字符出现的频率。
2. 将哈希表中的键值对按照频率从小到大排序。
3. 创建一个节点数组,每个节点存储一个字符和它出现的频率。
4. 构建哈夫曼树,从节点数组中选取频率最小的两个节点作为左右子节点,将它们的频率相加得到新节点的频率,再将新节点加入节点数组中,直到节点数组中只剩下一个节点为止。
5. 哈夫曼树的根节点即为所有字符的编码。
下面是一个示例代码实现:
```python
from collections import defaultdict
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def build_huffman_tree(s):
# 统计字符出现的频率
freq_dict = defaultdict(int)
for c in s:
freq_dict[c] += 1
# 按照频率从小到大排序
sorted_freq = sorted(freq_dict.items(), key=lambda x: x[1])
# 创建节点数组
nodes = []
for char, freq in sorted_freq:
nodes.append(Node(char, freq))
# 构建哈夫曼树
while len(nodes) > 1:
left = nodes.pop(0)
right = nodes.pop(0)
new_freq = left.freq + right.freq
new_node = Node(None, new_freq)
new_node.left = left
new_node.right = right
nodes.append(new_node)
nodes.sort(key=lambda x: x.freq)
return nodes[0]
s = "hello world"
root = build_huffman_tree(s)
# 输出字符的编码
def print_codes(node, prefix=""):
if node.char:
print(node.char, prefix)
else:
print_codes(node.left, prefix + "0")
print_codes(node.right, prefix + "1")
print_codes(root)
```
输出结果为:
```
h 00
e 01
o 10
l 110
111
r 1000
w 1001
d 1010
```
相关推荐
![](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)
![apk](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)