huffman-code - 扩展霍夫曼码

Question

我有这个作业：找到任何给定字母表中符号的代码字。它说我必须对三个符号组使用二进制霍夫曼。这到底是什么意思？我是否在 [字母]^3 上使用常规霍夫曼？如果是这样，那么我该如何区分一组中的 3 个符号？

Answer 1

我不太清楚，因为您对问题的描述并不是那么详细，但我猜想它们的意思是，与其单独编码字母表中的每个符号，不如将每三个符号作为一个组来处理.

因此，例如，如果您的字母表由a、b和组成c，而不是为每个单独生成一个编码，您将为 、 、 等创建一个编码aaa。aab这些aac字符串中的每一个都将被视为一个单独的符号霍夫曼算法；您可以通过对它们进行字符串比较来区分它们。如果您需要接受任意长度的输入，您还需要在字母表中包含长度为 1 或 2 的字符串。例如，如果您正在对 string 进行编码，则aabacab需要将其分解为符号aab, aca, 和b.

这有助于回答你的问题吗？我不太确定你在找什么，所以如果这还没有解决任何问题，请随时编辑你的问题或在评论中回复。

Answer 2

深思：较短的字符串和“块边界”的排列呢？1 和 2 个字符串呢？您是否只是在输入文本中计算 3、6、9、12、... 字符，然后在最后填充任何不均匀的长度？

如果块可以是可变大小的，那么找到最合适的就很有趣了。我怀疑它会退化为旅行推销员类型的问题，但也许有一个简洁的“定理”或其他工具可以解决这类问题。

也许尝试 3 个字符的所有排列，保存最常用的字符，然后尝试为 1 和 2 个字符的长间隙提供一个很好的拟合？嗯，听起来可能真的很慢，但使用某种递归除法方法是可行的：拉出块长度为 N 的长字符串，然后递归将间隙编码为长度 N - 1。

恐怕问题多于答案。