Edit distance of run-length encoded strings.

DOI10.1016/S0020-0190(02)00215-6zbMath1043.68059OpenAlexW2026893402MaRDI QIDQ1853090

Gad M. Landau, Joseph S. B. Mitchell, Ora Arbell

Publication date: 21 January 2003

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00215-6

zbMATH Keywords

AlgorithmsDynamic programmingString matchingEdit distanceRun-length compression

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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 (14)

Speeding up HMM decoding and training by exploiting sequence repetitions ⋮ Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions ⋮ Edit distance for a run-length-encoded string and an uncompressed string ⋮ Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism ⋮ Parallel comparison of run-length-encoded strings on a linear systolic array ⋮ 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 ⋮ Levenshtein graphs: resolvability, automorphisms \& determining sets ⋮ Computing similarity of run-length encoded strings with affine gap penalty ⋮ A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings ⋮ Unnamed Item ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ Random Access to Grammar-Compressed Strings and Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved algorithm for computing the edit distance of run-length coded strings
• Matching for run-length encoded strings
• Finding approximate patterns in strings
• Algorithms for approximate string matching

This page was built for publication: Edit distance of run-length encoded strings.