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

DOI10.1016/0020-0190(95)00005-WMaRDI QIDQ673470zbMATH OpenOpenAlexFDO

Authors Horst Bunke, János 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)

Cites work

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

Cited in

(17)

• Fast algorithms for computing the constrained LCS of run-length encoded strings
• scientific article; zbMATH DE number 7561710 (Why is no real title available?)
• Edit distance of run-length encoded strings.
• Parallel comparison of run-length-encoded strings on a linear systolic array
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Edit distance for a run-length-encoded string and an uncompressed string
• Matching for run-length encoded strings
• Random access to grammar-compressed strings and trees
• Speeding up HMM decoding and training by exploiting sequence repetitions
• Dynamic RLE-compressed edit distance tables under general weighted cost functions
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Unified compression-based acceleration of edit-distance computation
• Computing similarity of run-length encoded strings with affine gap penalty
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Faster STR-EC-LCS computation

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

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