Edit distance for a run-length-encoded string and an uncompressed string

DOI10.1016/j.ipl.2007.07.006zbMath1184.68606OpenAlexW2007540612WikidataQ126220278 ScholiaQ126220278MaRDI QIDQ2380032

Jia-Jie Liu, Yue-Li Wang, Guan-Shieng Huang, Richard Chia-Tung Lee

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.07.006

zbMATH Keywords

algorithmsedit distancerun-length-encodingstring compression

Mathematics Subject Classification ID

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

Related Items

Efficient merged longest common subsequence algorithms for similar sequences ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Sequence Alignment Algorithms for Run-Length-Encoded Strings ⋮ A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings ⋮ Unnamed Item ⋮ Hardness of comparing two run-length encoded strings ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

Cites Work

• Unnamed Item
• An improved algorithm for computing the edit distance of run-length coded strings
• Data structures and algorithms for approximate string matching
• Edit distance of run-length encoded strings.
• An Improved Algorithm For Approximate String Matching
• Algorithms for approximate string matching
• Approximate Boyer–Moore String Matching
• Algorithms on Strings, Trees and Sequences
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices

This page was built for publication: Edit distance for a run-length-encoded string and an uncompressed string