TY - CHAP

T1 - Burrows-Wheeler transform and Run-Length Enconding

AU - Mantaci, Sabrina

AU - Sciortino, Marinella

AU - Rosone, Giovanna

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Burrows-Wheeler transform

KW - Clustering effect

KW - Computer Science (all)

KW - Run-length encoding

KW - Theoretical Computer Science

KW - Burrows-Wheeler transform

KW - Clustering effect

KW - Computer Science (all)

KW - Run-length encoding

KW - Theoretical Computer Science

UR - http://hdl.handle.net/10447/259708

UR - https://link.springer.com/chapter/10.1007%2F978-3-319-66396-8_21

M3 - Chapter

SN - 9783319663951

T3 - LECTURE NOTES IN COMPUTER SCIENCE

SP - 228

EP - 239

BT - Combinatorics on Words, 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11–15, 2017, Proceedings

ER -