Burrows-Wheeler transform and Run-Length Enconding

Risultato della ricerca: Chapter

6 Citazioni (Scopus)

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

Serie di pubblicazioni

NomeLECTURE NOTES IN COMPUTER SCIENCE

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • ???subjectarea.asjc.1700.1700???

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

Cita questo