Breaking a Time-and-Space Barrier in Constructing Full-Text Indices

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

zbMATH Keywords

suffix treessuffix arraystext indexingpreprocessing

Mathematics Subject Classification ID

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