dtw- (Fast) Dynamic Time Warping

Safe HaskellNone



This module implements dynamic time warping as described here: http://en.wikipedia.org/w/index.php?title=Dynamic_time_warping

Additionally fastDtw is implemented as described in the paper: "FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space" by Stan Salvador and Philip Chan.

Please note that fastDtw is only an approximative solution. If you need the optimal solution and can bear with the heavily increased demand both in cpu and in memory you should use dtwMemo or dtwMemoWindowed.


>>> -- create two sample datasets
>>> let as = [ sin x | x <- [0,0.1..pi] ]
>>> let bs = [ sin (x+0.1) | x <- [0,0.1..pi] ]
>>> -- define a cost function between two datapoints
>>> let dist x y = abs (x-y)
>>> -- define a function that will half the size of a dataset (see below)
>>> let shrink xs = case xs of (a:b:cs) -> (a+b)/2 : shrink cs; a:[] -> [a]; [] -> []
>>> -- calculate the cost with fastDtw and dtwMemo for comparison
>>> cost $ fastDtw dist shrink 2 as bs :: Float
>>> cost $ dtwMemo (\x y -> abs (x-y)) as bs :: Float

Some words on the shrink function

Care must be taken when choosing a shrink function. It's vital that the resolution is halfed, this is not exactly a problem with the algorithm but with the implementation. The lower resolution dataset should be an honest representation of the higher resolution dataset. For starters binning as in the example above should suffice.



dtwNaive :: (Ord c, Fractional c, DataSet a, DataSet b) => (Item a -> Item b -> c) -> a -> b -> c Source

this is the naive implementation of dynamic time warping no caching what so ever is taking place this should not be used and is just used as a reference for the other implementations

dtwMemo :: (Ord c, Fractional c, DataSet a, DataSet b) => (Item a -> Item b -> c) -> a -> b -> Result c Source

this is the "standard" implementation of dynamic time warping O(N^2) is achieved by memoization of previous results

fastDtw Source


:: (Ord c, Fractional c, DataSet a) 
=> (Item a -> Item a -> c) 
-> (a -> a)

function that shrinks a dataset by a factor of two

-> Int

radius that the search window is expanded at each resolution level

-> a

first dataset

-> a

second dataset

-> Result c


this is the "fast" implementation of dynamic time warping as per the authors this methods calculates a good approximate result in O(N), depending on the usecase the windowsize should be tweaked

class DataSet dataset where Source

a generic dataset is basically just an indexing function | and an indicator of the dataset size

Associated Types

type Item dataset :: * Source


ix :: dataset -> Int -> Item dataset Source

len :: dataset -> Int Source


DataSet [a] 
DataSet (Seq a) 
DataSet (Vector a) 
Unbox a => DataSet (Vector a) 
Storable a => DataSet (Vector a) 

data Result a Source




cost :: a
path :: Path


Eq a => Eq (Result a) 
Read a => Read (Result a) 
Show a => Show (Result a) 

type Path = [Index] Source

type Index = (Int, Int) Source