基于自适应搜索窗口的序列相似比对算法

摘要：

DTW(Dynamic Time Warping)算法被广泛应用于序列数据比对,以度量序列间距离,但算法较高的时间复杂度限制了其在长序列比对上的应用.提出基于自适应搜索窗口的序列相似比对算法(ADTW),算法利用分段聚集平均(Piecewise Aggregate Approximation,PAA)策略进行序列抽样得到低精度序列,然后计算低精度序列下的比对路径,并根据低精度距离矩阵上的梯度变化预测路径偏差,限制路径搜索窗口的拓展范围;随后算法逐步提高序列精度,并在搜索窗口内修正路径、计算新的搜索窗口,最终,实现DTW距离和相似比对路径的快速求解.对比FastDTW,ADTW算法在同等度量准确率下提高计算效率约20%,其时间复杂度为O(n) .

关键词：相似搜索、时序度量、动态时间规整(DTW)、搜索窗口

所属期刊栏目：55

分类号：TP391.13(计算技术、计算机技术)

资助基金：国家自然科学基金61303016

在线出版日期：2019-10-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：54-59,71