Efficient serialization/deserialization of huffman tree

Question

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.

Answer 1

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.