Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism

DOI10.1016/j.ipl.2004.02.011zbMath1177.68248OpenAlexW2127515417MaRDI QIDQ2390245

Valerio Freschi, Alessandro Bogliolo

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.02.011

zbMATH Keywords

parallel processingrun-length encodinglongest common subsequencestring comparison

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Related Items

R\'enyi entropy and pattern matching for run-length encoded sequences ⋮ Parallel comparison of run-length-encoded strings on a linear systolic array ⋮ Versatile string kernels ⋮ An Opportunistic Text Indexing Structure Based on Run Length Encoding ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ Efficient algorithms for the block edit problems ⋮ Finding a longest common subsequence between a run-length-encoded string and an uncompressed string ⋮ A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings ⋮ Unnamed Item ⋮ From Sequence Mining to Multidimensional Sequence Mining ⋮ A faster algorithm for the computation of string convolutions using LZ78 parsing

Cites Work

• Unnamed Item
• Unnamed Item
• An improved algorithm for computing the edit distance of run-length coded strings
• Matching for run-length encoded strings
• A fast and practical bit-vector algorithm for the longest common subsequence problem
• Edit distance of run-length encoded strings.
• A fast algorithm for computing longest common subsequences
• Compression of individual sequences via variable-rate coding
• Algorithms for the Longest Common Subsequence Problem
• Sparse dynamic programming I
• Sparse Dynamic Programming for Longest Common Subsequence from Fragments

This page was built for publication: Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism