Notes on block-sorting data compression
Hidetoshi Yokoo · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1999
The block-sorting data compression method of Burrows and Wheeler has received considerable attention in anticipation that it may be comparable, or even superior, to the Ziv–Lempel codes. This article discusses its characteristic points from the viewpoint of string algorithms. The block-sorting compression algorithm initially sorts all rotations of an input text lexicographically. This transformation is still reversible when we restrict the key length of sorting. We first focus on the combinatorial aspect of this reversibility, then show that the block-sorting algorithm has the capability of finding repetitions in an original string. We give a new description of the algorithm in terms of the Karp–Miller–Rosenberg (KMR) repetition finder in order to combine the above two aspects. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(6): 18–25, 1999