ASYMPTOTIC OPTIMALITY OF THE BLOCK SORTING DATA-COMPRESSION ALGORITHM

Authors
ARIMURA M YAMAMOTO H
Citation
M. Arimura et H. Yamamoto, ASYMPTOTIC OPTIMALITY OF THE BLOCK SORTING DATA-COMPRESSION ALGORITHM, IEICE transactions on fundamentals of electronics, communications and computer science, E81A(10), 1998, pp. 2117-2122
Citations number
14
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E81A
Issue
10
Year of publication
1998
Pages
2117 - 2122
Database
ISI
SICI code
0916-8508(1998)E81A:10<2117:AOOTBS>2.0.ZU;2-V
Abstract
In this paper the performance of the Block Sorting algorithm proposed by Burrows and Wheeler is evaluated theoretically. It is proved that t he Block Sorting algorithm is asymptotically optimal for stationary er godic finite order Markov sources. Our proof is based on the facts tha t symbols with the same Markov state (or context) in an original data sequence are grouped together in the output sequence obtained by Burro ws-Wheeler transform, and the codeword length of each group can be bou nded by a function described with the frequencies of symbols included in the group.