Wheeler graphs: A framework for BWT-based data structures

The famous Burrows–Wheeler Transform (BWT) was originally defined for a single string but variations have been developed for sets of strings, labeled trees, de Bruijn graphs, etc. In this paper we propose a framework that includes many of these variations and that we hope will simplify the search fo...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2017-10, Vol.698, p.67-78
Main Authors: Gagie, Travis, Manzini, Giovanni, Sirén, Jouni
Format: Article
Language:English
Subjects:
Burrows–Wheeler transform
Compressed data structures
Pattern matching
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The famous Burrows–Wheeler Transform (BWT) was originally defined for a single string but variations have been developed for sets of strings, labeled trees, de Bruijn graphs, etc. In this paper we propose a framework that includes many of these variations and that we hope will simplify the search for more. We first define Wheeler graphs and show they have a property we call path coherence. We show that if the state diagram of a finite-state automaton is a Wheeler graph then, by its path coherence, we can order the nodes such that, for any string, the nodes reachable from the initial state or states by processing that string are consecutive. This means that even if the automaton is non-deterministic, we can still store it compactly and process strings with it quickly. We then rederive several variations of the BWT by designing straightforward finite-state automata for the relevant problems and showing that their state diagrams are Wheeler graphs.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2017.06.016