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

Fingerprint

Data compression
Redundancy
redundancy
coding
symbol

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

Cite this

A O(N) semipredictive universal encoder via the BWT. / Baron, Dror; Bresler, Yoram.

In: IEEE Transactions on Information Theory, Vol. 50, No. 5, 01.05.2004, p. 928-937.

Research output: Contribution to journalLetter

@article{154771daaf974b70bfedad610f23f1f3,
title = "A O(N) semipredictive universal encoder via the BWT",
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.",
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",
author = "Dror Baron and Yoram Bresler",
year = "2004",
month = "5",
day = "1",
doi = "10.1109/TIT.2004.826664",
language = "English (US)",
volume = "50",
pages = "928--937",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "5",

}

TY - JOUR

T1 - A O(N) semipredictive universal encoder via the BWT

AU - Baron, Dror

AU - Bresler, Yoram

PY - 2004/5/1

Y1 - 2004/5/1

N2 - 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.

AB - 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.

KW - Burrows-Wheeler transform (BWT)

KW - Context tree pruning

KW - Data compression

KW - Dynamic programming

KW - Lossless source coding

KW - Minimum description length (MDL)

KW - Suffix trees

KW - Tree sources

KW - Universal coding

UR - http://www.scopus.com/inward/record.url?scp=2442449140&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2442449140&partnerID=8YFLogxK

U2 - 10.1109/TIT.2004.826664

DO - 10.1109/TIT.2004.826664

M3 - Letter

AN - SCOPUS:2442449140

VL - 50

SP - 928

EP - 937

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 5

ER -