Алгоритм декодирования Хаффмана

Question

У меня возникла проблема с построением структуры дерева Хаффмана при декодировании.

Прямо сейчас я кодирую дерево, если у него есть дети, делающие префикс 0, и если у него нет ребенка, сделайте это 1.

Например, дерево, как (a,b,c,d) бы быть закодированы как 001a1b01c1d и их код Хаффмана

00|01|10|11 

Примечание: | была добавлена ​​для ясности и фактически не является в заголовке.

Вот дерево в графической форме:

/\ 
    /\ /\ 
    a b c d 

Прямо сейчас, когда я пытаюсь восстановить дерево с помощью 001a1b01c1d, проблема у меня возникли проблемы воссоздает дерево правильно, потому что я не уверен, что проверять когда вы возвращаетесь к дереву (как далеко продвигаться).

Here is the code the index was only added just to try the word 'random' obviously it doesn't work for other cases. I am thinking of using the depth of the tree somehow

void Tree::build(std::queue<char> encodedHeader) { 
    char currentChar; 
    this -> thisRoot = new HCNode(0, '\0',0,0,0); 
    HCNode * newRoot = new HCNode (0,'\0',0,0,0); 
    HCNode * childZero = new HCNode (0, '\0', 0,0,0); 
    HCNode * childOne = new HCNode (0, '\0', 0,0,0); 
    childZero -> p = newRoot; 
    childOne -> p = newRoot; 
    newRoot -> c0 = childZero; 
    newRoot -> c1 = childOne; 
    this -> foreverRoot = newRoot; 

    while(!header.empty()) { 
     currentChar = header.front(); 
     header.pop(); 
     if(currentChar != '\n') { 
      if (currentChar == '0') { 
       HCNode * childZero = new HCNode (0, '\0', 0,0,0); 
       HCNode * childOne = new HCNode (0, '\0', 0,0,0); 
       child0 -> p = newRoot; 
       child1 -> p = newRoot; 
       newRoot -> c0 = childZero; 
       newRoot -> c1 = childOne; 

       currentChar = header.front(); 
       while (currentChar == '0') { 
        newRoot = newRoot -> c0; 
        header.pop(); 
        currentChar = header.front(); 
        HCNode * childZero = new HCNode (0, '\0', 0,0,0); 
        HCNode * childOne = new HCNode (0, '\0', 0,0,0); 
        childZero -> p = newRoot; 
        childOne -> p = newRoot; 
        newRoot -> c0 = childZero; 
        newRoot -> c1 = childOne; 
       } 
      } 
      else { 
       currentChar = header.front(); 
       header.pop(); 

       if(newRoot -> c0 != NULL) { 
        newRoot -> c0 -> symbol = currentChar; 
        newRoot = newRoot -> c1; 
       } 
       else { 
        newRoot -> symbol = currentChar; 
        while(newRoot -> p != NULL && index != 2) { 
         index++; 
         newRoot = newRoot -> p; 
        } 
        index = 0; 
        newRoot = newRoot -> c1; 
       } 
      } 
     } 
    } 

Answer 1

Я буквально только что написал код, чтобы сделать это упражнение, и вы используете точно такой же формат заголовка, как я. Трюк я обнаружил, что это гораздо проще реализовать рекурсивно, как:

Node read_tree(some_input input, string current_code = "") { 
    Node node; 
    if (input.readchar() == '0') { 
     node.left = read_tree(input, current_code + "0"); 
     node.left.parent = node; 
     node.right = read_tree(input, current_code + "1"); 
     node.right.parent = node; 
    } else { 
     node.code = input.readchar(); 
    } 
    return node; 
} 

Очевидно, что вам нужно сделать что-то подобное с использованием собственных более реалистичных типов, но основная идея должна работать.

Answer 2

Прежде всего, я очень сожалею о своем английском (это не мой родной язык :-). Как правило, рекурсия решает проблемы с деревьями, и это хороший совет здесь. вот код, который я думаю, может быть работа (я не проверял, так что возможно это нужно немного работы будет):

buildTree(std::queue<char> header, HCNode* node) 
{ 
    char currentChar = header.front(); 
    header.pop(); 
    if(currentChar == '0') 
    { 
      childZero -> p = newRoot; 
      childOne -> p = newRoot; 
      node->c0 = new HCNode (0, '\0', 0,0,0); 
      node->c1 = new HCNode (0, '\0', 0,0,0); 
      node->c0->p = node; 
      node->c1->p = node; 
      buildTree(header, node->c0); // this is the recurtion 
      buildTree(header, node->c1); // this is the recurtion too 
    } 
    else // currentChar == '1' 
    { 
      currentChar = header.front();// currentChar = symbol 
      header.pop(); 
      node-> symbol = currentChar; 
    } 
} 
void Tree::build(std::queue<char> encodedHeader) 
{ 
    this->foreverRoot = new HCNode(0, '\0',0,0,0); 
    buildTree(header, foreverRoot); 
} 

я надеюсь, что это будет полезно. удачи.