It is well known that there is a worst case optimal algorithm to compute the Huffman code in time $\theta(n\lg n)$. This is improved in two orthogonal ways:
Optimal prefix free codes can be computed faster if the set of distinct frequencies is small (e.g. of size $\sigma$): sort the frequencies using [Munro and Spira, 1976] so that to take advantage of the small value of $\sigma$, and compute the Huffman tree in linear time from the sorted frequencies. This yields a solution in $O(n\lg\sigma)$
There is an $O(n 16^k)$ algorithm to compute equivalent codes where $k$ is the number of distinct codewords lengths [Belal and Elmasry].
Is there a way to combine those techniques, in order to improve on the current best complexity of $O(n\min\{16^k,\lg\sigma\})$?
THE $O(nk)$ RESULT FROM STACS 2006 SEEM TO BE WRONG, Elmasry published on ARXIV in 2010 (http://arxiv.org/abs/cs/0509015) a version announcing - $O(16^kn)$ operations on unsorted input and - $O(9^k \log^{2k-1} n)$ operations on sorted input
I see an analogy with the complexity of computing the planar convex hull, where algorithms in $O(n\lg n)$ (sorting based, as the $O(n\lg n)$ algorithm for Huffman's code) and in $O(nh)$ (gift wrapping) were superseded by Kirkpatrick and Seidel's algorithm in $O(n\lg h)$ (later proved to be instance optimal with complexity of the form $O(nH(n_1,\ldots,n_k)$). In the case of Prefix Free codes, $O(n\lg n)$ versus $O(nk)$ suggests the possibility of an algorithm with complexity $O(n\lg k)$, or even $O(nH(n_1,\ldots,n_k)$ where $n_i$ is the number of codewords of length $i$, using the analogy of an edge of the convex hull covering $n_i$ points to a code length covering $n_i$ symbols.
A simple example shows that sorting the (rounded) logarithmic values of the frequencies (in linear time in the $\theta(\lg n)$ word RAM model) does not give an optimal prefix free code in linear time:
- For $n=3$, $f_1=1/2-\varepsilon$ and $f_2=f_3=1/4+\varepsilon$
- $\lceil\lg f_i\rceil=2$ so log sorting does not change order
- yet two codes out of three cost $n/4$ bits more than optimal.
Another interesting question would be to reduce the complexity when $k$ is large, i.e. all codes have distinct lengths:
- for instance when $k=n$ the frequencies are all of distinct log value. In this case one can sort the frequencies in linear time in the $\theta(\lg n)$ word RAM, and compute the Huffman code in linear time (because sorting their log values is enough to sort the values), resulting in overall linear time, much better than the $n^2$ from the algorithm from Belal and Elmasry.