### 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 language | English (US) |
---|---|

Pages (from-to) | 928-937 |

Number of pages | 10 |

Journal | IEEE Transactions on Information Theory |

Volume | 50 |

Issue number | 5 |

DOIs | |

State | Published - May 1 2004 |

### Fingerprint

### 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

*IEEE Transactions on Information Theory*,

*50*(5), 928-937. https://doi.org/10.1109/TIT.2004.826664

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

Research output: Contribution to journal › Letter

*IEEE Transactions on Information Theory*, vol. 50, no. 5, pp. 928-937. https://doi.org/10.1109/TIT.2004.826664

}

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 -