c++ - 哈夫曼解码算法

Question

我在解码时无法构建霍夫曼树的结构。

现在我正在对树进行编码，如果它有 child ，则使用前缀 0，如果没有 child ，则使用 1。

例如，像(a,b,c,d)这样的树将被编码为001a1b01c1d，它们的霍夫曼编码为

00|01|10|11

注意:| 是为清楚起见而添加的，实际上并不在标题中。

这是图形形式的树:

    / \
   /\ /\
  a b c d

现在，当我尝试使用 001a1b01c1d 重建树时，我遇到的问题是正确地重新创建树，因为我不确定返回到树时要检查什么 (上升多远)。

这里是添加索引的代码，只是为了尝试“随机”这个词，显然它不适用于其他情况。我正在考虑以某种方式使用树的深度

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

我实际上只是写了一些代码来做这个练习，而您使用的 header 格式与我所做的完全相同。我发现的技巧是，这更容易递归实现，如:

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

显然，您需要使用自己的更现实的类型来做类似的事情，但基本思想应该可行。