c - C中的霍夫曼编码

Question

我正在尝试编写一个模块，将霍夫曼编码的单词分配给输入符号，但给定的代码与它们应有的样子不同。

例如，如果我使用以下符号概率运行它:

(第 1 列:概率；第 2 列:我的霍夫曼代码；第 3 列:正确的霍夫曼代码)

0,25 --> 01 --> 10

0,15 --> 101 --> 111

0,15 --> 110 --> 110

0,1 --> 1111 --> 010

0,1 --> 000 --> 001

0,05 --> 0010 --> 0110

0,05 --> 0011 --> 0001

0,05 --> 1000 --> 0000

0,05 --> 1001 --> 01111

0,05 --> 1110 --> 01110

我认为问题可能出在我的生成霍夫曼代码函数中，因为strcat() 函数的行为最初对我的想法不利，所以我将其合并使用 strcat()。不确定这样是否好。

我为您提供了两个负责代码分配的函数，build_huffman_tree() 和generate_huffman_tree()，希望您能帮我解决这个问题，并指出在哪里问题可能是。

生成古夫曼树:

void generate_huffman_tree(node *n, char *code){
if(n->left== NULL && n->right== NULL){
    SYMBOLS[code_counter] = n->symbol; // this 3 lines just store current code, not important
    CODES[code_counter] = strdup(code);
    code_counter += 1;
}
if(n->left!= NULL){
    char temp[100];
    strcpy(temp, code);
    strcat(temp, "0");
    generate_huffman_tree(n->left, temp);
}
if(n->right!= NULL){
    char temp[100];
    strcpy(temp, code);
    strcat(temp, "1");
    generate_huffman_tree(n->right, temp);
}

构建霍夫曼树:

node *build_huffman_tree(double *probabilities){

int num_of_nodes = NUM_SYMBOLS;
int num = NUM_SYMBOLS;

// 1) Initialization: Create new node for every probability
node *leafs = (node*) malloc(num_of_nodes*sizeof(node));
int i;
for(i=0; i<num_of_nodes; i+=1){
    node c;
    c.probability= *(probability+ i);
    c.symbol= *(SYMBOLS + i);
    c.left= NULL;
    c.right= NULL;
    *(leafs+i) = c;
}

node *root= (node*) malloc(sizeof(node)); // Root node which will be returned

while(num_of_nodes> 1){

    // 2) Find 2 nodes with lowest probabilities
    node *min_n1= (node*)malloc(sizeof(node));
    node *min_n2 = (node*)malloc(sizeof(node));

    *min_n1 = *find_min_node(leafs, num, min_n1);
    leafs = remove_node(leafs, min_n1, num); 
    num -= 1;

    *min_n2= *find_min_node(leafs, num, min_n2);
    leafs = remove_node(leafs, min_n2, num);
    num -= 1;

    // 3) Create parent node, and assign 2 min nodes as its children
            // add parent node to leafs, while its children have been removed from leafs
    node *new_node = (node*) malloc(sizeof(node));
    new_node->probabilty= min_n1->probability + min_n2->probability;
    new_node->left= min_n1;
    new_node->right= min_n2;

    leafs = add_node(leafs, new_node, num);
    num += 1;

    num_of_nodes -= 1;

    root = new_node;
}

return root;

我已经测试了用于查找 2 分钟节点、向叶子结构中删除和添加节点的函数，事实证明它工作正常，所以我想问题应该出在此处。

Answer 1

我没有看你的源代码，但是你生成的哈夫曼代码没有任何问题。您所说的“正确的霍夫曼代码”也没有错。该组概率可能有不止一个有效的霍夫曼代码。如果将两个霍夫曼代码的概率和乘以比特长度，您会发现这些和完全相同。两种霍夫曼编码都是最优的，尽管它们不同。

发生这种情况的方式是，当您寻找两个最低频率时，有不止一个选择。根据您做出的选择，您将获得不同的树。