霍夫曼解碼算法

Question

解碼時，我無法構建哈夫曼樹的結構。

現在我正在編碼的樹，如果它有子碼使前綴0，如果它沒有孩子使它1。

例如，像(a,b,c,d)樹會被編碼爲001a1b01c1d及其Huffman編碼是

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

我很希望這將是有益的。祝你好運。