Smaller Fully-Functional Bidirectional BWT Indexes
| dc.contributor.author | Belazzougui,, Djamal | |
| dc.contributor.author | Cunial, Fabio | |
| dc.date.accessioned | 2023-10-16T09:28:26Z | |
| dc.date.available | 2023-10-16T09:28:26Z | |
| dc.date.issued | 2020-09-17 | |
| dc.description.abstract | Burrows-Wheeler indexes that support both extending and contracting any substring of the text $T$ of length $n$ on which they are built, in any direction, provide substantial flexibility in traversing the text and can be used to implement several algorithms. The practical appeal of such indexes is contingent on them being compact, and current designs that are sensitive to the compressibility of the input take either $O(e+\REV{e})$ words of space, where $e$ and $\REV{e}$ are the number of right and left extensions of the maximal repeats of $T$, or $O(r\log(n/r)+\REV{r}\log(n/\REV{r}))$ words, where $r$ and $\REV{r}$ are the number of runs in the Burrows-Wheeler transform of $T$ and of its reverse. In this paper we describe a fully-functional bidirectional index that takes $O(m+r+\REV{r})$ words, where $m$ is the number of maximal repeats of $T$, as well as a variant that takes $O(r+\REV{r})$ words. | |
| dc.identifier.isbn | 978-3-030-59211-0 | |
| dc.identifier.isbn | 978-3-030-59212-7 | |
| dc.identifier.uri | https://dl.cerist.dz/handle/CERIST/993 | |
| dc.publisher | Springer Nature | |
| dc.relation.ispartofseries | SPIRE 2020: 27th International Symposium on String Processing and Information Retrieval | |
| dc.relation.pages | 42-59 | |
| dc.relation.place | Orlando, FL, USA | |
| dc.structure | CAlcul Parallèle et Applications | |
| dc.subject | BWT | |
| dc.subject | Suffix tree | |
| dc.subject | Suffix-link tree | |
| dc.subject | BWT runs | |
| dc.subject | Maximal repeats | |
| dc.subject | Bidirectional index | |
| dc.title | Smaller Fully-Functional Bidirectional BWT Indexes | |
| dc.type | Conference paper |