Dynamic Shannon coding

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book , Preprint , Conference object 01 Jan 2004Embargo end date: 01 Jan 2005 English Publisher:Elsevier BVJournal:Information Processing Letters, volume 102, pages 113-117 (issn: 0020-0190,

Copyright policy )Funded by:NSERC | unidentified

Authors: Travis Gagie;

doi: 10.1016/j.ipl.2006.09.015 , 10.1007/978-3-540-30140-0_33 , 10.1109/dcc.2004.1281516 , 10.48550/arxiv.cs/0503085

arXiv: cs/0503085

Dynamic Shannon coding

- Summary
- Subjects
- Metrics

Abstract

We present a new algorithm for dynamic prefix-free coding, based on Shannon coding. We give a simple analysis and prove a better upper bound on the length of the encoding produced than the corresponding bound for dynamic Huffman coding. We show how our algorithm can be modified for efficient length-restricted coding, alphabetic coding and coding with unequal letter costs.

6 pages; conference version presented at ESA 2004; journal version submitted to IEEE Transactions on Information Theory

Related Organizations

University of Toronto
Canada

Keywords

FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT), E.4, Source coding, data compression, on-line algorithms

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	9
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average