Comment coder efficacement l'algorithme de déformation du temps dynamique avec une contrainte de localité?

Question

Pour deux listes, $ [S_1, S_2, ... S_N] $ et $ [T_1, T_2, ..., T_M] $

J'ai besoin de mettre en œuvre Dtw algorithme avec une contrainte supplémentaire:

Si $ s_i $ est apparié avec $ t_j $, alors l'élément suivant $ s_ {i + 1} $ doit être égalé avec quelque $ t_ {j + k} $ assez proche à $ t_j $ (c'est-à-dire $ 0 le k le w $ pour une taille de fenêtre fixe $ w $).

Cette contrainte doit tenir pour chaque $ s_i $.

1) existe-t-il une solution $ o (nm) $ à un tel problème?

2) Si un algorithme efficace n'existe pas, quelle serait une bonne solution pratique?

(Notez que la contrainte de localité mentionnée dans le Dtw Le lien ci-dessus est différent de la contrainte dont j'ai besoin).