Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2007 Copyright 2007 Universität Bonn, Institut für Informatik, Abt. V
85281

13.07.2007

A Fast Algorithm for Adaptive Prefix Coding
Marek Karpinski and Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we present a new algorithm for adaptive prefix coding. Our algorithm encodes a text S of m symbols in O(m) time, i.e., in O(1) amortized time per symbol. The length of the encoded string is bounded above by (H+1)m +O(n log 2m) bits where n is the alphabet size and H is the entropy.

This is the first algorithm that adaptively encodes a text in O(m) time and achieves an almost optimal bound on the encoding length in the worst case. Besides that, our algorithm does not depend on an explicit code tree traversal.

Last Change: 12/05/07 at 09:36:28
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope