基于动态时间规整（Dynamic Time Warping, DTW）的文本序列相似度计算算法详解

1. 算法背景与问题描述

动态时间规整（DTW）原本是语音识别领域的一种经典算法，用于解决两个时间序列在时间轴上不对齐时的相似度计算问题。在自然语言处理中，我们可以将文本序列（如字符序列、词序列、甚至句子编码向量序列）看作时间序列，用DTW来计算它们之间的相似度。

核心问题

假设我们有两个文本序列：

• 序列A：长度n，A = a₁, a₂, ..., aₙ
• 序列B：长度m，B = b₁, b₂, ..., bₘ

这两个序列可能：

1. 长度不同（n ≠ m）
2. 存在局部的拉伸、压缩或延迟
3. 需要找到最优的对齐方式，使得对齐后的累积距离最小

例如，比较两个句子：

• "今天/天气/真/好" (4个词)
• "今天/的/天气/真的/很好" (5个词)

传统编辑距离能处理插入/删除/替换，但DTW提供了更灵活的对齐方式，特别适合序列元素是连续数值向量的情况（如词嵌入序列）。

2. 算法原理与数学形式化

2.1 基本定义

设我们有距离函数d(aᵢ, bⱼ)，衡量元素aᵢ和bⱼ之间的距离（如欧氏距离、余弦距离）。

规整路径（Warping Path）：
一个连续路径W = w₁, w₂, ..., w_K，其中w_k = (i_k, j_k)满足：

1. 边界条件：w₁ = (1,1), w_K = (n,m)（必须从两端开始对齐）
2. 单调性：i₁ ≤ i₂ ≤ ... ≤ i_K, j₁ ≤ j₂ ≤ ... ≤ j_K（不能回溯）
3. 连续性：i_{k+1} - i_k ≤ 1, j_{k+1} - j_k ≤ 1（每一步最多移动一个单位）

2.2 目标函数

DTW的目标是找到使累积距离最小的规整路径：

\[DTW(A,B) = \min_{W} \sqrt{\sum_{k=1}^{K} d(a_{i_k}, b_{j_k})} \]

实际上常用简化形式（去掉平方根）：

\[DTW(A,B) = \min_{W} \sum_{k=1}^{K} d(a_{i_k}, b_{j_k}) \]

3. 动态规划求解过程

3.1 构建累积距离矩阵

定义一个n×m的矩阵D，其中D[i][j]表示子序列A[1:i]和B[1:j]之间的最小累积距离。

初始化：

\[D[0][0] = 0 \]

\[ D[i][0] = \infty \quad (i=1,...,n) \]

\[ D[0][j] = \infty \quad (j=1,...,m) \]

递推公式：

\[D[i][j] = d(a_i, b_j) + \min \begin{cases} D[i-1][j] & \text{（A中插入间隙）} \\ D[i][j-1] & \text{（B中插入间隙）} \\ D[i-1][j-1] & \text{（直接匹配）} \end{cases} \]

3.2 算法步骤详解

让我们用具体例子说明，假设：
A = [1, 3, 4, 9, 8]（长度5）
B = [1, 4, 3, 8]（长度4）
距离函数：绝对差d(x,y) = |x-y|

步骤1：构建距离矩阵
先计算局部距离矩阵d[i][j]：

步骤2：构建累积距离矩阵D
初始化第一行第一列为无穷大（除了D[0][0]=0）

递推计算：

• D[1][1] = d(1,1)+min(∞,∞,0) = 0+0 = 0
• D[1][2] = d(1,4)+min(∞,D[1][1],∞) = 3+0 = 3
• D[1][3] = d(1,3)+min(∞,D[1][2],∞) = 2+3 = 5
• D[1][4] = d(1,8)+min(∞,D[1][3],∞) = 7+5 = 12
• D[2][1] = d(3,1)+min(D[1][1],∞,∞) = 2+0 = 2
• D[2][2] = d(3,4)+min(D[2][1],D[1][2],D[1][1]) = 1+min(2,3,0)=1+0=1
• 继续计算...

最终D矩阵：

步骤3：回溯找到最优路径
从D[5][4]=3开始回溯：

• 比较D[4][3]=7, D[4][4]=3, D[5][3]=10
• 最小是D[4][4]=3，来自D[3][3]=2
• 继续回溯...

得到路径：W = [(1,1), (2,2), (3,2), (4,3), (5,4)]
对应匹配：1↔1, 3↔4, 4↔4, 9↔3, 8↔8

