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

DOI10.1016/J.IPL.2007.07.006MaRDI QIDQ2380032zbMATH OpenOpenAlexWikidataFDO

Authors Jia-Jie Liu, Yue-Li Wang, Guan-Shieng Huang, R. C. T. 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

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

Recommendations

• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Edit distance of run-length encoded strings.
• An algorithm for matching run-length coded strings
• Approximate matching of run-length compressed strings

Cites work

• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Algorithms for approximate string matching
• Algorithms on Strings, Trees and Sequences
• An Improved Algorithm For Approximate String Matching
• An improved algorithm for computing the edit distance of run-length coded strings
• Approximate Boyer–Moore String Matching
• Data structures and algorithms for approximate string matching
• Edit distance of run-length encoded strings.
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)

Cited in

(14)

• Efficient merged longest common subsequence algorithms for similar sequences
• Edit distance of run-length encoded strings.
• Unified compression-based acceleration of edit-distance computation
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• RLE edit distance in near optimal time
• A unified algorithm for accelerating edit-distance computation via text-compression
• An algorithm for matching run-length coded strings
• Õptimal dynamic time warping on run-length encoded strings
• Approximating dynamic time warping distance between run-length encoded strings
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Hardness of comparing two run-length encoded strings

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

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