Skip to main content
Passa alla visualizzazione normale.

SABRINA MANTACI

Burrows-Wheeler transform and Run-Length Enconding

  • Authors: Mantaci, S.; Restivo, A.; Rosone, G.; Sciortino, M.
  • Publication year: 2017
  • Type: Capitolo o Saggio (Capitolo o saggio)
  • Key words: Burrows-Wheeler transform; Clustering effect; Run-length encoding; Theoretical Computer Science; Computer Science (all)
  • OA Link: http://hdl.handle.net/10447/259708

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.