Burrows-Wheeler transform and Run-Length Enconding

Risultato della ricerca: Chapter

7 Citazioni (Scopus)


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.
Lingua originaleEnglish
Titolo della pubblicazione ospiteCombinatorics on Words, 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11–15, 2017, Proceedings
Numero di pagine12
Stato di pubblicazionePublished - 2017

Serie di pubblicazioni


All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???


Entra nei temi di ricerca di 'Burrows-Wheeler transform and Run-Length Enconding'. Insieme formano una fingerprint unica.

Cita questo