Edit distance of run-length encoded strings.
From MaRDI portal
Publication:1853090
DOI10.1016/S0020-0190(02)00215-6zbMath1043.68059MaRDI 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
68W40: Analysis of algorithms
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, Random Access to Grammar-Compressed Strings and Trees, Speeding up HMM decoding and training by exploiting sequence repetitions, Parallel comparison of run-length-encoded strings on a linear systolic array, 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, Unified compression-based acceleration of edit-distance computation, A fully compressed algorithm for computing the edit distance of run-length encoded strings, 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, Levenshtein graphs: resolvability, automorphisms \& determining sets, Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions, Sequence Alignment Algorithms for Run-Length-Encoded Strings, Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
Cites Work