Published Articles >> Table of Contents >> Abstract

Data Compression Conference (DCC '04)   p. 372
Linear Time Universal Coding of Tree Sources via FSM Closure
Alvaro Martin, Universidad de la República, Montevideo, Uruguay
Gadiel Seroussi, Hewlett-Packard Laboratories, Palo Alto, CA
Marcelo J. Weinberger, Hewlett-Packard Laboratories, Palo Alto, CA

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.2004.1281482
Send link to a friend

Abstract
Applying generalized context trees and their finite state machine closures, we show that a two-pass version of Context a twice-universal lossless coding scheme for tree models, can be implemented in linear encoding/decoding time. As it turns out, an optimal context selection rule and the corresponding context transitions are computationally not more expensive than the various steps involved in the implementation of the Burrows-Wheeler transform (BWT) and use, in fact, similar tools. We also present a reversible transform that displays the same "context deinterleaving" feature as the BWT but is naturally based on an optimal context tree. This transform offers insight into the workings of the BWT and the nature of its sub-optimality for twice-universal coding of tree models.
Back to Top Additional Information
Citation:  Alvaro Martin, Gadiel Seroussi, Marcelo J. Weinberger, "Linear Time Universal Coding of Tree Sources via FSM Closure," dcc, p. 372,  Data Compression Conference (DCC '04),  2004