Questions tagged [huffman]
The huffman tag has no usage guidance.
3
questions
4
votes
0
answers
67
views
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 ...
- 2,733
8
votes
1
answer
306
views
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 ...
- 2,733
1
vote
1
answer
492
views
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 ...
- 203