Burrows-Wheeler transform and Run-Length Enconding
- Autori: Mantaci, S.; Restivo, A.; Rosone, G.; Sciortino, M.
- Anno di pubblicazione: 2017
- Tipologia: Capitolo o Saggio (Capitolo o saggio)
- Parole Chiave: Burrows-Wheeler transform; Clustering effect; Run-length encoding; Theoretical Computer Science; Computer Science (all)
- OA Link: http://hdl.handle.net/10447/259708
Abstract
In this paper we study the clustering effect of the Burrows-Wheeler Transform (BWT) from a combinatorial viewpoint. In particular, given a word w we define the BWT-clustering ratio of w as the ratio between the number of clusters produced by BWT and the number of the clusters of w. The number of clusters of a word is measured by its Run-Length Encoding. We show that the BWT-clustering ratio ranges in ]0, 2]. Moreover, given a rational number r∈]0,2], it is possible to find infinitely many words having BWT-clustering ratio equal to r. Finally, we show how the words can be classified according to their BWT-clustering ratio. The behavior of such a parameter is studied for very well-known families of binary words.