어떻게 huffman 트리의 바이너리 코드 테이블을 생성 할 수 있습니까?

Question

나는 허프만 트리의 각 문자에 대해 이진 코드를 제공하는 함수를 구현하려고합니다.

함수를 구현하려면 재귀 함수를 사용하여 테이블을 탐색 해 보았습니다. 그러나 나는 각 문자에 대한 이진 코드 결과를 채우는 방법을 모르므로 함수가 모든 문자 및 이진 코드와 함께 struct 배열을 반환하도록

누군가가 올바른 방향으로 나를 가리킬 수 있기를 바랍니다.

미리 감사드립니다.

Answer 1

compute_code_table을 재귀 적으로 시작하면 트리를 쉽게 탐색 할 수 있습니다.

둘째, 모든 작업이나 과제가 특정 작업을 수행하는 방법을 (의사 코드로 또는하지 않고) 설명하는 일부 출처를 온라인으로 검색하는 데 도움이됩니다. 이 경우, 이것은 다음과 같은 설명이 산출 :

당신이 공은 왼손 지점을마다하고, 1 마다하고 출력하기, 당신이 원하는 값으로 트리를 탐색 하프 맨 코드를 생성하는 당신 오른 쪽 가지를 가져 가라. (일반적으로 사용자가 원하는 코드에서 트리를 거꾸로 통과하고 이진 호프만 인코딩 문자열을 역방향으로 작성합니다. 첫 번째 비트는 맨 위부터 시작해야하기 때문에).

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)를 호출해야합니다.

이 코드는 특정 사례에 적용되지 않으므로 다시 작성해야합니다.

Answer 2

좋아,의는 가능한 해결책을 보자 :

#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"); 
     } 
    } 
} 

기본적 아이디어는 모든 잎에 가득 테이블을하는 것입니다. 재귀를 수행하는 동안 현재 노드, 테이블 및 현재 코드를 전달합니다. 우리가 리프에 있다면 테이블에 코드를 저장합니다. 그렇지 않으면 재귀를 수행해야합니다. 코드 길이를 늘리고 최하위 비트에 0을 더한 다음 왼쪽 분기를 수행 한 다음 0을 1로 변경하고 오른쪽 가지를해라.