Unified compression-based acceleration of edit-distance computation

DOI10.1007/s00453-011-9590-6zbMath1259.68048arXiv1004.1194OpenAlexW1679675208WikidataQ56813217 ScholiaQ56813217MaRDI QIDQ1939664

Shir Landau, Gad M. Landau, Danny Hermelin, Oren Weimann

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.1194

zbMATH Keywords

data compressioncombinatorial pattern matchingedit-distancestraight-line-programming

Mathematics Subject Classification ID

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

Hybridizing variable neighborhood search with ant colony optimization for solving the single row facility layout problem, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, Unnamed Item, Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition, Fast distance multiplication of unit-Monge matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved algorithm for computing the edit distance of run-length coded strings
• Faster subsequence recognition in compressed strings
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Geometric applications of a matrix-searching algorithm
• A faster algorithm computing string edit distances
• Matching for run-length encoded strings
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Edit distance of run-length encoded strings.
• Collage system: A unifying framework for compressed pattern matching.
• Window Subsequence Problems for Compressed Texts
• Efficient Parallel Algorithms for String Editing and Related Problems
• Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
• Processing Compressed Texts: A Tractability Border
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Algorithms on Strings, Trees and Sequences
• The String-to-String Correction Problem
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Querying and Embedding Compressed Texts