Burrows-Wheeler transform and Run-Length Enconding

Research output: Chapter in Book/Report/Conference proceedingChapter

7 Citations (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.
Original languageEnglish
Title of host publicationCombinatorics on Words, 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11–15, 2017, Proceedings
Pages228-239
Number of pages12
Publication statusPublished - 2017

Publication series

NameLECTURE NOTES IN COMPUTER SCIENCE

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Burrows-Wheeler transform and Run-Length Enconding'. Together they form a unique fingerprint.

Cite this