Questions tagged [huffman]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers

Are there any practical applications of a faster algorithm to compute Huffman codes?

Which practical problem would benefit from a technique to compute optimal prefix free codes faster (say, faster than O(sigma log sigma) on sigma input symbols)? When compressing a source of n symbols ...
J..y B..y's user avatar
  • 2,733
8 votes
1 answer

Original reference for Huffman shaped Merge Sort?

What is the first publication of the concept of optimizing merge sort by identifying sequences of consecutive positions in increasing orders (aka runs) in linear time; then repeatedly merging the ...
J..y B..y's user avatar
  • 2,733
1 vote
1 answer

Does Huffman coding always produce shorter codes than the Shannon code?

Let $X\in\{1,2,\ldots,m\}$ be a discrete random variable with $X\sim p$. Let $C$ be a code for $X$ with $l_i$ being the length $i$-th codeword and let $L(C)$ be the expected length of the code. The ...
Christian Bueno's user avatar