哈夫曼树用于非二进制字母表？ [英] Huffman trees for non-binary alphabets?

问题描述

有哈夫曼编码的情况下所产生的字母不是二进制树一个简单的概括？举例来说，如果我想COM preSS一些文字写出来的三元，我仍然可以建立的每个字符我一个preFIX无编码系统为写出。请问霍夫曼建设（使用k元树，而不是二进制树）的直接推广仍能正常工作，有效地？还是这种结构导致了非常低效的编码方案？

Is there an easy generalization of Huffman coding trees for situations where the resulting alphabet is not binary? For instance, if I wanted to compress some text by writing it out in ternary, I could still build up a prefix-free coding system for each character I as writing out. Would the straightforward generalization of the Huffman construction (using a k-ary tree rather than a binary tree) still work correctly and efficiently? Or does this construction lead to a highly inefficient coding scheme?

推荐答案

该算法仍然有效，它仍然简单 - 事实上，维基百科有一个简短提及的 n元Huffman编码援引原霍夫曼纸张的来源。

The algorithm still works and it's still simple — in fact Wikipedia has a brief reference to n-ary Huffman coding citing the original Huffman paper as a source.

有确实发生对我来说，虽然，正如霍夫曼是略微次优的，因为它分配比特的整数倍，以每一个符号（不像例如算术编码），三元霍夫曼应该是一点点的更多的次优的，因为它要分配的的 trits 。不是作秀，塞，尤其是对于只有3个，但它确实表明，n元霍夫曼将进一步为您提高ñ落后于其它编码算法。

It does occur to me, though, that just as Huffman is slightly suboptimal because it allocates an integer number of bits to each symbol (unlike e.g. Arithmetic coding), ternary Huffman should be a little bit more suboptimal because it has to allocate an integer number of trits. Not a show-stopper, especially for only 3, but it does indicate that n-ary Huffman will fall further behind other coding algorithms as you increase n.

这篇关于哈夫曼树用于非二进制字母表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！