Dynamic time warping
# Dynamic time warping

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.

## Esempio di implementazione

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 |.

## Riferimenti Bibliografici

* 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
