What is the complexity of computing optimal prefix free codes, when the frequencies are similar?

Question

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:

1. 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)$

2. 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

---

1. 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.

2. 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.

3. 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.

Answer 1

It took a few years (five!), but here is a partial answer to the question:

http://arxiv.org/abs/1602.00023

Optimal Prefix Free Codes With Partial Sorting Jérémy Barbay (Submitted on 29 Jan 2016)

We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in time within O(n(1+lgα))⊆O(nlgn), where the alternation α∈[1..n−1] measures the amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size n and alternation α. Such results refine the state of the art complexity of Θ(nlgn) in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort a multiset depending on the queries on it (known since 1988).