Computing the Cyclic Edit Distance for Pattern Classification by Ranking Edit Paths

摘要

The cyclic edit distance between two strings A and B of lengths m and n is the minimum edit distance between A and every cyclic shift of B. This can be applied, for instance, in classification tasks where strings represent the contour of objects. Bunke and Buehler proposed an algorithm that approximates the cyclic edit distance in time O(mn). In this paper we show how to apply a technique for ranking the K shortest paths to an edit graph underlying the Bunke and Biihler algorithm to obtain the exact solution. This technique, combined with pruning rules, leads to an efficient and exact procedure for nearest-neighbour classification based on cyclic edit distances. Experimental results show that the proposed method can be used to classify handwritten digits using the exact cyclic edit distance with only a small increase in computing time with respect to the original Bunke and Biihler algorithm.