Skip to content

Instantly share code, notes, and snippets.

@socrateslee
Created March 3, 2012 14:06
Show Gist options
  • Save socrateslee/1966342 to your computer and use it in GitHub Desktop.
Save socrateslee/1966342 to your computer and use it in GitHub Desktop.
Simple DTW(Dynamic Time Wrapping) in C#
//http://data-matters.blogspot.com/2008/07/simple-implementation-of-dtwdynamic.html
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace DTW
{
class SimpleDTW
{
double[] x;
double[] y;
double[,] distance;
double[,] f;
ArrayList pathX;
ArrayList pathY;
ArrayList distanceList;
double sum;
public SimpleDTW(double[] _x, double[] _y)
{
x = _x;
y = _y;
distance = new double[x.Length, y.Length];
f = new double[x.Length+1, y.Length+1];
for (int i = 0; i < x.Length; ++i){
for (int j = 0; j < y.Length; ++j){
distance[i, j] = Math.Abs(x[i] - y[j]);
}
}
for (int i = 0; i <= x.Length; ++i)
{
for (int j = 0; j <= y.Length; ++j)
{
f[i, j] = -1.0;
}
}
for (int i = 1; i <= x.Length; ++i) {
f[i,0] = double.PositiveInfinity;
}
for (int j = 1; j <= y.Length; ++j) {
f[0, j] = double.PositiveInfinity;
}
f[0, 0] = 0.0;
sum = 0.0;
pathX = new ArrayList();
pathY = new ArrayList();
distanceList = new ArrayList();
}
public ArrayList getPathX(){
return pathX;
}
public ArrayList getPathY() {
return pathY;
}
public double getSum(){
return sum;
}
public double[,] getFMatrix() {
return f;
}
public ArrayList getDistanceList() {
return distanceList;
}
public void computeDTW() {
sum = computeFBackward(x.Length, y.Length);
//sum = computeFForward();
}
public double computeFForward() {
for (int i = 1; i <= x.Length; ++i) {
for (int j = 1; j <= y.Length; ++j) {
if (f[i - 1, j] <= f[i - 1, j - 1] && f[i - 1, j] <= f[i, j - 1]) {
f[i, j] = distance[i - 1, j - 1] + f[i - 1, j];
}
else if (f[i, j - 1] <= f[i - 1, j - 1] && f[i, j - 1] <= f[i - 1, j]) {
f[i, j] = distance[i - 1, j - 1] + f[i, j - 1 ];
}
else if (f[i - 1, j-1 ] <= f[i , j - 1] && f[i - 1, j - 1] <= f[i-1, j ]) {
f[i, j] = distance[i - 1, j - 1] + f[i - 1, j - 1 ];
}
}
}
return f[x.Length, y.Length];
}
public double computeFBackward(int i, int j)
{
if (!(f[i, j] < 0.0) ){
return f[i, j];
}
else {
if (computeFBackward(i - 1, j) <= computeFBackward(i, j - 1) && computeFBackward(i - 1, j) <= computeFBackward(i - 1, j - 1)
&& computeFBackward(i - 1, j) < double.PositiveInfinity)
{
f[i, j] = distance[i - 1, j - 1] + computeFBackward(i - 1, j);
}
else if (computeFBackward(i, j - 1) <= computeFBackward(i - 1, j) && computeFBackward(i, j - 1) <= computeFBackward(i - 1, j - 1)
&& computeFBackward(i, j - 1) < double.PositiveInfinity)
{
f[i, j] = distance[i - 1, j - 1] + computeFBackward(i, j - 1);
}
else if (computeFBackward(i - 1, j - 1) <= computeFBackward(i - 1, j) && computeFBackward(i - 1, j - 1) <= computeFBackward(i, j - 1)
&& computeFBackward(i - 1, j - 1) < double.PositiveInfinity)
{
f[i, j] = distance[i - 1, j - 1] + computeFBackward(i - 1, j - 1);
}
}
return f[i, j];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment