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