CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe show how to build several data structures of central importance to string processing by taking as input the Burrows-Wheeler transform (BWT) and using small extra working space. Let $n$ be the text length and $sigma$ be the alphabet size. We first provide two algorithms that enumerate all LCP values and suffix tree intervals in $O(nlogsigma)$ time using just $o(nlogsigma)$ bits of working space on top of the input re-writable BWT. Using these algorithms as building blocks, for any parameter $0 < epsilon leq 1$ we show how to build the PLCP bitvector and the balanced parentheses representation of the suffix tree topology in $Oleft(n(logsigma + epsilon^{-1}cdot loglog n) ight)$ time using at most $nlogsigma cdot(epsilon + o(1))$ bits of working space on top of the input re-writable BWT and the output. For example, we can build a compressed suffix tree from the BWT using just succinct working space (i.e. $o(nlogsigma)$ bits) and $Thetaleft(nlogsigma + n(loglog n)^{1+delta} ight)$ time, for any constant $delta>0$. This improves the previous most space-efficient algorithms, which worked in $O(n)$ bits and $O(nlog n)$ time. We also consider the problem of merging BWTs of string collections, and provide a solution running in $O(nlogsigma)$ time and using just $o(nlogsigma)$ bits of working space. An efficient implementation of our LCP construction and BWT merge algorithms uses (in RAM) as few as $n$ bits on top of a packed representation of the input/output and process data as fast as $2.92$ megabases per second.
| Autori interni: | ROSONE, GIOVANNA (Corresponding) |
| Autori: | Prezza, Nicola; Rosone, Giovanna |
| Titolo: | Space-efficient construction of compressed suffix trees |
| Anno del prodotto: | 2021 |
| Digital Object Identifier (DOI): | 10.1016/j.tcs.2020.11.024 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| PR_TCS2021.pdf | Articolo | Documento in Post-print |  | Embargo: 08/01/2023 Richiedi una copia |
http://hdl.handle.net/11568/1062324
Copyright © 2021