FastDTW（Fast Dynamic Time Warping）是一种用于计算两个时间序列之间相似性的高效算法。它是经典动态时间规整（DTW）算法的一种近似方法，旨在解决 DTW 计算复杂度高的问题。

为了更好地理解 FastDTW，我们首先需要了解它要解决的问题和它改进的原始算法。

1. 背景：什么是 DTW？

动态时间规整 (Dynamic Time Warping, DTW) 是一种用于衡量两个不同长度的时间序列之间相似度的经典算法。它的核心思想是找到两个序列之间的最佳对齐方式，即使它们在时间轴上有非线性（如速度不一）的偏移。

• 解决的问题：例如，比较两个人说同一个单词的音频序列，尽管一个人说得快，一个人说得慢，DTW 也能有效地匹配它们。
• 缺点：经典 DTW 使用动态规划来填充一个成本矩阵，其时间和空间复杂度都是 O(NM)，其中 N 和 M 是两个序列的长度。当序列很长时（例如，含有数万个数据点的传感器数据），计算会变得非常缓慢且消耗内存。

2. FastDTW 的核心思想

FastDTW 的核心思路是 “分而治之” 和 “多分辨率分析”。它通过将问题规模不断缩小，在低分辨率上计算一个粗略的对齐路径，然后逐步细化这个路径，最终得到完整分辨率上的对齐结果。

这种方法极大地降低了计算复杂度和内存占用，从 O(NM) 降到了 O(N)（线性复杂度），同时其计算结果与精确的 DTW 非常接近。

3. FastDTW 的工作原理（三步流程）

FastDTW 算法主要包含三个步骤：

第1步：粗化（Coarsening） 将原始时间序列通过平均或抽取的方式进行压缩，生成分辨率越来越低的序列。例如，将每两个相邻的点合并为一个点（取平均值），这样序列长度就减半了。这个过程可以重复多次，直到序列变得非常短。

• 原始序列： [1, 2, 3, 4, 5, 6]
• 第一次粗化（粒度=2）： [(1+2)/2, (3+4)/2, (5+6)/2] => [1.5, 3.5, 5.5]
• 第二次粗化（粒度=2）： [(1.5+3.5)/2, (5.5)/?] (通常通过填充处理奇数长度) => [2.5, 5.5]

第2步：投影（Projection） 在最低分辨率的序列上，使用标准的 DTW 算法。因为序列非常短，所以计算速度极快。计算出的最优弯曲路径（Warping Path）我们称之为 低分辨率路径。

第3步：细化（Refining） 将低分辨率路径投影到更高一级分辨率的序列上。这个投影路径在高分辨率上提供了一个搜索窗口（通常会在该路径周围扩展一个小的半径，例如 radius=1）。算法只在这个狭窄的窗口内进行DTW计算，而不是在整个矩阵上计算。这个过程逐级向上重复，直到投影回原始的全分辨率序列。