Dynamic Time Warping

Given two sequences of data, there are many ways to establish a metric to calculate their mutual distance.
Dynamic time warping is a fascinating algorithm invented by Sakoe and Chiba.
Basically, it's looking at the underlying data and seeing how much one sequence needs to change in order to be like the other sequence.
However, it searches for time differences in the data, and gives discounts for latent or stretched appearances of the same data.
Think of it this way, if you had one audio sample of you saying:
"Hello"
and another of you saying
"       Helloo"
You would want to detect these samples as being very very similar.
The lag in the second sample is insignificant, as well as the long "o" at the end.
This is where DTW comes to the rescue.

It's a simple algorithm, but it's not easy to find a C# implementation on the web.
So I've been asked if i could write it down.
I hope I'll be able to post the more interesting implementations of fast DTW algorithms in the future.

Basic DTW implementation in C#:

 public static double DTW(double[] arr1, double[] arr2)  
     {  
       int M = arr1.Length;  
       int N = arr2.Length;  
       var DTW = new double[M + 1,N + 1];  
       //Initial matrix  
       DTW[0, 0] = 0;  
       for (int j = 1; j <= M; j++)  
       {  
         DTW[j, 0] = double.PositiveInfinity;  
       }  
       for (int i = 1; i <= N; i++)  
       {  
         DTW[0, i] = double.PositiveInfinity;  
       }  
       //End of Init  
       for (int i = 1; i <= M; i++)  
       {  
         for (int j = 1; j <= N; j++)  
         {  
           double cost = Math.Abs(arr1[i - 1] - arr2[j - 1]);  
           DTW[i, j] = cost + Math.Min(DTW[i - 1, j],        // insertion  
                         Math.Min(DTW[i, j - 1],    // deletion  
                              DTW[i - 1, j - 1])); // match  
         }  
       }  
       return DTW[M, N];  
     }  

References:

• Wikipedia - Dynamic time warping
• 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