An algorithm for matching run-length coded strings |
| |
Authors: | Prof Dr H Bunke Prof Dr J Csirik |
| |
Affiliation: | 1. Institut für Informatik und angewandte Mathematik, Universit?t Bern, L?nggasstrasse 51, CH-3012, Bern, Switzerland 2. Department of Applied Computer Science, University of Szeged, Arpad ter 2, H-6720, Szeged, Hungary
|
| |
Abstract: | An algorithm for the computation of the edit distance of run-length coded strings is given. In run-length coding, not all individual symbols in a string are explicitly listed. Instead, one run of identical consecutive symbols is coded by giving one representative symbol together with its multiplicity. The algorithm determines the minimum cost sequence of edit operations transforming one string into another. In the worst case, the algorithm has a time complexity ofO(n·m), wheren andm give the lengths of the strings to be compared. In the best case, the time complexity isO(k·l), wherek andl are the numbers of runs of identical symbols in the two strings under comparison. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|