4. 在NLP中的具体应用

4.1 词嵌入序列对齐

假设每个词用d维向量表示，A和B是词向量序列：
d(a_i, b_j) = 1 - cos_sim(a_i, b_j) 或欧氏距离

应用场景：

• 句子相似度计算（考虑词序变化）
• 短文本匹配
• 对话系统中用户query与模板的匹配

4.2 优化与变种

4.2.1 窗口约束（Sakoe-Chiba Band）
限制路径不能偏离对角线太远，设窗口大小r：
|i - j| ≤ r
时间复杂度从O(nm)降到O(r·max(n,m))

4.2.2 步长模式限制
限制路径的斜率，避免过度拉伸：

• 常见：(1,0), (0,1), (1,1) 三种移动
• 或增加(1,2), (2,1)等

4.2.3 下界加速
在搜索前计算下界，快速排除不相似序列：

• LB_Kim：基于首尾元素距离
• LB_Keogh：基于包络线

5. 实际计算示例（文本场景）

5.1 字符级DTW

比较两个单词："intention" 和 "execution"

字符映射为ASCII码（简化）：
A = [105, 110, 116, 101, 110, 116, 105, 111, 110] ("intention")
B = [101, 120, 101, 99, 117, 116, 105, 111, 110] ("execution")

距离函数：d(x,y) = |x-y|

计算过程同上，最终得到最小累积距离，反映两个词的相似度。

5.2 代码实现框架

import numpy as np

def dtw_distance(seq1, seq2, dist_func):
    """基础DTW实现"""
    n, m = len(seq1), len(seq2)
    D = np.full((n+1, m+1), np.inf)
    D[0, 0] = 0
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            cost = dist_func(seq1[i-1], seq2[j-1])
            D[i, j] = cost + min(D[i-1, j],    # 插入
                                 D[i, j-1],    # 删除  
                                 D[i-1, j-1])  # 匹配
    return D[n, m]

# 带窗口约束的版本
def dtw_window(seq1, seq2, dist_func, window_size):
    n, m = len(seq1), len(seq2)
    D = np.full((n+1, m+1), np.inf)
    D[0, 0] = 0
    
    for i in range(1, n+1):
        # 只计算窗口内的j
        lower = max(1, i - window_size)
        upper = min(m, i + window_size)
        for j in range(lower, upper+1):
            cost = dist_func(seq1[i-1], seq2[j-1])
            D[i, j] = cost + min(D[i-1, j] if i>1 else np.inf,
                                 D[i, j-1] if j>1 else np.inf,
                                 D[i-1, j-1] if (i>1 and j>1) else np.inf)
    return D[n, m]

6. 算法特性与适用场景

6.1 优点

1. 处理不等长序列：不需要预处理为等长
2. 弹性对齐：允许序列局部拉伸/压缩
3. 全局最优：保证找到最小累积距离路径
4. 适用于连续空间：适合词向量等连续表示

6.2 缺点

1. 时间复杂度高：O(nm)，长序列计算慢
2. 非度量性：不满足三角不等式
3. 对异常值敏感：单个大距离会显著影响结果
4. 可解释性有限：路径可能不直观

6.3 NLP应用场景

1. 语音识别：音频特征序列与模板匹配
2. 手写识别：笔画序列匹配
3. 时间序列分类：文本情感随时间变化分析
4. 基因序列比对：生物信息学中的类似问题
5. 多模态对齐：文本与视频帧序列对齐

7. 扩展与改进

7.1 Soft-DTW

将min操作替换为soft-min：

\[\text{soft-min}_\gamma(x_1,...,x_n) = -\gamma \log \sum_{i=1}^n e^{-x_i/\gamma} \]

当γ→0时退化为标准DTW，γ>0时整个函数可微，可用于深度学习。

7.2 FastDTW

分层逼近方法：

1. 粗化：降低序列分辨率
2. 投影：在粗粒度上计算DTW路径
3. 细化：在细粒度上搜索路径周围
   时间复杂度降至O(n)

7.3 与其他算法的比较

8. 总结

DTW为NLP中的序列相似度计算提供了一种弹性对齐的方法。虽然计算成本较高，但通过窗口约束、下界加速等技术可以在实际中应用。在处理词向量序列、语音特征序列等连续值序列时，DTW相比传统编辑距离能更好地捕捉序列间的相似性。随着深度学习发展，Soft-DTW等可微变种可以与神经网络结合，实现端到端的序列对齐学习。