Efficient algorithms for the block edit problems

In this paper, we focus on the edit distance between two given strings where block-edit operations are allowed and better fitting to the human natural edit behaviors. Previous results showed that this problem is NP-hard when block moves are allowed. Various approximations to this problem have been proposed in recent years. However, this problem can be solved by the polynomial-time optimization algorithms if some reasonable restrictions are applied. The restricted variations which we consider involve character insertions, character deletions, block copies and block deletions. In this paper, three problems are defined with different measuring functions, which are P ( EIS, C ), P ( EI, L ) and P ( EI, N ). Then we show that with some preprocessing, the minimum block edit distances of these three problems can be obtained by dynamic programming in O ( nm ), O ( nm log m ) and O ( nm 2 ) time, respectively, where n and m are the lengths of the two input strings.

Authors

• Hsing-Yen Ann
• Chang-Biau Yang
• Yung-Hsing Peng
• Bern-Cherng Liaw

Keywords

• Design of algorithms
• String edit distance
• Block-edit
• Similarity
• Dynamic programming