### Optimal Prefix Free Codes With Partial Sorting

**2016-01-29**

1602.00023 | cs.DS

We describe an algorithm computing an optimal prefix free code for $n$
unsorted positive weights in time within $O(n(1+\lg \alpha))\subseteq O(n\lg
n)$, where the alternation $\alpha\in[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 $\alpha$. Such
results refine the state of the art complexity of $\Theta(n\lg n)$ 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).

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-03-01**

1903.00227 | cs.DS

Data structures for efficient sampling from a set of weighted items are an
important building block … show more

**2019-02-14**

1902.05224 | cs.DS

Converting a compressed format of a string into another compressed format
without an explicit decomp… show more

**2019-03-01**

1903.00507 | cs.DS

We design the first learned index that solves the dictionary problem with
time and space complexity … show more

**2019-02-13**

1902.04692 | cs.NE

Although the performance of base-line Evolutionary Algorithms (EAs) on linear
functions has been stu… show more

**2018-08-12**

1808.03978 | cs.DS

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries
in text compression an… show more

**2019-03-06**

1903.02533 | cs.DS

The range-minimum query (RMQ) problem is a fundamental data structuring task
with numerous applicati… show more

**2018-02-18**

1802.06440 | cs.DS

One of the most fundamental problems in Computer Science is the Knapsack
problem. Given a set of n i… show more

**2018-06-05**

1806.01804 | cs.DS

We present the first solution to $\tau$-majorities on tree paths. Given a
tree of $n$ nodes, each wi… show more

**2019-03-22**

Massively parallel join algorithms have received much attention in recent
years, while most prior wo… show more

**2019-03-19**

1903.08014 | cs.DS

We revisit the range sampling problem: the input is a set of points where
each point is associated w… show more

**2018-06-21**

1806.08182 | cs.DS

Motivated by crowdsourced computation, peer-grading, and recommendation
systems, Braverman, Mao and … show more

**2018-04-23**

1804.08731 | cs.DS

In the longest common substring (LCS) problem, we are given two strings $S$
and $T$, each of length … show more

**2018-07-10**

1807.03611 | cs.DS

While FPGAs have been used extensively as hardware accelerators in industrial
computation, no theore… show more

**2019-02-10**

1902.03534 | cs.DS

We study the classic set cover problem from the perspective of sub-linear
algorithms. Given access t… show more

**2018-12-05**

1812.02023 | cs.DS

Clustering is a fundamental tool for analyzing large data sets. A rich body
of work has been devoted… show more

**2018-07-25**

1807.09524 | cs.DC

We present the first near-linear work and poly-logritharithmic depth
algorithm for computing a minim… show more

**2012-07-07**

1207.1794 | cs.DS

Combinatorial optimization is widely applied in a number of areas nowadays.
Unfortunately, many comb… show more