Approximate string matching on Ziv--Lempel compressed text

DOI10.1016/S1570-8667(03)00032-7MaRDI QIDQ1827277zbMATH OpenFDO

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

Publication date 6 August 2004

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

Full work available at URL https://doi.org/10.1016/S1570-8667(03)00032-7

zbMATH Keywords

Collage systemsCompressed pattern matchingDynamic programmingEdit distanceZiv--Lempel compression

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1615281
• Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts
• Beating \(O(nm)\) in approximate LZW-compressed pattern matching
• Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
• Practical and flexible pattern matching over Ziv-Lempel compressed text.

Cites work

• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• A Method for the Construction of Minimum-Redundancy Codes
• A universal algorithm for sequential data compression
• An Improved Algorithm For Approximate String Matching
• Applications of Path Compression on Balanced Trees
• Compression of individual sequences via variable-rate coding
• Faster approximate string matching
• Finding approximate patterns in strings
• scientific article; zbMATH DE number 1615279 (Why is no real title available?)
• scientific article; zbMATH DE number 1615280 (Why is no real title available?)
• scientific article; zbMATH DE number 1615281 (Why is no real title available?)
• scientific article; zbMATH DE number 2185628 (Why is no real title available?)
• scientific article; zbMATH DE number 2185629 (Why is no real title available?)
• scientific article; zbMATH DE number 1044854 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• Let sleeping files lie: Pattern matching in Z-compressed files.
• String matching in Lempel-Ziv compressed strings
• The theory and computation of evolutionary distances: Pattern recognition

Cited in

(20)

• Approximate matching of run-length compressed strings
• Approximate pattern matching in LZ77-compressed texts
• Binary jumbled string matching for highly run-length compressible texts
• scientific article; zbMATH DE number 1615281 (Why is no real title available?)
• Beating \(O(nm)\) in approximate LZW-compressed pattern matching
• Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts
• Compressed matching for feature vectors
• Towards approximate matching in compressed strings: local subsequence recognition
• Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
• Faster approximate pattern matching in compressed repetitive texts
• Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
• The structural border array
• scientific article; zbMATH DE number 1786446 (Why is no real title available?)
• scientific article; zbMATH DE number 1790365 (Why is no real title available?)
• Efficient algorithms for Lempel-Ziv encoding
• Engineering practical Lempel-Ziv tries
• Few matches or almost periodicity: faster pattern matching with mismatches in compressed texts
• Faster subsequence recognition in compressed strings
• Practical and flexible pattern matching over Ziv-Lempel compressed text.
• Compressed parameterized pattern matching

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

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