Efficient Algorithms For Normalized Edit Distance
Abdullah N. Arslan, Ömer Eğeci̇oğlu · 2000
ABSTRACT: A common model for computing the similarity of two stringsXandYof lengthsm andnrespectively, withmn, is to transformXintoYthrough a sequence of edit operations, called an edit sequence. The edit operations are of three types: insertion, deletion, and substitution. A given cost function assigns a weight to each edit operation. The amortized weight for a given edit sequence is the ratio of its weight to its length, and the minimum of this ratio over all edit sequences is the normalized edit distance. Existing algorithms for normalized edit distance computation with proven complexity bounds requireO(mn2)time in the worst-case. We give provably better algorithms: anO(mnlogn)-time algorithm when the cost function is uniform, i.e, the weights of edit operations depend only on the type but not on the individual symbols involved, and anO(mnlogm)-time algorithm when the weights are rational.