Unified compression-based acceleration of edit-distance computation
From MaRDI portal
Publication:1939664
DOI10.1007/s00453-011-9590-6zbMath1259.68048arXiv1004.1194WikidataQ56813217 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
68W05: Nonnumerical algorithms
90C39: Dynamic programming
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Related Items
Unnamed Item, Hybridizing variable neighborhood search with ant colony optimization for solving the single row facility layout problem, Fast distance multiplication of unit-Monge matrices, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition
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