Dynamic RLE-compressed edit distance tables under general weighted cost functions

DOI10.1142/S0129054118410083MaRDI QIDQ3177340zbMATH OpenOpenAlexFDO

Authors 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

edit distancestring comparisonrun-length encodingstring algorithm

Mathematics Subject Classification ID

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

Recommendations

• Compacting a dynamic edit distance table by RLE compression
• Dynamic edit distance table under a general weighted cost function
• A dynamic edit distance table
• scientific article; zbMATH DE number 1615270
• A fully compressed algorithm for computing the edit distance of run-length encoded strings

Cites work

• A dynamic edit distance table
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• An improved algorithm for computing the edit distance of run-length coded strings
• Approximate matching of run-length compressed strings
• Average-case optimal approximate circular string matching
• Compacting a dynamic edit distance table by RLE compression
• Computing the longest common subsequence of two run-length encoded strings
• Dynamic edit distance table under a general weighted cost function
• Edit distance of run-length encoded strings.
• FINDING ALL APPROXIMATE GAPPED PALINDROMES
• Incremental String Comparison
• Matching for run-length encoded strings
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• String comparison by transposition networks

Cited in

(4)

• Compacting a dynamic edit distance table by RLE compression
• Dynamic edit distance table under a general weighted cost function
• scientific article; zbMATH DE number 1615270 (Why is no real title available?)
• A dynamic edit distance table

This page was built for publication: Dynamic RLE-compressed edit distance tables under general weighted cost functions

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