Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
From MaRDI portal
Publication:5470696
DOI10.1137/S0097539702402354zbMath1092.68115OpenAlexW2170899819MaRDI QIDQ5470696
Roberto Grossi, Jeffrey Scott Vitter
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539702402354
compressionpattern matchingsuffix treescompressed data structuresstring searchingsuffix arraystext indexingtext retrieval
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items
Extended suffix array construction using Lyndon factors, Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, Lyndon array construction during Burrows-Wheeler inversion, On position restricted substring searching in succinct space, The heaviest induced ancestors problem: better data structures and applications, Space-Efficient Frameworks for Top- k String Retrieval, Grammar compressed sequences with rank/select support, Approximate string matching with compressed indexes, Suffix-sorting via Shannon-Fano-Elias codes, Space-time trade-offs for finding shortest unique substrings and maximal unique matches, Kings, Name Days, Lazy Servants and Magic, Dictionary Matching with Uneven Gaps, Compressed property suffix trees, On compressing and indexing repetitive sequences, Faster repetition-aware compressed suffix trees based on block trees, Optimal in-place suffix sorting, An Opportunistic Text Indexing Structure Based on Run Length Encoding, On compressing permutations and adaptive sorting, Cross-document pattern matching, Reverse-Safe Text Indexing, String Indexing with Compressed Patterns, Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets, Encoding 2D range maximum queries, Ultra-succinct representation of ordered trees with applications, Finding range minima in the middle: approximations and applications, Stronger Lempel-Ziv based compressed text indexing, Time-Optimal Top-$k$ Document Retrieval, Unnamed Item, Compressed text indexing with wildcards, The longest common substring problem, Space-efficient algorithms for computing minimal/shortest unique substrings, Dictionary matching with a bounded gap in pattern or in text, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Wavelet trees for all, On the combinatorics of suffix arrays, Succinct data structures for flexible text retrieval systems, Space-efficient construction of compressed suffix trees, A linear size index for approximate pattern matching, Efficient fully-compressed sequence representations, Optimal indexes for sparse bit vectors, Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space, Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, Improved space-time tradeoffs for approximate full-text indexing with one edit error, Algorithms for Indexing Highly Similar DNA Sequences, Full-Text Indexes for High-Throughput Sequencing, Faster suffix sorting, Rank and select revisited and extended, Fast compressed self-indexes with deterministic linear-time construction, A grouping approach for succinct dynamic dictionary matching, A randomized numerical aligner (rNA), Combined data structure for previous- and next-smaller-values, A quick tour on suffix arrays and compressed suffix arrays, Space-efficient construction of Lempel-Ziv compressed text indexes, Boosting Pattern Matching Performance via k-bit Filtering, Lempel-Ziv compressed structures for document retrieval, Succinct data structures for searchable partial sums with optimal worst-case performance, Lempel-Ziv factorization powered by space efficient suffix trees, Dynamic rank/select structures with applications to run-length encoded texts, A brief history of parameterized matching problems, Read Mapping on Genome Variation Graphs, Locally Compressed Suffix Arrays, Fast Compressed Tries through Path Decompositions, General Document Retrieval in Compact Space, Top tree compression of tries, Faster entropy-bounded compressed suffix trees, THE VIRTUAL SUFFIX TREE, A compressed dynamic self-index for highly repetitive text collections, Orthogonal Range Searching for Text Indexing, Indexes for Document Retrieval with Relevance, Improved and extended locating functionality on compressed suffix arrays, Geometric BWT: compressed text indexing via sparse suffixes and range searching, Structural Pattern Matching - Succinctly., Fast Compressed Self-Indexes with Deterministic Linear-Time Construction, New compression schemes for natural number sequences, Compressing dictionary matching index via sparsification technique, The Heaviest Induced Ancestors Problem Revisited, Space-efficient substring occurrence estimation
