Python哈夫曼编码
时间: 2023-11-15 14:02:40 浏览: 98
Python哈夫曼编码是一种根据词频变化的变长二进制编码方式,多用于压缩算法。它的实现方法是将信源符号按出现概率从大到小排列,然后选2个最小的结合,依次类推,直到剩下2个符号为止。使用哈夫曼编码,结果不唯一,平均码长相同,接近信源熵,方法容易简单。但是对于接近等概率分布的信源编码效率低。在Python中,可以使用newHuffman.py和demo.py两个模块来实现Huffman编码。其中,newHuffman.py是功能模块,demo.py是控制模块。由于每个人对Huffman编码的写法略有不同,可能具体的每个符号编码出来的结果会不同,但是平均长度和编码效率的值必定是相同的。
相关问题
python 哈夫曼编码
哈夫曼编码是一种基于字符出现频率的编码方式,它可以将字符编码为不同长度的二进制码,从而实现数据的压缩。下面是一个Python实现的哈夫曼编码的例子:
```python
import heapq
from collections import defaultdict
def encode(s):
# 统计字符出现频率
freq = defaultdict(int)
for c in s:
freq[c] += 1
# 构建哈夫曼树
heap = [[wt, [sym, ""]] for sym, wt in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
# 构建编码表
code = dict(heapq.heappop(heap)[1:])
encoded = "".join([code[c] for c in s])
return encoded, code
def decode(encoded, code):
inv_code = {v: k for k, v in code.items()}
current_code = ""
decoded = ""
for bit in encoded:
current_code += bit
if current_code in inv_code:
decoded += inv_code[current_code]
current_code = ""
return decoded
```
这个例子中,`encode`函数接受一个字符串作为输入,返回该字符串的哈夫曼编码和编码表。`decode`函数接受一个哈夫曼编码和编码表作为输入,返回解码后的字符串。
python哈夫曼编码代码
以下是Python实现哈夫曼编码的代码:
```python
import heapq
from collections import defaultdict
def encode(symb2freq):
heap = [[wt, [sym, ""]] for sym, wt in symb2freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
txt = "hello world"
symb2freq = defaultdict(int)
for ch in txt:
symb2freq[ch] += 1
huff = encode(symb2freq)
print("Symbol\tWeight\tHuffman Code")
for p in huff:
print("%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1]))
```
这段代码实现了哈夫曼编码的基本功能,包括构建哈夫曼树、生成哈夫曼编码等。在这个例子中,我们使用了一个字符串“hello world”作为输入,然后统计每个字符出现的频率,最后生成对应的哈夫曼编码。
阅读全文