Edit distance of run-length encoded strings
Let X and Y be two run-length encoded strings, of encoded lengths k and 1, respectively. We present a simple 0(\X\l + \Y\k) time algorithm that computes their edit distance. (C) 2002 Elsevier Science B.V. All rights reserved.
edit distance algorithms string matching dynamic programming run-length compression