You are here:Home Practical exercises Dynamic Time Warping (DTW) in Python

Dynamic Time Warping (DTW) in Python

Although it's not really used anymore, Dynamic Time Warping (DTW) is a nice introduction to the key concept of Dynamic Programming.

This is a very simple implementation, and there are lots of ways you could make it better. Work through the steps below, then at the end you will find the complete code. I encourage you to try to improve it!

The videos are in full HD (1920 x 1080), so you can view them full screen. Or, right-click the video player and you will see options such as opening it in a new window, so you can watch the video at the same time as looking over the code. In total, the videos last about an hour.

All the code in this part of the site is released under a Creative Commons Attribution 3.0 Unported license.

  • Recap of how DTW works

    If you've forgotten how Dynamic Time Warping (DTW) works, here's a little reminder for you. Look elsewhere on speech.zone for more in-depth material on this topic.

  • A data structure for the grid

    Time to think like a computer scientist: algorithms and data structures! First, we need to decide on the main data structure.

  • Pretty printing

    To make debugging easier, we write a function that will print out a list of lists in a more readable way than simply printing the raw Python data structure.

  • The core algorithm

    It's time to actually implement the core algorithm, which will be surprisingly simple now that we've set up suitable data structures.

  • Recovering the alignment

    As wel as the overall cost of the shortest path, we might want to recover the alignment, so we need a way to do that too.

  • A data structure for recovering the alignment

    Here we implement a very simple data structure for holding backpointers.

  • Leaving a trail of backpointers

    Inside the core algorithm, we now need to keep a record of which path entering each cell in the grid was the best one.

  • Recovering the alignment from the backpointers

    After the iteration over the grid is finished, we need to go back and trace through the backpointers

  • How to implement backtracing

    There are several ways we could implement this part, so let's ask the audience for their suggestions.

  • One implementation of backtracing

    A simple solution is a 'while loop' and that's what we use here.

  • A more elegant object-oriented solution

    Some hints on how you could write a more elegant implementation, by making it more object-oriented.

  • The final DTW code

    Here's the complete code. It's a very simple solution, and could certainly be made more elegant. Why not try doing that for yourself, starting from this version?