Compressed indexes for approximate string matching

DOI10.1007/s00453-008-9263-2zbMath1205.68523OpenAlexW2176433769MaRDI QIDQ5961970

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

zbMATH Keywords

approximate string matchingcompressed index

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (7)

Less space: indexing for queries with wildcards ⋮ Fast String Dictionary Lookup with One Error ⋮ Unnamed Item ⋮ Improved space-time tradeoffs for approximate full-text indexing with one edit error ⋮ Index structures for fast similarity search for binary vectors ⋮ Cache-oblivious index for approximate string matching ⋮ Index structures for fast similarity search for symbol strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximate string matching using compressed suffix data structures
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Succinct Representation of Balanced Parentheses and Static Trees
• Suffix Arrays: A New Method for On-Line String Searches
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Fast Algorithms for Finding Nearest Common Ancestors
• Dictionary matching and indexing with errors and don't cares
• A Space-Economical Suffix Tree Construction Algorithm
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• A Linear Size Index for Approximate Pattern Matching
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Algorithms and Data Structures

This page was built for publication: Compressed indexes for approximate string matching