Title :
Output distribution of the Burrows-Wheeler transform
Author :
Visweswariah, Karthik ; Kulkarni, Sanjeev ; Verdu, Sergio
Author_Institution :
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
Abstract :
The Burrows-Wheeler transform is a block-sorting algorithm which has been shown empirically to be useful in compressing text data. In this paper we study the output distribution of the transform for i.i.d. sources, tree sources and stationary ergodic sources. We can also give analytic bounds on the performance of some universal compression schemes which use the Burrows-Wheeler transform
Keywords :
Markov processes; source coding; transform coding; BWT; Burrows-Wheeler transform; block-sorting algorithm; i.i.d. sources; independent identically distributed sources; output distribution; performance; stationary ergodic sources; text data; tree sources; universal compression schemes; Data compression; Entropy; Markov processes; Performance analysis; Steady-state;
Conference_Titel :
Information Theory, 2000. Proceedings. IEEE International Symposium on
Conference_Location :
Sorrento
Print_ISBN :
0-7803-5857-0
DOI :
10.1109/ISIT.2000.866343
