Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
From MaRDI portal
Publication:3654373
DOI10.1137/070685373zbMath1191.68225MaRDI 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
68W40: Analysis of algorithms
68P10: Searching and sorting
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P05: Data structures
Related Items
On compressing and indexing repetitive sequences, A grouping approach for succinct dynamic dictionary matching, Space-efficient construction of Lempel-Ziv compressed text indexes, Approximate string matching using compressed suffix arrays, Suffix-sorting via Shannon-Fano-Elias codes, Space-efficient construction of compressed suffix trees, Parallel computation of the Burrows Wheeler transform in compact space, Computing the Burrows-Wheeler transform in place and in small space, Space-time trade-offs for finding shortest unique substrings and maximal unique matches, Lightweight data indexing and compression in external memory, Fast BWT in small space by blockwise suffix sorting, Fully Functional Static and Dynamic Succinct Trees
