为什么Huffman树代码需要无符号字符

Question

我正在尝试创建一个霍夫曼树，我看到的问题对我来说很奇怪，它如下:

给定以下数据结构：

struct huffman
{
    unsigned char sym;              /* symbol */
    struct huffman *left, *right;   /* left and right subtrees */
};

编写一个程序，该程序将二进制文件的名称作为唯一参数，构建该文件的霍夫曼树，假设原子（基本符号）是8位无符号字符，并打印树和字典。
分配必须使用 malloc（） 以外的任何东西来完成，排序可以使用 qsort（） 来完成。

这里让我感到困惑的是，要编写一个程序来创建霍夫曼树，我们只需要做以下事情：

1. 我们需要取一个频率数组（可以是Farray[]={……}）
2. 对其进行排序并添加两个最小的节点以形成一棵树，直到它不留下最后一个节点（即头部）

现在问题就在这里：为什么以及在哪里需要这些无符号的字符数据？（这个问题想要什么类型的无符号字符数据，我认为只有频率就足以显示霍夫曼树）？

Answer 1

通常数据压缩分为两个大步骤；给定数据流：

• 评估给定符号出现在流中的概率，换句话说，您评估符号在数据集中出现的频率
• 一旦你研究了这些事件并创建了与概率相关的符号的表，你需要根据它们的概率对符号进行编码，为了实现这个魔法，你创建了一个字典，原来的符号通常只是被另一个尺寸小得多的符号替换，尤其是对于数据集中经常使用的符号，字典会跟踪编码和解码阶段的这种替换。霍夫曼给了你一个算法来自动化这个过程，并获得相当好的结果。

在实践中，它比这更复杂一些，因为涉及树，但主要目的始终是构建字典。

这里有完整的教程。

Answer 2

我这样做已经有一段时间了，但我认为需要生成的“字典”来编码数据，而“树”用于解码它。当然，你总是可以从另一个构建一个。

解码时，您遍历树（左/右，根据连续的输入位），当您击中终端节点（空指针）时，节点中的“sym”就是产出值。

Answer 3

如果您纯粹想显示树的形状，那么是的，您只需要构建它。然而，为了使它有任何用途，您需要知道每个节点代表什么原始符号。

假设您的输入符号是[ABCD]。想象中的霍夫曼树/字典可能如下所示：

         ( )
        /   \              A = 1
      ( )   (A)            B = 00
     /   \                 C = 010
   (B)   ( )               D = 011
        /   \
      (C)   (D)

如果不存储sym，它看起来像这样：

         ( )
        /   \              A = ?
      ( )   ( )            B = ?
     /   \                 C = ?
   ( )   ( )               D = ?
        /   \
      ( )   ( )

不是很有用，是吗？

编辑2：计划中缺少的步骤是步骤0：从文件构建频率数组（不知何故，我错过了您也不需要实际编码文件）。这不是实际的霍夫曼算法本身的一部分，我找不到一个像样的例子来链接，所以这里有一个粗略的想法：

FILE *input = fopen("inputfile", "rb");
int freq[256] = {0};
int c;
while ((c = fgetc(input)) != EOF)
    freq[c]++;
fclose(input);

/* do Huffman algorithm  */
...

现在，这仍然需要改进，因为它既不使用malloc（）也不将文件名作为参数，但这不是我的家庭作业；）