Dynamic Time Warping

Implements the dynamic time warping distance of Vintsyuk (1968) and its backtracing in cython.

edist.dtw.dtw()

Computes the dynamic time warping distance between the input sequence x and the input sequence y, given the element-wise distance function delta.

Parameters:
  • x (list) – a sequence of objects.
  • y (list) – another sequence of objects.
  • delta (function) – a function that takes an element of x as first and an element of y as second input and returns the distance between them.
Returns:

d – the dynamic time warping distance between x and y according to delta.
Return type:

float
edist.dtw.dtw_backtrace()

Computes a co-optimal alignment between the two input sequences x and y, given the element-wise distance function delta. This mechanism is deterministic and will always prefer replacements over other options.

Parameters:
  • x (list) – a sequence of objects.
  • y (list) – another sequence of objects.
  • delta (function) – a function that takes an element of x as first and an element of y as second input and returns the distance between them.
Returns:

alignment – A co-optimal alignment between x and y according to dynamic time warping.
Return type:

class alignment.Alignment
edist.dtw.dtw_backtrace_matrix()

Computes a matrix, summarizing all co-optimal alignments between x and y in a matrix P, where entry P[i, j] specifies the fraction of co-optimal alignments in which node x[i] has been aligned with node y[j].

Parameters:
  • x (list) – a sequence of objects.
  • y (list) – another sequence of objects.
  • delta (function) – a function that takes an element of x as first and an element of y as second input and returns the distance between them.
Returns:

  • P (array_like) – a matrix, where entry P[i, j] specifies the fraction of co-optimal alignments in which node x[i] has been aligned with node y[j].
  • K (array_like) – a matrix that contains the counts for all co-optimal alignments in which node x[i] has been aligned with node y[j].
  • k (int) – the number of co-optimal alignments overall, such that P = K / k.
edist.dtw.dtw_backtrace_stochastic()

Computes a co-optimal alignment between the two input sequences x and y, given the element-wise distance function delta. This mechanism is stochastic and will return a random co-optimal alignment.

Note that the randomness does _not_ produce a uniform distribution over all co-optimal alignments because reandom choices at the start of the alignment process dominate. If you wish to characterize the overall distribution accurately, use sed_backtrace_matrix instead.

Parameters:
  • x (list) – a sequence of objects.
  • y (list) – another sequence of objects.
  • delta (function) – a function that takes an element of x as first and an element of y as second input and returns the distance between them.
Returns:

alignment – A co-optimal alignment between x and y according to dynamic time warping.
Return type:

class alignment.Alignment
edist.dtw.dtw_euclidean()

Computes the multivariate dynamic time warping distance between two input arrays x and y, using the Euclidean distance as element-wise distance measure.

Parameters:
  • x (array_like) – a m x K matrix of doubles.
  • y (array_like) – a n x K matrix of doubles.
Returns:

d – the dynamic time warping distance between x and y.
Return type:

float
edist.dtw.dtw_manhattan()

Computes the multivariate dynamic time warping distance between two input arrays x and y, using the Manhattan distance as element-wise distance measure.

Parameters:
  • x (array_like) – a m x K matrix of doubles.
  • y (array_like) – a n x K matrix of doubles.
Returns:

d – the dynamic time warping distance between x and y.
Return type:

float
edist.dtw.dtw_numeric()

Computes the dynamic time warping distance between two input arrays x and y, using the absolute value as element-wise distance measure.

Parameters:
  • x (array_like) – an array of doubles.
  • y (array_like) – another array of doubles.
Returns:

d – the dynamic time warping distance between x and y.
Return type:

float
edist.dtw.dtw_string()

Computes the dynamic time warping distance between two input strings x and y, using the Kronecker distance as element-wise distance measure.

Parameters:
  • x (str) – a string.
  • y (str) – another string.
Returns:

d – the dynamic time warping distance between x and y.
Return type:

float