Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

DOI10.1145/335305.335351zbMath1296.68035OpenAlexW2056707490MaRDI QIDQ3192007

Roberto Grossi, Jeffrey Scott Vitter

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335351

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items

Approximate string matching using compressed suffix arrays ⋮ The cell probe complexity of succinct data structures ⋮ On the Structure of Consistent Partitions of Substring Set of a Word ⋮ Replacing suffix trees with enhanced suffix arrays ⋮ Indexing text using the Ziv--Lempel trie ⋮ Wheeler graphs: a framework for BWT-based data structures ⋮ Ranked Document Retrieval with Forbidden Pattern ⋮ Succinct Non-overlapping Indexing ⋮ Compressed indexes for text with wildcards ⋮ On compressing and indexing repetitive sequences ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Using compressed suffix-arrays for a compact representation of temporal-graphs ⋮ Succinct representations of permutations and functions ⋮ Wavelet trees for all ⋮ Text indexing with errors ⋮ A framework for designing space-efficient dictionaries for parameterized and order-preserving matching ⋮ Improved approximate string matching using compressed suffix data structures ⋮ Counting suffix arrays and strings ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ Compressed data structures: Dictionaries and data-aware measures ⋮ Succincter Text Indexing with Wildcards ⋮ Self-indexing Based on LZ77 ⋮ An artificial neural network based approach for online string matching/filtering of large databases ⋮ On-line construction of compact directed acyclic word graphs ⋮ Forty Years of Text Indexing ⋮ An experimental study of a compressed index ⋮ Distribution-aware compressed full-text indexes ⋮ Opportunistic data structures for range queries ⋮ Ranked document retrieval for multiple patterns ⋮ Succinct non-overlapping indexing ⋮ Compressed indexes for approximate string matching ⋮ Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays ⋮ Unnamed Item ⋮ Linear Time Suffix Array Construction Using D-Critical Substrings ⋮ Locally Compressed Suffix Arrays ⋮ Constructing suffix arrays in linear time ⋮ Time-space trade-offs for compressed suffix arrays. ⋮ Improved and extended locating functionality on compressed suffix arrays