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.
|Title of host publication||Combinatorics on Words, 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11–15, 2017, Proceedings|
|Number of pages||12|
|Publication status||Published - 2017|
|Name||LECTURE NOTES IN COMPUTER SCIENCE|
- Theoretical Computer Science
- General Computer Science