StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The generation problem (uniqueness of decoding) can be guaranteed by building a binary tree of n leaf nodes, and enumerating the position of each such node in the tree (0 is left branch, 1 is right branch). And you are right, Huffman Trees have this property. Note that for Huffman Trees, each node is given a weight equal to the frequency of its representative character, and the tree is built with a recursive property that the left-right decision on node joins is based on the sum of the children to that point. This cumulative sum property is also why a Fibonacci distribution gives the worst-case compression for Huffman Trees.</p> <p>Note, Huffman encoding is optimal for variable encoding of fixed alphabets. An example of a non-fixed alphabet is the decision to treat " the " as a single element in your set to be compressed (as opposed to two spaces and one each of the letters). </p> <p>Your problem appears to not be substitution related. You just want prefix codes for n elements where the sum of the lengths of all prefix codes is minimized. This is the same as building a Huffman tree where every element frequency is 1 (because it guarantees the minimum encoding of the total encoded string, which for you is equal to the sum of the bits of every encoded element exactly once, i.e. minimizing the total bits). Note: this guarantees the minimum encoding, it does not guarantee the fastest implementation. You probably do not need to build a tree for each method call. Unfortunately, I don't know an implementation off the top of my head.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload