Practical Einear Space Algorithms for Computing String-Edit Distances

摘要

String-edit operations consist of insertion of a symbol, deletion of a symbol, and substituting one symbol with another. String-edit distances have been applied in problems of error correction and pattern recognition. In this paper, two practical algorithms for computing the edit distance between two strings are presented. The space complexity for the first is m + n + O(1), where m and n are the lengths of the input strings. The second requires only min(m, n) + O(1).