Skip to main content

New answers tagged

16 votes
Accepted

Any algorithm to do Huffman encoding without using graphs?

If you're allowed to reorder the symbols, then the answer is yes. We'll approach this in three stages. Linear-time Huffman tree construction First things first. If the symbols are sorted into order of ...
Pseudonym's user avatar
  • 22.5k
2 votes

Expected Entropy of the Empirical Distribution

Edit: Added some major optimizations Not a closed form equation for the expected entropy, but an algorithm to compute it. Here $n$ is the number of outcomes with probabilities $[p_1, p_2, \dots, p_n]$,...
EnEm's user avatar
  • 664

Top 50 recent answers are included