如何生成霍夫曼树的二进制代码 table？

Question

我想实现一个函数，它为哈夫曼树中的每个字符提供一个二进制代码。

为了实现该功能，我尝试使用递归函数遍历 table。但是我不知道如何将结果填充为每个字符的二进制代码，以便函数 returns 一个包含所有字符和二进制代码的结构数组

我希望有人能指出我正确的方向。

提前致谢！

Answer 1

好的，让我们看看可能的解决方案：

#include <stdint.h>

typedef struct code {
    size_t code_length;
    uint32_t code;
} code;

void compute_code_table(tree_t node, code *t, code c) 
{
    if (node->left == NULL) 
        t[node->letter] = c;
    else {
        c.code_length++;
        c.code <<= 1;
        compute_code_table(node->left, t, c);
        c.code += 1;
        compute_code_table(node->right, t, c);
    }
}

void code_print(code *c)
{
    size_t n = c->code_length;
    while (n --> 0)
        putchar('0' + ((c->code >> n) & 1));
}

int main(void)
{
    tree_t root = fixed_tree();
    code table[256] = { 0 };
    code c = { 0 };
    compute_code_table(root, table, c);

    for (size_t i = 0; i < 256; ++i) {
        if (table[i].code_length) {
            printf("%c\t", i);
            code_print(table + i);
            printf("\n");
        }
    }
}

基本上，我们的想法是在每片叶子处填充一个 table。在执行递归时，我们传递当前节点、table 和当前代码。如果我们在叶子上，我们只将代码存储在 table 中，否则我们需要执行递归：增加代码长度，在最低有效位添加 0 并执行左分支，然后更改该 0到 1 并做正确的分支。

Answer 2

我将从 compute_code_table 递归开始，这使您可以轻松遍历树。

其次，在线搜索一些解释（以伪代码或非伪代码）如何完成特定任务的资源有助于每项任务或分配。在这种情况下，这会产生以下解释：

To generate a huffman code you traverse the tree to the value you want, outputing a 0 every time you take a lefthand branch, and a 1 every time you take a righthand branch. (normally you traverse the tree backwards from the code you want and build the binary huffman encoding string backwards as well, since the first bit must start from the top).

siggraph.org

在 C 中，可以这样实现：

int compute_code_table_for_node(tree_t tree, node_t target_node, node_t current_node, int code_table) {
    // Check for target
    if ( current_node == target_node ) {
        // Found target
        return code_table;
    }

    // Check if end-node
    if ( current_node->left == NULL && current_node->right == NULL ) {
        // Is an end node
        return -1;
    }


    // Try left
    int left = compute_code_table_for_node(tree, target_node, current_node->left, code_table << 1 + 0);

    // Try right
    int right = compute_code_table_for_node(tree, target_node, current_node->right, code_table << 1 + 1);

    // Find which path was taken
    if ( left == -1 ) {
        // Left path didn't find it, so it must be the right path:
        return code_table << 1 + 1;
    } else {
        // Left path found it
        return code_table << 1 + 0;
    }
}

那么您只需为 tree 中的每个 node 调用 compute_code_table_for_node(tree, node, tree->head, 0)。

这段代码不适用于您的特定情况，因此您必须重写它。

如何生成霍夫曼树的二进制代码 table？

How can i generate a binary code table of a huffman tree?

c

algorithm

tree

huffman-code