Editing Dynamic time warping (section)

== Implementation ==

This example illustrates the implementation of the dynamic time warping algorithm when the two sequences <var>s</var> and <var>t</var> are strings of discrete symbols. For two symbols <var>x</var> and <var>y</var>, <code>d(x, y)</code> is a distance between the symbols, e.g. <code>d(x, y)</code> = <math>| x - y |</math>.

 int DTWDistance(s: array [1..n], t: array [1..m]) {
     DTW := array [0..n, 0..m]
     
     for i := 0 to n
         for j := 0 to m
             DTW[i, j] := infinity
     DTW[0, 0] := 0
     
     for i := 1 to n
         for j := 1 to m
             cost := d(s[i], t[j])
             DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                         DTW[i  , j-1],    // deletion
                                         DTW[i-1, j-1])    // match
     
     return DTW[n, m]
 }

where <code>DTW[i, j]</code> is the distance between <code>s[1:i]</code> and <code>t[1:j]</code> with the best alignment.

We sometimes want to add a locality constraint. That is, we require that if <code>s[i]</code> is matched with <code>t[j]</code>, then <math>| i - j |</math> is no larger than <var>w</var>, a window parameter.

We can easily modify the above algorithm to add a locality constraint (differences <mark>marked</mark>).
However, the above given modification works only if <math>| n - m |</math> is no larger than <var>w</var>, i.e. the end point is within the window length from diagonal. In order to make the algorithm work, the window parameter <var>w</var> must be adapted so that <math>| n - m | \le w</math> (see the line marked with (*) in the code).

 int DTWDistance(s: array [1..n], t: array [1..m]<mark>, w: int</mark>) {
     DTW := array [0..n, 0..m]
 
     <mark>w := max(w, abs(n-m))</mark> // adapt window size (*)
 
     for i := 0 to n
         for j:= 0 to m
             DTW[i, j] := infinity
     DTW[0, 0] := 0
     <mark>for i := 1 to n</mark>
         <mark>for j := max(1, i-w) to min(m, i+w)</mark>
             <mark>DTW[i, j] := 0</mark>
 
     for i := 1 to n
         for j := <mark>max(1, i-w) to min(m, i+w)</mark>
             cost := d(s[i], t[j])
             DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                         DTW[i  , j-1],    // deletion
                                         DTW[i-1, j-1])    // match
     return DTW[n, m]
 }