矩阵反对角线的矩形化紧凑表示（DTW场景）

在动态时间规整（DTW）计算中，为了优化缓存命中率，通常会将N×N方阵的反对角线元素按紧凑形式存储到二维数组中。下面直接给出原始方阵与紧凑数组的双向索引映射函数，以及双向增量映射函数的具体实现：

符号定义 #

• 原始N×N方阵：索引为 (i, j)，其中 0 ≤ i, j < N
• 紧凑存储N×N数组：索引为 (r, c)，其中 0 ≤ r, c < N
• 反对角线标识：k = i + j（原始方阵中，同一反对角线的元素具有相同的k值）

1. 双向索引映射函数 #

从原始方阵 (i,j) 到紧凑数组 (r,c) #

def original_to_compact(i, j, N):
    k = i + j
    if k < N:
        # 前N条反对角线（k从0到N-1），行号为k，列号为i
        r = k
        c = i
    else:
        # 后N-1条反对角线（k从N到2N-2），行号为k - N，列号为j - (k - N)
        r = k - N
        c = j - (k - N)
    return (r, c)

从紧凑数组 (r,c) 到原始方阵 (i,j) #

def compact_to_original(r, c, N):
    max_c_forward = r  # 前半段反对角线的最大列索引
    if c <= max_c_forward:
        k = r
        i = c
        j = k - i
    else:
        k = r + N
        j = c + r
        i = N - c
    return (i, j)

2. 双向增量映射函数 #

增量映射用于快速计算相邻元素的索引偏移，无需重新计算完整映射，适合DTW的迭代计算场景：

原始方阵到紧凑数组的增量映射 #

假设当前原始索引为 (i,j)，对应紧凑索引 (r,c)，则：

• 向下移动（(i+1,j)）：
  若 i+1 + j < N，则偏移为 (+1, +1)；否则偏移为 (0, 0)
• 向右移动（(i,j+1)）：
  若 i + j+1 < N，则偏移为 (+1, 0)；否则偏移为 (0, +1)
• 对角线移动（(i+1,j+1)）：
  若 i+1 + j+1 < N，则偏移为 (+2, +1)；否则偏移为 (+1, 0)

紧凑数组到原始方阵的增量映射 #

假设当前紧凑索引为 (r,c)，对应原始索引 (i,j)，则：

• 向下移动（(r+1,c)）：
  直接代入compact_to_original(r+1, c, N)计算，或根据当前段判断：
  若属于前半段，新索引为 (c, (r+1)-c)；若属于后半段，新索引为 (N - c, c + (r+1))
• 向右移动（(r,c+1)）：
  直接代入compact_to_original(r, c+1, N)计算，或根据当前段判断：
  若属于前半段，新索引为 (c+1, r - (c+1))；若属于后半段，新索引为 (N - (c+1), (c+1) + r)

验证示例（N=4） #

以N=4为例：

• 原始索引(1,3)（k=4 ≥4）→ 紧凑索引：r=4-4=0，c=3 - (4-4)=3 → (0,3)
• 紧凑索引(0,3) → 属于后半段，k=0+4=4，j=3+0=3，i=4-3=1 → 正确对应原始(1,3)

内容的提问来源于stack exchange，提问作者Tom Huntington