Algorithms for string editing which permit arbitrarily complex edit constraints
Let X and Y be any two strings of finite length. We consider the problem of transforming X to Y using the edit operations of deletion, insertion and substitution. The optimal transformation is the one which has the minimum edit distance associated with it. The problem of computing this distance and the optimal transformation using no edit constraints has been studied in the literature. In this paper we consider the problem of transform X to Y using any arbitrary edit constraints involving the number and type of edit operations to be performed. An algorithm has been presented to compute the minimum distance associated with editing X to Y subject to the specified constraint. The algorithm requires 0 (|X| . |y|. min(|x| , |y|)) time and space. The technique to compute the optimal-transformation has also been presented.