Numerical sequence matching based on local sum functions
The edit distance has found a broad spectrum of applications in word processing and bioinformatics. However, in a far greater range of applications, such as pattern recognition, image processing and signal processing it is of more practical interest to evaluate the distance between two sequences where each data element is numerical. In this paper within the dynamic programming framework, we develop an algorithm which can effectively and efficiently yield an indicator measuring the distance between two numerical sequences in the presence of severe noises such as data element swapping, data value splitting and merging, and various quantization schemes. Instead of trying to find the matching values in the two sequences, which are invalid any more, we formulate a local sum function (LSF) as the building unit of our distance measure. Due to its local nature, a dynamic programming procedure can be incurred to evaluate the distance between these two sequences. Experiments conducted on both synthetic and real world sequences suggest encouraging performances.
edit distance pattern recognition dynamic programming quantization schemes digital libraries