We describe and highlight a generalization of the Burrows–Wheeler Transform (bwt) to a multiset of words. The extended transformation, denoted by ebwt, is reversible. Moreover, it allows to define a bijection between the words over a finite alphabet A and the finite multisets of conjugacy classes of primitive words in A∗. Besides its mathematical interest, the extended transform can be useful for applications in the context of string processing. In the last part of this paper we illustrate one such application, providing a similarity measure between sequences based on ebwt.

MANTACI, S., ROSONE, G., RESTIVO, A., SCIORTINO, M. (2007). An extension of the Burrows-Wheeler Transform. THEORETICAL COMPUTER SCIENCE, 387 (3), 298-312 [10.1016/j.tcs.2007.07.014].

An extension of the Burrows-Wheeler Transform

MANTACI, Sabrina;ROSONE, Giovanna;RESTIVO, Antonio;SCIORTINO, Marinella
2007-01-01

Abstract

We describe and highlight a generalization of the Burrows–Wheeler Transform (bwt) to a multiset of words. The extended transformation, denoted by ebwt, is reversible. Moreover, it allows to define a bijection between the words over a finite alphabet A and the finite multisets of conjugacy classes of primitive words in A∗. Besides its mathematical interest, the extended transform can be useful for applications in the context of string processing. In the last part of this paper we illustrate one such application, providing a similarity measure between sequences based on ebwt.
2007
MANTACI, S., ROSONE, G., RESTIVO, A., SCIORTINO, M. (2007). An extension of the Burrows-Wheeler Transform. THEORETICAL COMPUTER SCIENCE, 387 (3), 298-312 [10.1016/j.tcs.2007.07.014].
File in questo prodotto:
File Dimensione Formato  
MRRS_TCS_2007.pdf

Solo gestori archvio

Dimensione 445.43 kB
Formato Adobe PDF
445.43 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/26745
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 99
  • ???jsp.display-item.citation.isi??? 64
social impact