Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions

DOI10.1142/S0129054118410083zbMath1397.68242OpenAlexW2811254326MaRDI QIDQ3177340

Heikki Hyyrö, Shunsuke Inenaga

Publication date: 24 July 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054118410083

zbMATH Keywords

run-length encodingedit distancestring comparisonstring algorithm

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Dynamic edit distance table under a general weighted cost function
• An improved algorithm for computing the edit distance of run-length coded strings
• A dynamic edit distance table
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Matching for run-length encoded strings
• Approximate matching of run-length compressed strings
• Edit distance of run-length encoded strings.
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Compacting a Dynamic Edit Distance Table by RLE Compression
• Average-Case Optimal Approximate Circular String Matching
• FINDING ALL APPROXIMATE GAPPED PALINDROMES
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Incremental String Comparison
• Computing the Longest Common Subsequence of Two Run-Length Encoded Strings

This page was built for publication: Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions