Compressed indexes for approximate string matching

DOI10.1007/S00453-008-9263-2MaRDI QIDQ5961970zbMATH OpenOpenAlexFDO

Authors Ho-Leung Chan, Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tam, 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

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

Recommendations

• Compressed Indexes for Approximate String Matching
• A Linear Size Index for Approximate Pattern Matching
• A linear size index for approximate pattern matching
• scientific article; zbMATH DE number 2185640
• Approximate string matching using compressed suffix arrays

Cites work

• A Linear Size Index for Approximate Pattern Matching
• A Space-Economical Suffix Tree Construction Algorithm
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Dictionary matching and indexing with errors and don't cares
• Dynamic text and static pattern matching.
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 1670652 (Why is no real title available?)
• scientific article; zbMATH DE number 2185612 (Why is no real title available?)
• scientific article; zbMATH DE number 2086228 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 2119665 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• Improved approximate string matching using compressed suffix data structures
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Succinct representation of balanced parentheses and static trees
• Suffix Arrays: A New Method for On-Line String Searches

Cited in

(28)

• Approximate matching of run-length compressed strings
• Approximate string matching with compressed indexes
• Index structures for fast similarity search for symbol strings
• Compressing dictionary matching index via sparsification technique
• Fast string dictionary lookup with one error
• FM-index of alignment: a compressed index for similar strings
• Less space: indexing for queries with wildcards
• scientific article; zbMATH DE number 2185640 (Why is no real title available?)
• Cache-Oblivious Index for Approximate String Matching
• Compressed Text Indexes with Fast Locate
• Compressed data structures for strings. On searching and extracting strings from compressed textual data
• Simple, compact and robust approximate string dictionary
• scientific article; zbMATH DE number 1786446 (Why is no real title available?)
• Improved space-time tradeoffs for approximate full-text indexing with one edit error
• Fast entropy-bounded string dictionary look-up with mismatches
• Combinatorial Pattern Matching
• Compressed Indexes for Approximate String Matching
• Developments in Language Theory
• Cache-oblivious index for approximate string matching
• Combinatorial Pattern Matching
• Algorithms and Computation
• Fast index for approximate string matching
• An approximation algorithm for alphabet indexing problem
• Pattern masking for dictionary matching: theory and practice
• A linear size index for approximate pattern matching
• Index structures for fast similarity search for binary vectors
• Approximate string matching using compressed suffix arrays
• Improved approximate string matching using compressed suffix data structures

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)