霍夫曼编码是一种压缩数据流的方法，通过用较短的词对更频繁的项目进行编码。

这是字母A到J的分布以及我获得的代码：

0.00066872  0.01864353  0.0474964   0.18568327  0.11587298 
0.13329128  0.08580358  0.0881718   0.1847246   0.13964385

请注意，A是最少出现的蚂蚁，得到一个长度为 6 的单词，而I出现频率更高，长度为 2。

'B': '100011'
'A': '000011'
'D': '111'
'C': '10011'
'F': '001'
'E': '110'
'H': '010'
'G': '1011'
'J': '101'
'I': '00'

霍夫曼算法用不同的键构建一棵树。来自伪代码

• 从包含符号及其频率的叶节点集开始，由构建代码的初始数据确定。

• 现在找到两个权重最小的叶子并将它们合并以产生一个节点，该节点具有这两个节点作为其左右分支。新节点的权重是两个权重之和。从原始集合中删除两片叶子并用这个新节点替换它们。

• 现在继续这个过程。在每一步，合并两个权重最小的节点，将它们从集合中移除，并用一个将这两个节点作为左右分支的节点替换它们。

伪代码

算法：哈夫曼树（C）

1. n ← |C|
2. Q ← C a min–频率键控的优先级队列
3. 对于 i ← 1 到 n-1 做
4. 分配新节点 z
5. z.left ← x ← EXTRACT-MIN(Q)
6. z.right ← y ← EXTRACT-MIN(Q)
7. z.freq ← x.freq ← y.freq
8. Q.INSERT(z)
9. B 返回树的根
10. 返回 EXTRACT-MIN(Q)

这是我在 Python 中的实现。它使用了大量的排序，并且不使用上述任何数据类型。 有没有办法使用 numPy 和/或优先级队列来做到这一点？

f  = lambda a,b: int(100*(a[1]-b[1]))

p = np.random.random(10)*np.arange(10)+0.01
p = p/sum(p)
q = p
p = sorted([(str(x[0]), x[1]) for x in enumerate(p)], f)

code = { x[0]: '' for x in p}


for k in range(10-1):
    for x in p[0][0]:
        code[x] += '0'
    for x in p[1][0]:
        code[x] += '1'

    p = sorted(p[2:] + [(p[0][0]+p[1][0], p[0][1]+p[1][1])],f)

print q
print code