Towards approximate matching in compressed strings: local subsequence recognition

DOI10.1007/978-3-642-20712-9_32MaRDI QIDQ3007644zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Faster subsequence recognition in compressed strings
• Random access to grammar-compressed strings
• Random access to grammar-compressed strings and trees
• Approximate string matching on Ziv--Lempel compressed text

Cites work

• A faster algorithm computing string edit distances
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• A unified algorithm for accelerating edit-distance computation via text-compression
• A universal algorithm for sequential data compression
• Approximately matching context-free languages
• Collage system: A unifying framework for compressed pattern matching.
• Compression of individual sequences via variable-rate coding
• Fast and compact regular expression matching
• Fast distance multiplication of unit-Monge matrices
• Faster subsequence recognition in compressed strings
• scientific article; zbMATH DE number 1490000 (Why is no real title available?)
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Processing Compressed Texts: A Tractability Border
• Querying and Embedding Compressed Texts
• Semi-local longest common subsequences in subquadratic time
• Semi-local string comparison: algorithmic techniques and applications
• The String-to-String Correction Problem
• Unified compression-based acceleration of edit-distance computation
• Window Subsequence Problems for Compressed Texts

Cited in

(5)

• Fast distance multiplication of unit-Monge matrices
• Substring compression problems
• Faster subsequence and don't-care pattern matching on compressed texts
• Fast algorithms for window accumulated subsequence matching problem
• Faster subsequence recognition in compressed strings

This page was built for publication: Towards approximate matching in compressed strings: local subsequence recognition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3007644)