# Optimal Prefix Free Codes with Partial Sorting +
## 1 Introduction
### Background  
Any prefix free code can be computed in time linear in the input size from a set of code lengths satisfying the Kraft inequality \(\sum_{i=1}^{n}D^{-L[i]}\leq 1\). The original description of the code by [PERSON] [1] yields a heap-based algorithm performing \(O(n\log n)\) algebraic operations, using the bijection between \(D\)-ary prefix free codes and \(D\)-ary cardinal trees [12]. In order to consider the optimality of this running time, one must notice that this algorithm is not in the comparison model (as it performs sums on elements of its input), but still in a quite restricted computational model, dubbed the algebraic decision tree computational model [13], composed of algorithms which can be modeled as a decision tree where decision nodes are based only on algebraic operations with a finite number of operators. In the algebraic decision tree computational model, the complexity of the algorithm suggested by [PERSON] [1] is asymptotically optimal for any constant value of \(D\), in the worst case over instances composed of \(n\) positive weights, as computing the optimal prefix free code for the \((D\times n+1)\) weights \(W[0,\ldots,Dn]=\{D^{x_{1}},\ldots,D^{x_{1}},D^{x_{2}},\ldots,D^{x_{2}},\ldots,D^{x_{n}},\ldots,D^{x_{n}}\}\) is equivalent to sorting the positive integers \(\{x_{1},\ldots,x_{n}\}\), a task proven to require \(\Omega(Dn\log(Dn))=\Omega(n\log n)\) (as \(D\) is a constant) in the algebraic decision tree model, by a simple argument of information theory.  
Yet, not all instances require the same amount of work to compute an optimal code (see Table 1 for a partial list of relevant results):  
* When the weights are given in sorted order, [PERSON] [14] showed in 1976 that an optimal code can be computed using within \(O(n)\) algebraic operations.
* When the weights consist of \(r\in[1..n]\) distinct values and are given in a sorted, compressed form, [PERSON] and [PERSON] [15] showed in 1998 how to compute an optimal binary prefix free code using within \(O(r(1+\log(n/r)))\) algebraic operations, which is sublinear in \(n\) when \(r\in o(n)\).
* In the case where the weights are given unsorted, [PERSON] and [PERSON] [16; 17] described in 2006 many families of instances for which an optimal binary prefix free code can be computed in linear time.  
Such example of \"easy instances\" suggest that it could be possible to compute optimal prefix free codes in much less time by taking advantage of some measure of \"easiness\", and indeed [PERSON] and [PERSON] [16; 17] proposed an algorithm claimed to perform within \(O(kn)\) algebraic operations, in the worst case over instances formed by \(n\) weights such that the binary prefix free code obtained by [PERSON]'s method [1] has exactly \(k\) distinct code lengths. The proof included in the proceedings yields only a bound within \(O(16^{k}n)\), while the claim of a complexity within \(O(kn)\) was later downgraded to \(O(16^{k}n)\) in extended versions of their article published on public repositories [17]. Such result is asymptotically better than the state of the art when \(k\) is finite, but worse when \(k\) is larger than \(\log_{2}n\), which does not seem to be the case in practice (see our own experimental results in Table 3).