0
$\begingroup$

I have implemented huffman encoding in the form

struct node
{
    node * left;
    node * right;
    double freq; // the frequency
    string letter;
    string binary_code; // the variable length code
};

that works fine, eg:

Data: electric eels
Compressed: -σ» //doesnt render in this text editor sorry
Decompressed: electric eelss
Ratio: 38%

But I have no idea how to efficiently encode the tree itself (needed for the decompression) to send over socket, and then decode it.

Can someone help me with some c code/pseudocode style explanation?

Any help appreciated.

$\endgroup$
2
$\begingroup$

The usual approach is to build Canonical Huffman code from the frequencies and use it to encode the data.

Canonical Huffman code can be encoded in a pretty compact way, as was described in the ZIP APPNOTE.TXT file, look for words Shannon-Fano and Huffman.

You can find C code in any deflate/inflate implementation or Huff0.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, wouldn't deserialization be O(n^2) then? as you'd have to loop over each code and each character in encoded string. It feels like there would be a O(n*m + log(n)) solution for some reason $\endgroup$ – BinkyNichols Jul 16 '19 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.