Approximate matching of run-length compressed strings

DOI10.1007/s00453-002-1005-2zbMath1045.68059OpenAlexW2049170719WikidataQ58054198 ScholiaQ58054198MaRDI QIDQ1402213

Veli Mäkinen, Gonzalo Navarro, Esko Ukkonen

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)

Related Items

Compressed matching for feature vectors, Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions, Classification of run-length encoded binary data, Linear-time text compression by longest-first substitution, A fully compressed algorithm for computing the edit distance of run-length encoded strings, Sequence Alignment Algorithms for Run-Length-Encoded Strings, Levenshtein graphs: resolvability, automorphisms \& determining sets, Computing similarity of run-length encoded strings with affine gap penalty, Hardness of comparing two run-length encoded strings, Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard