A O(N) semipredictive universal encoder via the BWT

Dror Baron, Yoram Bresler

Research output: Contribution to journalLetter

Abstract

We provide an O(N) algorithm for a nonsequential semipredictive encoder whose pointwise redundancy with respect to any (unbounded depth) tree source is O(1) bits per state above Rissanen's lower bound. This is achieved by using the Burrows-Wheeler transform (BWT), an invertible permutation transform that has been suggested for lossless data compression. First, we use the BWT only as an efficient computational tool for pruning context trees, and encode the input sequence rather than the BWT ouput. Second, we estimate the minimum description length (MDL) source by incorporating suffix tree methods to construct the unbounded depth context tree that corresponds to the input sequence in O(N) time. Third, we point out that a variety of previous source coding methods required superlinear complexity for determining which tree source state generated each of the symbols of the input. We show how backtracking from the BWT output to the input sequence enables to solve this problem in O(N) worst case complexity.

Original languageEnglish (US)
Pages (from-to)928-937
Number of pages10
JournalIEEE Transactions on Information Theory
Volume50
Issue number5
DOIs
StatePublished - May 1 2004

Keywords

  • Burrows-Wheeler transform (BWT)
  • Context tree pruning
  • Data compression
  • Dynamic programming
  • Lossless source coding
  • Minimum description length (MDL)
  • Suffix trees
  • Tree sources
  • Universal coding

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Information Systems

Fingerprint Dive into the research topics of 'A O(N) semipredictive universal encoder via the BWT'. Together they form a unique fingerprint.

  • Cite this