动态时间规整 (DTW) 是一种算法，旨在衡量两个速度或时序可能不同的序列之间的相似性。它常用于时间数据对齐至关重要的任务，例如比较音频信号、语音或传感器数据。与要求序列长度相等或严格对齐的方法（例如欧氏距离）不同，DTW 通过非线性地扭曲时间轴来寻找最优匹配，从而最小化对应点之间的总距离。这使得它对于序列之间速度、持续时间或节奏的变化具有鲁棒性。核心思想是构建一个网格，其中每个单元格代表对齐两个点的成本，然后找到通过该网格且累积成本最低的路径。
在音频匹配中，DTW 用于比较从音频信号中提取的特征，即使它们的长度或节奏不同。例如，在语音识别中，可以使用 DTW 对以不同速度说出的同一词语的两个录音进行对齐，以确定它们是否匹配。类似地，在音乐分析中，DTW 可以识别节奏不同的歌曲中相似的旋律或节奏。一个实际应用是哼唱查询系统：用户哼唱一段旋律，DTW 将哼唱的音高轮廓与歌曲数据库进行对齐，以找到最接近的匹配。该算法首先从音频片段中提取梅尔频率倒谱系数 (MFCC) 或色度向量等特征，然后使用 DTW 计算这些特征序列之间的最优对齐。这种对齐考虑了时间差异，确保了鲁棒的相似性度量。
实现通常包括三个步骤。首先，将音频信号转换为特征向量（例如，使用快速傅里叶变换或 MFCC）。接下来，构建一个距离矩阵，其中每个元素表示第一个音频片段中的特征向量与第二个音频片段中的特征向量之间的距离。最后，应用动态规划算法来找到通过该矩阵的总距离最小的路径。步长（例如，允许对角线、水平或垂直移动）和斜率限制（防止过度扭曲）等约束确保了真实的对齐。虽然 DTW 计算量很大（对于长度为 N 的序列，时间复杂度为 O(N²)），但像 Sakoe-Chiba 带限制这样的优化可以限制搜索空间，使其在实时使用中变得可行。开发人员经常将 DTW 集成到音乐推荐引擎、语音认证或音频同步工具等应用程序中，这些应用程序处理时间变化至关重要。