Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
From MaRDI portal
Publication:3654373
DOI10.1137/070685373zbMath1191.68225OpenAlexW2105633925MaRDI QIDQ3654373
Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung
Publication date: 6 January 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/1dbca248c14a3a604e71b885ce9cacd0666301b6
Analysis of algorithms (68W40) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (12)
Approximate string matching using compressed suffix arrays ⋮ Suffix-sorting via Shannon-Fano-Elias codes ⋮ Space-time trade-offs for finding shortest unique substrings and maximal unique matches ⋮ On compressing and indexing repetitive sequences ⋮ Lightweight data indexing and compression in external memory ⋮ Space-efficient construction of compressed suffix trees ⋮ Fast BWT in small space by blockwise suffix sorting ⋮ A grouping approach for succinct dynamic dictionary matching ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Parallel computation of the Burrows Wheeler transform in compact space ⋮ Computing the Burrows-Wheeler transform in place and in small space
This page was built for publication: Breaking a Time-and-Space Barrier in Constructing Full-Text Indices