文章基本信息

标题：Fully-Functional Bidirectional Burrows-Wheeler Indexes and Infinite-Order De Bruijn Graphs
本地全文：下载
作者：Djamal Belazzougui ; Fabio Cunial
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：128
页码：1-15
DOI：10.4230/LIPIcs.CPM.2019.10
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given a string T on an alphabet of size sigma, we describe a bidirectional Burrows-Wheeler index that takes O( T log sigma) bits of space, and that supports the addition and removal of one character, on the left or right side of any substring of T, in constant time. Previously known data structures that used the same space allowed constant-time addition to any substring of T, but they could support removal only from specific substrings of T. We also describe an index that supports bidirectional addition and removal in O(log log T ) time, and that takes a number of words proportional to the number of left and right extensions of the maximal repeats of T. We use such fully-functional indexes to implement bidirectional, frequency-aware, variable-order de Bruijn graphs with no upper bound on their order, and supporting natural criteria for increasing and decreasing the order during traversal.
关键词：BWT; suffix tree; CDAWG; de Bruijn graph; maximal repeat; string depth; contraction; bidirectional index