Title | ||
---|---|---|
Strong link between BWT and XBW via Aho-Corasick automaton and applications to Run-Length Encoding. |
Abstract | ||
---|---|---|
The boom of genomic sequencing makes compression of set 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 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. |
Year | Venue | Field |
---|---|---|
2018 | arXiv: Data Structures and Algorithms | Data structure,Discrete mathematics,Bijection,Permutation,Automaton,Search engine indexing,Algorithm,Run-length encoding,Concatenation,Aho–Corasick string matching algorithm,Mathematics |
DocType | Volume | Citations |
Journal | abs/1805.10070 | 0 |
PageRank | References | Authors |
0.34 | 1 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bastien Cazaux | 1 | 10 | 6.65 |
E Rivals | 2 | 13 | 6.29 |