Skip to main content Skip to main navigation


Learning the Costs of Edit Operations for Edit Distances

Achim Weigel; Stefan Agne
In: Michael Frydrych; Jussi Parkkinen; Ari Visa (Hrsg.). Proceedings of the 10th Scandinavian Conference on Image Analysis. Scandinavian Conference on Image Analysis (SCIA-97), June 9-11, Lappeenranta, Finland, Pages 493-500, Vol. 1, ISBN 951-764-145-1, Pattern Recognition Society of Finland, 6/1997.


The edit distance is a well known measure to define the similarity of strings. It is based on elementary edit operations: insertions, deletions, and substitutions. Costs are associated with all these edit operations. The distance between two strings is defined as the transformation from one string to the other using edit operations with minimal costs. In this work an iterative learning algorithm for the edit costs of the edit distance is presented. It converges to a solution, if the rough form of one solution is known. The algorithm is compared with several known methods for edit cost determination. Here, it shows its ability to improve the values determined by these approaches.