STRING ALIGNMENT WITH SUBSTITUTION, INSERTION, DELETION, SQUASHING, AND EXPANSION OPERATIONS

Let X and Y be any two strings of finite length. The problem of transf orming X to Y using the edit operations of substitution, deletion, and insertion has been extensively studied in the literature. The problem can be solved in quadratic time if the edit operations are extended t o include the operation of transposition of adjacent characters, and i s NP-complete if the characters can be edited repeatedly. In this pape r we consider the problem of transforming X to Y when the set of edit operations is extended to include the squashing and expansion operatio ns. Whereas in the squashing operation two (or more) contiguous charac ters of X can be transformed into a single character of Y, in the expa nsion operation a single character in X may be expanded into two or mo re continuous characters of Y. These operations are typically found in the recognition of cursive script. A quadratic time solution to the p roblem has been presented. This solution is optimal for the infinite-a lphabet case. The strategy to compute the sequence of edit operations is also presented.