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

DOI10.1145/335305.335351zbMATH Open1296.68035OpenAlexW2056707490MaRDI QIDQ3192007FDOQ3192007

Authors: 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

Recommendations

• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Space efficient suffix trees
• Combinatorial Pattern Matching
• A categorization theorem on suffix arrays with applications to space efficient text indexes
• New text indexing functionalities of the compressed suffix arrays

Mathematics Subject Classification ID

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

Cited In (96)

• Fast compressed self-indexes with deterministic linear-time construction
• Succinct representations of permutations and functions
• Compressed indexing with signature grammars
• Title not available (Why is that?)
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• Indexing text using the Ziv--Lempel trie
• Combinatorial Pattern Matching
• Replacing suffix trees with enhanced suffix arrays
• Title not available (Why is that?)
• String matching with alphabet sampling
• Space efficient suffix trees
• An index data structure for matrices, with applications to fast two-dimensional pattern matching
• A linear lower bound on index size for text retrieval
• Wheeler graphs: a framework for BWT-based data structures
• A linear lower bound on index size for text retrieval
• Counting suffix arrays and strings
• Title not available (Why is that?)
• Succincter text indexing with wildcards
• Self-indexing based on LZ77
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• An experimental study of a compressed index
• Online timestamped text indexing
• ESP-index: a compressed index based on edit-sensitive parsing
• Faster compressed dictionary matching
• Indexed multi-pattern matching
• Compressed property suffix trees
• Compressed indexes for text with wildcards
• On compressing and indexing repetitive sequences
• Ranked document retrieval with forbidden pattern
• Approximate string matching using compressed suffix arrays
• Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays
• Fast matching statistics in small space
• An index structure for spaced seed search
• Compressed indexes for approximate string matching
• Locally compressed suffix arrays
• Dynamic dictionary matching and compressed suffix trees
• Compressed data structures: Dictionaries and data-aware measures
• Time-space trade-offs for compressed suffix arrays.
• Forty Years of Text Indexing
• Ranked document retrieval for multiple patterns
• Title not available (Why is that?)
• Succinct non-overlapping indexing
• Internal pattern matching queries in a text and applications
• Grammar-compressed indexes with logarithmic search time
• Orthogonal range searching for text indexing
• Using static suffix array in dynamic application: case of text compression by longest first substitution
• On-line construction of compact directed acyclic word graphs
• On building minimal automaton for subset matching queries
• Compressed spaced suffix arrays
• Reducing space for index implementation.
• Constructing suffix arrays in linear time
• Succinct Non-overlapping Indexing
• Distribution-aware compressed full-text indexes
• Linear Time Suffix Array Construction Using D-Critical Substrings
• The compressed permuterm index
• Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure
• Indexing compressed text
• Geometric BWT: compressed text indexing via sparse suffixes and range searching
• Suffix trays and suffix trists: structures for faster text indexing
• The cell probe complexity of succinct data structures
• Wavelet trees for all
• Time-space trade-offs for Lempel-Ziv compressed indexing
• A Compressed Enhanced Suffix Array Supporting Fast String Matching
• New text indexing functionalities of the compressed suffix arrays
• Improved approximate string matching using compressed suffix data structures
• Title not available (Why is that?)
• Hybrid indexing revisited
• Text indexing with errors
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Opportunistic data structures for range queries
• Compressed data structures for strings. On searching and extracting strings from compressed textual data
• Suffix Arrays: A New Method for On-Line String Searches
• A categorization theorem on suffix arrays with applications to space efficient text indexes
• A self-index on block trees
• Using compressed suffix-arrays for a compact representation of temporal-graphs
• Byte-aligned pattern matching in encoded genomic sequences
• Suffix arrays for multiple strings: a method for on-line multiple string searches
• On the Structure of Consistent Partitions of Substring Set of a Word
• A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
• Sliding suffix tree
• Semi-dynamic compact index for short patterns and succinct van Emde Boas tree
• Succinct backward-DAWG-matching
• Title not available (Why is that?)
• Improved and extended locating functionality on compressed suffix arrays
• Accessing the suffix array via \(\phi^{-1}\)-forest
• Algorithms for indexing highly similar DNA sequences
• Algorithms and Computation
• Reverse-safe text indexing
• String Processing and Information Retrieval
• An artificial neural network based approach for online string matching/filtering of large databases
• Improved characters distance sampling for online and offline text searching
• Optimized binary search and text retrieval
• Tables

This page was built for publication: Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192007)