Algorithmica, volume 55, issue 1, pages 29-41
A Fast Algorithm for Adaptive Prefix Coding
Publication type: Journal Article
Publication date: 2007-12-14
Computer Science Applications
Applied Mathematics
General Computer Science
Abstract
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(nlog 2 m) 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.
Found
Found
Top-30
Journals
|
1
2
|
|
|
Lecture Notes in Computer Science
2 publications, 40%
|
|
|
Information Processing Letters
1 publication, 20%
|
|
|
European Journal of Combinatorics
1 publication, 20%
|
|
|
IEEE Transactions on Information Theory
1 publication, 20%
|
|
|
1
2
|
Publishers
|
1
2
|
|
|
Elsevier
2 publications, 40%
|
|
|
Springer Nature
2 publications, 40%
|
|
|
Institute of Electrical and Electronics Engineers (IEEE)
1 publication, 20%
|
|
|
1
2
|
- We do not take into account publications without a DOI.
- Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
Cite this
GOST |
RIS |
BibTex |
MLA
Cite this
RIS
Copy
TY - JOUR
DO - 10.1007/s00453-007-9140-4
UR - https://doi.org/10.1007/s00453-007-9140-4
TI - A Fast Algorithm for Adaptive Prefix Coding
T2 - Algorithmica
AU - KARPINSKI, MAREK
AU - NEKRICH, YAKOV
PY - 2007
DA - 2007/12/14
PB - Springer Nature
SP - 29-41
IS - 1
VL - 55
SN - 0178-4617
SN - 1432-0541
ER -
Cite this
BibTex (up to 50 authors)
Copy
@article{2007_KARPINSKI,
author = {MAREK KARPINSKI and YAKOV NEKRICH},
title = {A Fast Algorithm for Adaptive Prefix Coding},
journal = {Algorithmica},
year = {2007},
volume = {55},
publisher = {Springer Nature},
month = {dec},
url = {https://doi.org/10.1007/s00453-007-9140-4},
number = {1},
pages = {29--41},
doi = {10.1007/s00453-007-9140-4}
}
Cite this
MLA
Copy
KARPINSKI, MAREK, and YAKOV NEKRICH. “A Fast Algorithm for Adaptive Prefix Coding.” Algorithmica, vol. 55, no. 1, Dec. 2007, pp. 29-41. https://doi.org/10.1007/s00453-007-9140-4.