DTW可以用来干什么呢？
DWT可以计算两个时间序列的相似度，尤其适用于不同长度、不同节奏的时间序列（比如不同的人读同一个词的音频序列）。距离越近，相似度越高。
DTW在语音中的运用：
在实际应用中，比如说语音识别中的孤立词识别，我们首先训练好常见字的读音，提取特征后作为一个模板。当需要识别一个新来的词的时候，也同样提取特征，然后和训练数据库中的每一个模板进行匹配，计算距离。求出最短距离的那个就是识别出来的字了。
那么距离如何计算呢，因为待识别的语音的长度和模板的长度不总是一直的，也很难做到一致，所以DTW就可以解决这个问题。
DTW如何计算距离呢？
我们都知道，当两个序列的长度一致时，计算距离，直接对应位求距离，然后把每对对应点的距离求和，即可作为两个序列的距离。但是由于两个序列的长度不一致，计算距离的时候上述方法肯定无效。所以，就要考虑，这个一个序列的点，需要匹配另一个序列的多个点，另一个序列也可以匹配这个序列的多个点。
如下图所示：
那么如何匹配呢？
在这之前，需要介绍匹配的规则，这一点很重要：
1） 边界条件：任何一种语音的发音快慢都有可能变化，但是其各部分的先后次序不可能改变，所以两个序列的初始点和结束点之间肯定存在匹配关系。
2） 连续性：就是不可能跨过某个点去匹配，只能和自己相邻的点对齐。
3） 单调性：上图中的灰色线不会相交。
知道这些之后，再举个栗子就明白如何通过DWT来计算两个序列之间匹配关系以及距离了：
栗子：
有两个一维数组，它们的长度分别为：
S1=[1,2,3,4,5,5,5,4]
S2=[3,4,5,5,5,4]
计算S1和S2各个元素之间的距离，这里由于一维序列，所以选择曼哈顿距离（差值的绝对值）作为两两元素之间的距离，得到如下的距离矩阵：
s2[0] s2[1] s2[2] s2[3] s2[4] s5[5]
s1[0][[2. 3. 4. 4. 4. 3.]
s1[1] [1. 2. 3. 3. 3. 2.]
s1[2] [0. 1. 2. 2. 2. 1.]
s1[3] [1. 0. 1. 1. 1. 0.]
s1[4] [2. 1. 0. 0. 0. 1.]
s1[5] [2. 1. 0. 0. 0. 1.]
s1[6] [2. 1. 0. 0. 0. 1.]
s1[7] [1. 0. 1. 1. 1. 0.]]
则序列的元素正确匹配的结果就是从距离矩阵的左上角走到最下角，把经过的元素累加，累加的和最小，则该最小和就是这两个序列使用DWT算法求得的距离了。匹配关系就是路径经过的元素所在的索引如（2,3），即s1[2]和s2[3]进行匹配。是不是很简单？
如何寻找最短路径呢？
怪不得名字叫做DTW(动态时规整，就是使用的动态规划求得最短距离路径)。
从上面匹配的规则，可知:路径从前一个元素经过(i,j)元素时，前一个元素只能来自(i-1,j-1), (i-1,j)或(i, j-1)这三个位置。否则，就会违背上述的匹配规律，感兴趣的小伙伴可以动手画一下图，会出现灰色线交叉的现象。
具体步骤：
1、求累计距离矩阵：
如上图：每个元素位置的累积距离数值为箭头指向它的元素的累计数值加上该元素本身的值。如果有三个箭头，则取这三个累计数值中的最小的一个作为该元素的累积数值。
2、得到累积矩阵之后，再回溯，得到最小累积和的路径
具体就不讲了，确实太简单了（还有其他事情【🤦】），看下python代码就知道了：感谢@Chelsea_Daggerhttps://www.jianshu.com/p/05bee48cc6a2提供的代码。
# -*- coding: UTF-8 -*-
from numpy import array, zeros, argmin, inf, equal, ndim
s1 = [1, 2, 3, 4, 5, 5, 5, 4]
s2 = [3, 4, 5, 5, 5, 4]r, c = len(s1), len(s2)
D0 = zeros((r+1,c+1))
D0[0,1:] = inf
D0[1:,0] = inf
D1 = D0[1:,1:]#浅复制for i in range(r):#生成原始距离矩阵for j in range(c):D1[i,j] = abs(s1[i]-s2[j]) # 曼哈顿距离M = D1.copy()
for i in range(r):#代码核心，动态计算最短距离for j in range(c):D1[i,j] += min(D0[i,j],D0[i,j+1],D0[i+1,j])i,j = array(D0.shape) - 2
#最短路径
p,q = [i],[j]
while(i>0 or j>0):tb = argmin((D0[i,j],D0[i,j+1],D0[i+1,j]))if tb==0 :i-=1j-=1elif tb==1 :i-=1else:j-=1p.insert(0,i)q.insert(0,j)print(M)
#原始距离矩阵
print(list(zip(p,q)))
#匹配路径过程
print(D1)
#Cost Matrix或者叫累积距离矩阵
print(D1[-1,-1])
#序列距离
