Compressed indexes for approximate string matching
DOI10.1007/S00453-008-9263-2zbMATH Open1205.68523OpenAlexW2176433769MaRDI QIDQ5961970FDOQ5961970
Ho-Leung Chan, Tak-Wah Lam, Siu-Lung Tam, Wing-Kin Sung, Swee-Seong Wong
Publication date: 16 September 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10722/92634
Recommendations
Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Cites Work
- Succinct representation of balanced parentheses and static trees
- Dictionary matching and indexing with errors and don't cares
- Title not available (Why is that?)
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Title not available (Why is that?)
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Suffix Arrays: A New Method for On-Line String Searches
- A Space-Economical Suffix Tree Construction Algorithm
- Title not available (Why is that?)
- Fast Algorithms for Finding Nearest Common Ancestors
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Title not available (Why is that?)
- Combinatorial Pattern Matching
- Improved approximate string matching using compressed suffix data structures
- Title not available (Why is that?)
- A Linear Size Index for Approximate Pattern Matching
- Combinatorial Pattern Matching
- Title not available (Why is that?)
- Algorithms and Data Structures
Cited In (21)
- Combinatorial Pattern Matching
- Simple, compact and robust approximate string dictionary
- Improved space-time tradeoffs for approximate full-text indexing with one edit error
- Cache-oblivious index for approximate string matching
- An approximation algorithm for alphabet indexing problem
- Compressing dictionary matching index via sparsification technique
- Combinatorial Pattern Matching
- FM-index of alignment: a compressed index for similar strings
- Less space: indexing for queries with wildcards
- Cache-Oblivious Index for Approximate String Matching
- Approximate matching of run-length compressed strings
- Index structures for fast similarity search for binary vectors
- Approximate string matching with compressed indexes
- Index structures for fast similarity search for symbol strings
- Compressed Text Indexes with Fast Locate
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast String Dictionary Lookup with One Error
- Compressed data structures for strings. On searching and extracting strings from compressed textual data
- Title not available (Why is that?)
- Pattern masking for dictionary matching: theory and practice
This page was built for publication: Compressed indexes for approximate string matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961970)
