Bj. Oommen, STRING ALIGNMENT WITH SUBSTITUTION, INSERTION, DELETION, SQUASHING, AND EXPANSION OPERATIONS, Information sciences, 83(1-2), 1995, pp. 89-107
Citations number
28
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
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.