How to efficiently code Dynamic Time Warping algorithm with a locality constrain?
-
04-11-2019 - |
Pergunta
For given two lists $[s_1, s_2, ... s_n]$ and $[t_1, t_2, ..., t_m]$
I need to implement DTW algorithm with one extra constraint:
If $s_i$ is matched with $t_j$ then the next element $s_{i+1}$ has to be matched with some $t_{j+k}$ close enough to $t_j$ (i.e. $0 \le k \le W$ for some fixed window size $W$).
This constraint has to hold for each $s_i$.
1) Does there exist $O(nm)$ solution to such problem?
2) If an efficient algorithm does not exist, what would be a good practical solution?
(Note that locality constraint mentioned in the DTW link above is different from the constraint I need).
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange