A windowed weighted approach for approximate cyclic string matching

摘要

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²) 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.