Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding

Lien entre Transformée de Burrows-Wheeler (BWT) et BWT étendue (XBW) via l'automate d'Aho-Corasick : applications en compression par encodage des longueurs

Abstract

The boom of genomic sequencing makes compression of sets of sequences inescapable. This underlies the need for multi-string indexing data structures that helps compressing the data. The most prominent example of such data structures is the Burrows-Wheeler Transform (BWT), a reversible permutation of a text that improves its compressibility. A similar data structure, the eXtended Burrows-Wheeler Transform (XBW), is able to index a tree labelled with alphabet symbols. A link between a multi-string BWT and the Aho-Corasick automaton has already been found and led to a way to build a XBW from a multi-string BWT. We exhibit a stronger link between a multi-string BWT and a XBW by using the order of the concatenation in the multi-string. This bijective link has several applications: first, it allows one to build one data structure from the other; second, it enables one to compute an ordering of the input strings that optimises a Run-Length measure (i.e., the compressibility) of the BWT or of the XBW.
Fichier principal
Vignette du fichier
LIPIcs-CPM-2019-24.pdf (680.26 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-02382066 , version 1 (27-11-2019)

Licence

Attribution

Identifiers

Cite

Bastien Cazaux, Eric Rivals. Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding. CPM 2019 - 30th Annual Symposium on Combinatorial Pattern Matching, University of Pisa, Jun 2019, Pise, Italy. pp.24:1--24:20, ⟨10.4230/LIPIcs.CPM.2019.24⟩. ⟨lirmm-02382066⟩
138 View
114 Download

Altmetric

Share

Gmail Facebook X LinkedIn More