-
Notifications
You must be signed in to change notification settings - Fork 0
/
DTW.py
70 lines (61 loc) · 1.98 KB
/
DTW.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
from matplotlib.patches import ConnectionPatch
import matplotlib.pyplot as plt
import numpy as np
import scipy.spatial.distance as dist
def dp(dist_mat):
N, M = dist_mat.shape
# Initialize the cost matrix
cost_mat = np.zeros((N + 1, M + 1))
for i in range(1, N + 1):
cost_mat[i, 0] = np.inf
for i in range(1, M + 1):
cost_mat[0, i] = np.inf
# Fill the cost matrix while keeping traceback information
traceback_mat = np.zeros((N, M))
for i in range(N):
for j in range(M):
penalty = [
cost_mat[i, j], # match (0)
cost_mat[i, j + 1], # insertion (1)
cost_mat[i + 1, j]] # deletion (2)
i_penalty = np.argmin(penalty)
cost_mat[i + 1, j + 1] = dist_mat[i, j] + penalty[i_penalty]
traceback_mat[i, j] = i_penalty
# Traceback from bottom right
i = N - 1
j = M - 1
path = [(i, j)]
while i > 0 or j > 0:
tb_type = traceback_mat[i, j]
if tb_type == 0:
# Match
i = i - 1
j = j - 1
elif tb_type == 1:
# Insertion
i = i - 1
elif tb_type == 2:
# Deletion
j = j - 1
path.append((i, j))
# Strip infinity edges from cost_mat before returning
cost_mat = cost_mat[1:, 1:]
return (path[::-1], cost_mat)
if __name__ == '__main__':
#example
x = np.array(["hello", 'wonderful', 'world'])
y = np.array(["hello", 'world'])
def dist(a, b):
return 0 if a==b else 1
# Distance matrix
N = x.shape[0]
M = y.shape[0]
dist_mat = np.zeros((N, M))
for i in range(N):
for j in range(M):
# dist_mat[i, j] = abs(x[i] - y[j])
dist_mat[i, j] = dist(x[i], y[j])
path, cost_mat = dp(dist_mat)
print("Alignment cost: {:.4f}".format(cost_mat[N - 1, M - 1]))
print("Normalized alignment cost: {:.4f}".format(cost_mat[N - 1, M - 1]/(N + M)))
print(path)