Dynamic Time Warping

Compute the dynamic time warping (DTW) distance between two sequences.

Two recordings of the same word, or two heartbeats, can have the same shape but run at different speeds. Comparing them point by point then gives a large distance. DTW lets one sequence stretch or shrink in time: it finds the alignment of the two sequences with the lowest total cost.

Let cost(i, j) = |a[i] - b[j]|. Fill a table D of size (len(a) + 1, len(b) + 1) with D[0, 0] = 0 and every other border cell set to infinity. Then

D[i, j] = cost(i - 1, j - 1) + min(D[i - 1, j], D[i, j - 1], D[i - 1, j - 1])

The distance is D[len(a), len(b)]. Each step of the path either moves both sequences forward, or holds one of them in place while the other moves.

Function signature

def dtw_distance(a, b):

Example

Input

dtw_distance([1, 3, 4, 9], [1, 3, 7, 8, 9])

Output

4.0

Reasoning

The best alignment matches 1-1 and 3-3 for free, then 4-7 for a cost of 3, 9-8 for a cost of 1, and 9-9 for free. The value 9 is used twice, which is the stretch that DTW allows. The total is 4.

Constraints and notes

• Both sequences are non-empty 1D sequences of numbers.
• DTW is symmetric: swapping a and b gives the same distance.
• Return a plain float.