The Asymptotical Optimality of the Block Sorting Data Compression Algorithm
Mitsuharu ARIMURA and Hirosuke YAMAMOTO
- In this paper the performance of the Block Sorting algorithm proposed by Burrows and Wheeler is evaluated theoretically. It ia proved that the Block Sorting algorithm is asymptotically optimal for stationary ergodic finite order Markov sources. Our proof are based on the facts that symbols with the same Markov state (or context) in an original data sequence are grouped together in the output sequence obtained by Burrows-Wheeler transform, and the codeword length of each group can be bounded by a function described with the frequencies of symbols included in the group.
- Key words: Lossless Data Compression, Block Sorting Algorithm, Stationary Ergodic Markov Source, Asymptotical Optimality
- PDF(448 Kbytes) Copyright(c)1998 IEICE