ML p(r)ior | Optimal Prefix Free Codes With Partial Sorting

### 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).

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-02-14
1902.05224 | cs.DS

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-02-13
1902.04692 | cs.NE

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

Highlights - Most important sentences from the article

2018-08-12
1808.03978 | cs.DS

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

Highlights - Most important sentences from the article

2019-03-06
1903.02533 | cs.DS

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-03-22
1903.09717 | cs.DB

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-06-21
1806.08182 | cs.DS

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-07-10
1807.03611 | cs.DS

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2012-07-07
1207.1794 | cs.DS

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