Normalizing the weighted edit distance

In this paper, we discuss the weighted edit distance and two well known normalizations, one based on editing path lengths and one based on the string lengths. We investigate the limitations of these approaches as well as the restrictions on the associated weight function including the triangular inequality. As a solution to the problems pointed out, we present a modified normalized edit distance. The new approach expresses the edit distance between two strings X and Y in a more adequate and intuitive way, reflecting the human decision process during comparisons. A further advantage is that this new distance measure is efficiently computable in O(|X|×|Y|) instead of O(|X|×|Y|×min (|X|,|Y|)) for the other normalizations