Il Dynamic time warping, o DTW, è un algoritmo che permette l'allineamento tra due o più sequenze, e che può portare ad una misura di distanza tra le due sequenze allineate. Tale algoritmo è particolarmente utile per trattare sequenze in cui singole componenti hanno caratteristiche che variano nel tempo, e per le quali la semplice espansione o compressione lineare delle due sequenze non porta risultati soddisfacenti. È stato utilizzato in diversi campi di applicazione, dal Riconoscimento vocale, al riconoscimento di attività motorie.

In generale, DTW è un metodo che permette di trovare una corrispondenza ottima tra due sequenze, attraverso una distorsione non lineare rispetto alla variabile indipendente (tipicamente il tempo). Alcune restrizioni per il calcolo della corrispondenza sono generalmente utilizzate: deve essere garantita la monotonicità nelle corrispondenze, ed il limite massimo di possibili corrispondenze tra elementi contigui della sequenza.

Qui viene riportata una implementazione del calcolo di una misura di distanza basata su DTW, quando le due sequenze sono stringhe di simboli discreti. d(x, y) è la distanza tra i simboli, e.g. d(x, y) = | x - y |.

int DTWDistance(int s[1..n], int t[1..m]) {
    declare int DTW[0..n, 0..m]
    declare int i, j, cost

    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]
}

• Sakoe, H. and Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1) pp. 43– 49, 1978, ISSN 0096-3518

• Wikimedia Commons contiene immagini o altri file su Dynamic time warping

Portale Neuroscienze: accedi alle voci di Teknopedia che trattano di neuroscienze