A fully compressed algorithm for computing the edit distance of run-length encoded strings

DOI10.1007/s00453-011-9592-4zbMath1259.68047OpenAlexW2897696602MaRDI QIDQ1939665

Kun-Mao Chao, Kuan-Yu Chen

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9592-4

zbMATH Keywords

edit distancerun lengthcompressed pattern matching

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 (4)

Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions ⋮ Fast exact dynamic time warping on run-length encoded time series ⋮ Unnamed Item ⋮ Almost linear time computation of maximal repetitions in run length encoded strings

Cites Work

• Unnamed Item
• Unnamed Item
• An improved algorithm for computing the edit distance of run-length coded strings
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Hardness of comparing two run-length encoded strings
• A faster algorithm computing string edit distances
• Matching for run-length encoded strings
• Inplace run-length 2d compressed search.
• Approximate matching of run-length compressed strings
• Edit distance of run-length encoded strings.
• Edit distance for a run-length-encoded string and an uncompressed string
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Finding approximate patterns in strings
• A linear space algorithm for computing maximal common subsequences
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• The String-to-String Correction Problem
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices

This page was built for publication: A fully compressed algorithm for computing the edit distance of run-length encoded strings