An improved algorithm for computing the edit distance of run-length coded strings

DOI10.1016/0020-0190(95)00005-WzbMath1004.68598OpenAlexW2049231620MaRDI QIDQ673470

Horst Bunke, János A. Csirik

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00005-w

zbMATH Keywords

algorithmsapproximate string matchingstring edit distance

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items

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 ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ Computing similarity of run-length encoded strings with affine gap penalty ⋮ Faster STR-EC-LCS Computation ⋮ 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 ⋮ Matching for run-length encoded strings ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Edit distance of run-length encoded strings.

Cites Work

• An algorithm for matching run-length coded strings
• Data structures and algorithms for approximate string matching
• A faster algorithm computing string edit distances
• An Improved Algorithm For Approximate String Matching
• Algorithms for approximate string matching
• Approximate Boyer–Moore String Matching
• A linear space algorithm for computing maximal common subsequences
• The String-to-String Correction Problem
• On the Set LCS and Set-Set LCS Problems

This page was built for publication: An improved algorithm for computing the edit distance of run-length coded strings