Publications

Stats

View publication

Title Fast and Compact Prefix Codes
Authors Travis Gagie, Gonzalo Navarro, Yakov Nekrich
Publication date 2010
Abstract It is well known that, given a probability distribution over n characters, in the worst case it takes Theta(n log n) bits to store a prefix code with minimum expected codeword length. However, in this paper we first show that, for any 0 \< e \< 1/2 with 1/e = O(polylog(n), it takes O(n log log (1/e)) bits to store a prefix code with expected codeword length within e of the minimum. We then show that, for any constant c > 1, it takes O(n^(1/c) log n) bits to store a prefix code with expected codeword length at most c times the minimum. In both cases, our data structures allow us to encode and decode any character in O(1) time.
Pages 419-427
Conference name Conference on Current Trends in Theory and Practice of Computer Science
Publisher Springer-Verlag (Berlin/Heidelberg, Germany)
Reference URL View reference page