0

我正在阅读 Huffman Coding Algorithm 来对字符串进行编码。我可以看到制作一棵树时考虑了字符的频率。

这是频率表：

a   b   d   e   f   h   i   k   n   o   r   s   t   u   v 
5   1   3   7   3   1   1   1   4   1   5   1   2   1   1   9

*space has frequency 9

我可以看到有一棵树是用这个做的。但是我无法得出如何将元素放置在树中的规则。

书上说所有出现频率较高的字都应该在字根附近。但是如果两个以上的字符频率相同，那么它们必须位于词根的不同侧。

问题是，我们如何决定立场？

在我的书中a有代码010，r有011并且e有代码100。

有人可以帮忙吗？

4

2 回答 2

3

你试过维基百科吗？有一个关于霍夫曼编码的很好的演示。算法很简单：你需要一个优先队列。

算法有点像这样：

1. Create tree nodes with each character and their frequencies
2. Put all the letters and their frequencies in a priority queue Q
3. Do until Q contains only one element:
    3a. Pick two lowest-frequency items a, b
    3b. Create a tree node z with frequency(z) = frequency(a) + frequency(b)
    3c. Add a and b as left and right children of z
    3d. Put z in Q
4. Pick up the only element from Q. This would be the root of the tree.
5. Assign binary codes to each leaf node according to their root-to-leaf path.

优先级队列应该设计成最小优先级队列，即频率最低的节点应该最先出来。对于处理相同频率的项目，使用一些其他标准（例如字母顺序）作为决胜局。与编码和解码的平局标准保持一致。

于 2012-05-23T16:29:49.823 回答
2

一旦你有了你的树，那么如何将 0 和 1 分配给道路上每个岔路口的两个分支是一个任意选择。因此，如果没有使该分配规范化的方法，那么对于如何将位分配给每个符号就没有“正确答案”，例如，r必须是011. r可以是任何三位值。（尽管这组频率的长度必须是三位。）

重要的是解码器获得与编码器相同的 0 和 1 分配。您可以直接发送代码，也可以发送长度并以规范的方式分配 0 和 1。例如，在 zip、gzip、png 等中使用的压缩算法仅发送每个符号的位数。然后从最小长度开始，为该长度的所有符号分配从 0 开始的代码。符号按顺序分配代码，符号按其表示整数排序。例如，字符的 ASCII 排序顺序。对于下一个长度，在右侧添加位并且代码计数继续。这确保了正确的前缀码，从左到右解码。

所以在这种情况下，代码长度是：

2: _
3: a, e, r
4: d, f, n
5: b, h, t
6: i, k, o, s, u, v

所以我们得到（每个长度内的符号按字母顺序排列）：

_: 00
a: 010
e: 011
r: 100
d: 1010
f: 1011
n: 1100
b: 11010
h: 11011
t: 11100
i: 111010
k: 111011
o: 111100
s: 111101
u: 111110
v: 111111

这里的位分配与书中三个符号中的两个不同。作为其他非常好的规范前缀代码选择的示例，您可以反转所有位，或者您可以反转位列的任何子集。例如，您可以反转整个第一列。您可以更改每个长度的符号顺序。您可以颠倒位顺序。事实上，zip等以相反的顺序存储上面显示的位，因此解码是从最低有效位开始进行的，即从右到左。

于 2012-05-23T20:24:03.443 回答