Approximate string matching on Ziv--Lempel compressed text

DOI10.1016/S1570-8667(03)00032-7zbMath1100.68127MaRDI QIDQ1827277

Juha Kärkkäinen, Esko Ukkonen, Gonzalo Navarro

Publication date: 6 August 2004

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

zbMATH Keywords

Dynamic programmingCompressed pattern matchingCollage systemsEdit distanceZiv--Lempel compression

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Dynamic programming (90C39) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (7)

Compressed matching for feature vectors ⋮ Faster subsequence recognition in compressed strings ⋮ Practical and flexible pattern matching over Ziv-Lempel compressed text. ⋮ The structural border array ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Compressed parameterized pattern matching ⋮ Approximate pattern matching in LZ77-compressed texts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Faster approximate string matching
• String matching in Lempel-Ziv compressed strings
• Applications of Path Compression on Balanced Trees
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• An Improved Algorithm For Approximate String Matching
• Finding approximate patterns in strings
• The theory and computation of evolutionary distances: Pattern recognition
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• A Method for the Construction of Minimum-Redundancy Codes

This page was built for publication: Approximate string matching on Ziv--Lempel compressed text