Towards Efficient Interactive Computation of Dynamic Time Warping Distance
Towards Efficient Interactive Computation of Dynamic Time Warping Distance
复制标题
动态时间扭曲距离的高效交互式计算
DOI：
10.1007/978-3-030-59212-7_3
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Akihiro Nishi;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
动态时间规整（DTW）是一种广泛使用的方法，它使我们能够有效地比较两个时间序列，可以在速度变化。给定两个长度为mandn的字符串A和B，有一个基本的动态规划算法，该算法计算A和B的DTW距离以及时间和空间上的最佳对齐。本文讨论了动态字符串DTW距离的交互式计算问题，其中字符编辑操作（插入、删除、替换）可以在字符串的任意位置进行。设Mand N分别为A和B的游程长度编码（RLE）的大小。我们提出了一个算法，占用空间和usestime更新一个紧凑的差分表示的DP表的每一个编辑操作，其中表示的单元格的数量，其值的编辑操作后的变化。我们的方法是至少一样有效的算法最近提出的Froese等人。运行的时间，是更快的，当小于，因为我们的初步实验表明，很可能是在大多数情况下的情况。
Thedynamic time warping(DTW) is a widely-used method that allows us to efficiently compare two time series that can vary in speed. Given two stringsAandBof respective lengthsmandn, there is a fundamental dynamic programming algorithm that computes the DTW distanceforAandBtogether with an optimal alignment intime and space. In this paper, we tackle the problem of interactive computation of the DTW distance for dynamic strings, denoted, where character-wise edit operation (insertion, deletion, substitution) can be performed at anarbitraryposition of the strings. LetMandNbe the sizes of therun-length encoding(RLE) ofAandB, respectively. We present an algorithm forthat occupiesspace and usestime to update a compact differential representationof the DP table per edit operation, wheredenotes the number of cells inwhose values change after the edit operation. Our method is at least as efficient as the algorithm recently proposed by Froese et al. running intime, and is faster whenis smaller thanwhich, as our preliminary experiments suggest, is likely to be the case in the majority of instances.