Optimizing the cost matrix for approximate string matching using genetic algorithms

摘要

This paper describes a method for optimizing the cost matrix of any approximate string matching algorithm based on the Levenshtein distance. The method, which uses genetic algorithms, defines the problem formally as a discrimination between a set of classes. It is tested and evaluated using both synthetically generated strings of symbols and chain code data extracted from the international Unipen database of on-line handwritten scripts. Experimental results show that this approach can effectively discover the hidden costs of elementary operations in a set of string classes. 1998 Pattern Recognition Society.