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

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)

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

• 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?)
• 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
• 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)

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

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)