Skip navigation

Dynamic Time Warping

Előismeret

A Dynamic Time Warping algoritmus egy távolságot határoz meg két vektor között. Alapvetően itt is feltételezhetjük, hogy a vektorok elemszáma megegyezik, azonban ez nem törvényszerű ezen algoritmusok esetében. Tehát ezzel a módszerrel olyan vektorok távolsága is meghatározható, amelyek komponens-száma különbözik.

A Dynamic Time Warping algoritmus pszeudokódja az alábbi módon adható meg [forrás:Wikipedia]:

int DTWDistance(s: array [1..n], t: array [1..m]) {
   DTW := array [0..n, 0..m]
 
   for i := 1 to n
     for j := 1 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]
}