无前缀编码的动态规划

Question

有没有一种方法可以计算给定字母字典及其频率的无前缀编码？类似于Huffman-编码但动态计算-优化函数是什么样子的？

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

Answer 1

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

正如您所建议的，从一些默认频率开始，跟踪到目前为止使用的字母的频率，对于解码的每个字母，递增该字母的计数，然后根据所有计数重新构建霍夫曼树，这在概念上是很简单的。(可能会完全改变每个字母后的树)。这将需要为每个字母做大量的工作，而且非常慢--但是有几个adaptive Huffman coding algorithms可以有效地做同样的事情--使用聪明的算法做更少的工作，所以速度更快。

许多其他数据压缩算法动态生成无前缀代码的速度也比任何自适应霍夫曼算法快得多，但代价很小--比如Polar codes或Engel coding，或者像Elias增量编码这样的universal codes。

从技术上讲，arithmetic coding data compression algorithm不是无前缀的代码，但通常提供比静态霍夫曼编码或自适应霍夫曼编码稍好的压缩(但运行速度较慢)。算术编码通常是自适应地实现的，跟踪到目前为止使用的所有字母的频率。(许多算术编码实现甚至跟踪更多的上下文--如果前面的字母是"t"，它会记住上下文中最频繁的字母是"h“，以及它的确切频率，等等，从而提供更好的压缩效果)。