Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition

DOI10.1007/978-3-642-20712-9_32zbMath1332.68301OpenAlexW125818881MaRDI QIDQ3007644

Alexander Tiskin

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_32

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Related Items

Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts, Compressed subsequence matching and packed tree coloring, Fast distance multiplication of unit-Monge matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximately matching context-free languages
• Faster subsequence recognition in compressed strings
• Semi-local string comparison: algorithmic techniques and applications
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Semi-local longest common subsequences in subquadratic time
• A faster algorithm computing string edit distances
• Collage system: A unifying framework for compressed pattern matching.
• Unified compression-based acceleration of edit-distance computation
• Fast and compact regular expression matching
• Window Subsequence Problems for Compressed Texts
• Processing Compressed Texts: A Tractability Border
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• The String-to-String Correction Problem
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Querying and Embedding Compressed Texts