A Normalized Levenshtein Distance Metric

摘要: Although a number of normalized edit distances presented so far may offer good performance in some applications, none them can be regarded as genuine metric between strings because they do not satisfy the triangle inequality. Given two X and Y over finite alphabet, this paper defines new distance simple function their lengths (|X| |Y|) Generalized Levenshtein Distance (GLD) them. The easily computed through GLD with complexity O(|X| \cdot it is valued [0, 1] under condition that weight set elementary operations all costs insertions/deletions having same weight. Experiments using AESA algorithm handwritten digit recognition show generally provide similar results to other perform slightly better if inequality violated particular data set.