dynamic-programming - 无前缀编码的动态规划

Question

有没有一种方法可以计算给定字母字典的无前缀编码及其频率。类似于 Huffman-Coding 但动态计算 - 优化函数看起来如何？

仅仅为了字典的 i 位置而构建树的问题是，频率最低的字母可能会改变，因此整个树的结构也会改变。

Answer 1

是的，有几种方法可以动态生成无前缀代码。

正如您所建议的，从一些默认频率开始在概念上很简单，跟踪到目前为止使用的字母的频率，并且对于每个解码的字母，增加该字母的计数，然后从所有计数重新构建 Huffman 树。（可能在每个字母之后完全改变树）。这将需要对每个字母进行大量工作并且速度非常慢 - 但是有几个自适应霍夫曼编码算法可以有效地做同样的事情 - 使用聪明的算法做的工作少得多，因此速度更快。

许多其他数据压缩算法也比任何自适应霍夫曼算法更快地动态生成无前缀码，但压缩的损失很小——例如Polar 码或Engel 码或通用码，如 Elias delta 码。

算术编码数据压缩算法在技术上不是无前缀代码，但通常比静态霍夫曼编码或自适应霍夫曼编码提供更好的压缩（但运行速度较慢）。算术编码通常是自适应地实现的，跟踪迄今为止使用的所有字母的频率。（许多算术编码实现跟踪更多的上下文——如果前一个字母是“t”，它会记住在这个上下文中出现频率最高的字母是“h”以及它的频率等等，从而提供更好的压缩）。