143 citations · 479 across the 107 of their papers we have counts for
Showing 2008Show all
3 papers · 1 filter
cs.IT2008
Worst-Case Optimal Adaptive Prefix Coding
Travis Gagie, Yakov Nekrich
A common complaint about adaptive prefix coding is that it is much slower than static prefix coding. Karpinski and Nekrich recently took an important step towards resolving this: t…
cs.DS2008
Low-Memory Adaptive Prefix Coding
Travis Gagie, Marek Karpinski, Yakov Nekrich
In this paper we study the adaptive prefix coding problem in cases where the size of the input alphabet is large. We present an online prefix coding algorithm that uses $O(σ^{1 / λ…
cs.IT2008★ 1 cited
A New Algorithm for Building Alphabetic Minimax Trees
Travis Gagie
We show how to build an alphabetic minimax tree for a sequence (W = w_1, >..., w_n) of real weights in (O (n d \log \log n)) time, where is the number of distinct integers (\lc…