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

DOI10.1142/S0129054118410083zbMATH Open1397.68242OpenAlexW2811254326MaRDI QIDQ3177340FDOQ3177340

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)

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• 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)