| 主权项 |
1. A computer-implemented method of determining matching subsequences between a first sequence of values and a second sequence of values, said method comprising:
inputting said first and second sequences of values into an alignment algorithm, said alignment algorithm defining a plane of points corresponding to said sequences of values, said alignment algorithm identifying similar points on said plane according to a predefined similarity metric, and said alignment algorithm grouping a plurality of said similar points between said two sequence values so as to define a path according to said alignment algorithm, and outputting a series of optimized matching subsequences according to predetermined path characteristic metrics, wherein said alignment algorithm uses a one-dimensional vector structure of paths, and said paths have a non-linear alignment between said matching subsequences,
where the first sequence of values is a first time series Q={q1; q2; ; qM} and the second sequence of values is a second time series R={r1; r2; . . . ; rN} of real valued n-dimensional vectors, where n is a design parameter, where said one-dimensional vector structure of paths is called ΔT and is set as void as start up and where said alignment algorithm includes the following steps; a) For every vector, qi, belonging to Q do: b1) Select the vectors in R which are considered most similar to qi according to the predefined similarity metric b2) For every vector rj belonging to the group selected in the previous step do: b21) Set a variable k=trj−tqi, where tqi and trj are the offsets of vector qi and rj from the start of their respective sequences; b22) Set a variable best_path=(qi, rj); b23) For k′=k−Wrange to k+WRange, where Wrange is a design parameter do: b231) Set a variable p=ΔT(k′); b232) Determine if the offset between vector pair (qi, rj) and p is less than a predefined first threshold, and if so, b233) Determine if the vector pair (qi, rj) meets a predefined set of warping constraints with respect to p and if so, b234) Select the best path according to a first path characteristic metric, between the path composed by adding the vector pair (qi, rj) to p and the path stored in best_path and set the variable best_path as the path selected; b235) Go to step b231) for the next value of k′;
b24) ΔT(k)=best_path;b25) Go to step b21) for the next value of rj;b3) Go to step b2) for the next value of qi. |
