DocumentCode
3032913
Title
Linear-time construction of optimal context trees
Author
Helfgott, Harald ; Cohn, Martin
Author_Institution
Brandeis Univ., Waltham, MA, USA
fYear
1998
fDate
30 Mar-1 Apr 1998
Firstpage
369
Lastpage
377
Abstract
We show how to construct an optimal context tree for a given plaintext and context order. Our algorithm runs in time linear in the size of the plaintext and the size of the context, and consumes space linear in the size of the plaintext. We evaluate the algorithm´s performance on the CCITT test set for bilevel images with the Euclidean-norm context order
Keywords
data compression; image coding; optimisation; trees (mathematics); CCITT test set; Euclidean-norm context order; bilevel images; context order; context size; image compression; linear space size; linear-time construction; optimal context trees; optimal tree; performance; plaintext order; time linear algorithm; Arithmetic; Binary trees; Context modeling; Costs; Image coding; Linearity; Machinery; Testing;
fLanguage
English
Publisher
ieee
Conference_Titel
Data Compression Conference, 1998. DCC '98. Proceedings
Conference_Location
Snowbird, UT
ISSN
1068-0314
Print_ISBN
0-8186-8406-2
Type
conf
DOI
10.1109/DCC.1998.672167
Filename
672167
Link To Document