Approximate matching of run-length compressed strings

DOI10.1007/S00453-002-1005-2MaRDI QIDQ1402213zbMATH OpenOpenAlexWikidataFDO

Authors Veli Mäkinen, Esko Ukkonen, Gonzalo Navarro

Publication date 19 August 2003

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-002-1005-2

zbMATH Keywords

Levenshtein distanceCompressed pattern matchingLongest common subsequenceRun-length encodingWeighted edit distance

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• scientific article; zbMATH DE number 1786446
• Approximate string matching using compressed suffix arrays
• Combinatorial Pattern Matching
• Approximate string matching with compressed indexes
• Compressed Indexes for Approximate String Matching
• Compressed indexes for approximate string matching
• Approximate string matching on Ziv--Lempel compressed text
• scientific article; zbMATH DE number 1790365
• scientific article; zbMATH DE number 1615281
• Algorithms and Computation

Cited in

(18)

• An algorithm for matching run-length coded strings
• Identifying approximate palindromes in run-length encoded strings
• Hardness of comparing two run-length encoded strings
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Efficient retrieval of approximate palindromes in a run-length encoded string
• Levenshtein graphs: resolvability, automorphisms \& determining sets
• Linear-time text compression by longest-first substitution
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Edit distance for a run-length-encoded string and an uncompressed string
• Classification of run-length encoded binary data
• scientific article; zbMATH DE number 1786446 (Why is no real title available?)
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Approximate string matching with compressed indexes
• Computing similarity of run-length encoded strings with affine gap penalty
• Compressed matching for feature vectors
• Binary jumbled string matching for highly run-length compressible texts
• Dynamic RLE-compressed edit distance tables under general weighted cost functions

This page was built for publication: Approximate matching of run-length compressed strings

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