Parametric string edit distance and its application to pattern recognition

摘要

A generalized version of the string matching algorithm by Wagner and Fischer (1974) is proposed. It is based on a parametrization of the edit cost. We assume constant cost for any delete and insert operation, but the cost for replacing a symbol is given as a parameter /spl tau/. For any two strings A and B, our algorithm computes their edit distance in terms of the parameter /spl tau/. We give the new algorithm, study some of its properties, and discuss potential applications to pattern recognition.