文件名称：论文研究-基于自适应搜索窗口的序列相似比对算法.pdf
文件大小：685KB
文件格式：PDF
更新时间：2022-10-01 07:54:05
论文研究
DTW（Dynamic Time Warping）算法被广泛应用于序列数据比对，以度量序列间距离，但算法较高的时间复杂度限制了其在长序列比对上的应用。提出基于自适应搜索窗口的序列相似比对算法（ADTW），算法利用分段聚集平均（Piecewise Aggregate Approximation，PAA）策略进行序列抽样得到低精度序列，然后计算低精度序列下的比对路径，并根据低精度距离矩阵上的梯度变化预测路径偏差，限制路径搜索窗口的拓展范围；随后算法逐步提高序列精度，并在搜索窗口内修正路径、计算新的搜索窗口，最终，实现DTW距离和相似比对路径的快速求解。对比FastDTW，ADTW算法在同等度量准确率下提高计算效率约20%，其时间复杂度为[O(n)]。