Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space

DOI10.1145/3375890zbMath1491.68067arXiv1809.02792OpenAlexW2999295646WikidataQ126181515 ScholiaQ126181515MaRDI QIDQ5133958

Travis Gagie, Nicola Prezza, Gonzalo Navarro

Publication date: 11 November 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.02792

zbMATH Keywords

Burrows-Wheeler transformrepetitive string collectionscompressed text indexescompressed suffix trees

Mathematics Subject Classification ID

Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)

Related Items (24)

Novel results on the number of runs of the Burrows-Wheeler-transform ⋮ r-indexing the eBWT ⋮ An LMS-based grammar self-index with local consistency properties ⋮ Logarithmic equal-letter runs for BWT of purely morphic words ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Faster repetition-aware compressed suffix trees based on block trees ⋮ A new class of string transformations for compressed text indexing ⋮ Bit catastrophes for the Burrows-Wheeler transform ⋮ Efficient construction of the BWT for repetitive text using string compression ⋮ Algorithms and complexity on indexing founder graphs ⋮ Balancing run-length straight-line programs ⋮ Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads ⋮ Improved characters distance sampling for online and offline text searching ⋮ Computational graph pangenomics: a tutorial on data structures and their applications ⋮ Unnamed Item ⋮ Accessing the suffix array via \(\phi^{-1}\)-forest ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries ⋮ A combinatorial view on string attractors ⋮ Block trees ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Refining the \(r\)-index ⋮ Wheeler languages ⋮ Adaptive succinctness

This page was built for publication: Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space