Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition

DOI10.1007/978-3-642-20712-9_32zbMath1332.68301MaRDI 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

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

68W32: Algorithms on strings

Related Items

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

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