AN ALGORITHM FOR MATCHING RUN-LENGTH CODED STRINGS

An algorithm for the computation of the edit distance of run-length co ded strings is given. In run-length coding, not all individual symbols in a string are explicitly listed. Instead, one run of identical cons ecutive symbols is coded by giving one representative symbol together with its multiplicity. The algorithm determines the minimum cost seque nce of edit operations transforming one string into another. In the wo rst case, the algorithm has a time complexity of O(n . m), where n and m give the lengths of the strings to be compared. In the best case, t he time complexity is O(k . 1), where k and l are the numbers of runs of identical symbols in the two strings under comparison.