algorithm - 非二进制字母的霍夫曼树？

Question

对于生成的字母表不是二进制的情况，霍夫曼编码树是否有一个简单的概括？例如，如果我想通过以三进制写出一些文本来压缩它，我仍然可以为我写出的每个字符建立一个无前缀编码系统。Huffman 构造的直接概括（使用 k-ary 树而不是二叉树）是否仍能正确有效地工作？或者这种结构是否会导致一种非常低效的编码方案？

Answer 1

该算法仍然有效，而且仍然很简单——事实上，维基百科对n 元霍夫曼编码有一个简短的参考，引用了原始的霍夫曼论文作为来源。

不过，我确实想到，正如霍夫曼稍微次优，因为它为每个符号分配整数位数（不像算术编码），三元霍夫曼应该更次优，因为它必须分配一个整数三重奏。不是一个显示停止器，特别是对于只有 3 个，但它确实表明随着 n 的增加，n 元霍夫曼将进一步落后于其他编码算法。

Answer 2

作为一项经验测试，我构建了二叉和三叉哈夫曼树来分配拼字游戏图块。

分布的熵显示每个字母不能超过 4.37 位。

二叉霍夫曼树平均每个字母使用 4.41 位。

三元霍夫曼树平均每个字母使用 2.81 个 trits，其信息密度与每个字母 4.45 位相同。