Advanced search


Ramón A. Mollineda, Enrique Vidal, Francisco Casacuberta. A Windowed Weighted Approach for Approximate Cyclic String Matching. Proceedings of the 16th International Conference on Pattern Recognition, 2002. Rangachar Kasturi, Denis Laurendeau, Ching Y. Suen (Editors). pp. 188-191. IAPR. IEEE Computer Society.

A method for measuring dissimilarities between cyclic strings is introduced. It computes a weighted mean between two (lower and upper) bounds of the exact cyclic edit distance, which are founded on a window-constrained edit graph related to the strings involved. Weights are the ones which minimize the sum of squared relative errors of the weighted solution with respect to exact values, on a training set of string pairs. This method takes O(n^2) time. Experiments on both artificial and real data, show the highly accurate solutions achieved by this technique, which is clearly faster than the most efficient exact algorithms.