如何从霍夫曼编码比特流中解码消息？我不清楚霍夫曼算法的想法。
据我了解，假设我收到一条短信“我的名字是 XYZ”。
然后编码过程是这样的： 1. 计算字符的频率。2. 按值对频率进行排序。3. 构建一棵树。4. 通过将左边缘视为 0 并将右边缘视为 1 来遍历树，以获取预期的消息字符。5. 连接代码以找到比特流。
现在的问题是，如何从编码的比特流中找到原始消息？
我认为我们需要再次构建霍夫曼树。
但是我怎样才能从比特流中构造霍夫曼树呢？
问问题
2671 次
2 回答
2
没有原始树就无法解码消息。所以发送方必须将它包含在消息中（如果长消息的开销会很小）或者双方在发送消息之前就树达成一致。然后过程是相反的：您从流中逐位读取并遍历树。一旦你击中叶子然后发出字符。
于 2011-02-13T19:04:43.630 回答
0
有几个选择。一种是使用固定的霍夫曼树——例如，如果你正在编码普通的英文文本，字符的相对频率通常足够接近常数，你可以非常合理地做到让发送者和接收者事先达成一致他们都将使用的三个。
对于您描述的两遍霍夫曼算法，您几乎无法将树（以某种形式）与数据一起传输。
您还可以使用动态 Huffman 树，例如，您从上面第一个选项中概述的树开始，但是当它们处理数据时，发射器和接收器都会调整树以适应观察到的频率。唯一的技巧是每个字符必须在调整之前使用树进行编码，然后进行调整，然后处理下一个字符。这样接收端可以与发送端保持同步。
于 2011-02-13T19:04:48.357 回答