Decoding a Huffman Tree

Question

I'm trying to decode a Huffman tree of the form:

001A1C01E01B1D

I'm using an implementation found here: Efficient way of storing Huffman tree to encode the tree in the form above and decode it as well.

This is my implementation of it:

HuffmanNode* HuffmanTree::decodeTree(string tree, int idx) {
    cout << idx << endl;
    if (tree[idx] == '1') {
        idx += 2;
        return new HuffmanNode(tree[idx - 1]);
    }
    else {
        if (idx != tree.length() - 1) {
            idx++;
            HuffmanNode* leftChild = decodeTree(tree, idx);
            idx++;
            HuffmanNode* rightChild = decodeTree(tree, idx);
            return new HuffmanNode(leftChild, rightChild);
        }
        else
            return new HuffmanNode(tree[idx]);
    }
}

I'm getting an access violation writing a location when the function unwinds (On "return new HuffmanNode(tree[idx - 1]);" ), and I'm hoping that the final return would be the root of the tree, but upon further inspection this doesn't seem to be the case. Can anyone give me some pointers? (No pun intended)

are you expecting idx to be shared between the recursive calls? if so you'll need to make it a reference in the parameter list. Also you could probably do with adding in some bounds safety checks (with appropriate errors); as it stands this would be tripped up by any string ending in "1", for example. — Dave

Kolmar Kolmar · Accepted Answer · 2015-04-02T19:56:42

The problem with your code is that idx is not modified inside recursive runs. Pass it into the function as int &: HuffmanNode* HuffmanTree::decodeTree(string tree, int &idx)

There is also one more bug in your code, which makes it segfault: instead of

if (tree[idx] == '1') {
    idx += 2;
    return new HuffmanNode(tree[idx - 1]);
}

you should have

if (tree[idx] == '1') {
    ++idx;
    return new HuffmanNode(tree[idx]);
}

Another 1 is being added to index within the second block:

idx++;
HuffmanNode* leftChild = decodeTree(tree, idx);
idx++;
HuffmanNode* rightChild = decodeTree(tree, idx);

Also, consider doing a thing, similar to the example you have linked to: pass reference to a string iterator, (or an istringstream, or some other stream) and don't pass an index: HuffmanNode* HuffmanTree::decodeTree(std::string::const_iterator &tree).

Also, you don't have to do checks like if (idx != tree.length() - 1) if the tree is well-formed. You may still do that at the start of the function to check for errors in your input, along with checks that current symbol is either '0' or '1'.

Decoding a Huffman Tree

1 Answers