Approximate string matching with compressed indexes
From MaRDI portal
Publication:1662494
DOI10.3390/a2031105zbMath1461.68271OpenAlexW2121806125WikidataQ58883988 ScholiaQ58883988MaRDI QIDQ1662494
Arlindo L. Oliveira, Luís M. S. Russo, Gonzalo Navarro, Pedro Morales-Almazan
Publication date: 20 August 2018
Published in: Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3390/a2031105
approximate string matchingcompressed indexcompressed suffix treeLempel-Ziv indexcompressed suffix array
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Approximation algorithms (68W25) Algorithms on strings (68W32)
Related Items
Approximate string matching using a bidirectional index, Approximate search of short patterns with high error rates using the \(01^\ast 0\) lossless seeds, Lossless Seeds for Searching Short Patterns with High Error Rates, On compressing permutations and adaptive sorting, Hybrid indexes for repetitive datasets, Summarized bit batch-based triangle listing in massive graphs, Efficient fully-compressed sequence representations, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Very fast and simple approximate string matching
- Indexing text using the Ziv--Lempel trie
- A sublinear algorithm for approximate keyword searching
- Linear bidirectional on-line construction of affix trees
- Compressed suffix trees with full functionality
- Indexing text with approximate \(q\)-grams
- Compressed representations of sequences and full-text indexes
- Suffix Arrays: A New Method for On-Line String Searches
- A fast bit-vector algorithm for approximate string matching based on dynamic programming
- An analysis of the Burrows—Wheeler transform
- Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
- An(other) Entropy-Bounded Compressed Suffix Tree
- Indexing compressed text
- Dictionary matching and indexing with errors and don't cares
- Finding approximate patterns in strings
- On the Complexity of Finite Sequences
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- Algorithms on Strings, Trees and Sequences
- Incremental String Comparison
- New text indexing functionalities of the compressed suffix arrays
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Dynamic entropy-compressed sequences and full-text indexes
- A Linear Size Index for Approximate Pattern Matching
- Reducing the Space Requirement of LZ-Index
- Combinatorial Pattern Matching
- Implementing the LZ-index
- Compressed text indexes
- Fully-Compressed Suffix Trees
- Average-optimal single and multiple approximate string matching
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Combinatorial Pattern Matching
- Algorithms and Computation
- Improving an algorithm for approximate pattern matching
