algorithm - 带时间戳的编辑/编辑距离 - 具有相似(最小)成本的不同路径

Question

我正在使用 Edit/Levenstein distance来衡量单词之间的相似度。与最简单的实现不同，我的信件有时间戳，假设样本编号 N=0,1,2,...

我面临的问题是，我可以沿着成本矩阵获得不同的路径，这些路径以相同(最小)成本结束，并且这些不同的路径与不同的目标字符串相关联。例如，如果我测量源字符串 aa 和目标字符串 bab 之间的距离，并且假设源字符串从时间戳 N=0 开始，那么我有 2成本相同为2的路径(一加一代):

1. 在 N=-1 处添加 b，保留第一个 a 不变，并将第二个 a 替换为 b.
2. 将第一个 a 替换为 b，将第二个 a 保持原样，并添加 b在 N=2。

在时间线上对齐，这 2 个结果是不同的:

Time:    ... -1 0 1 2 3 ...
Source:         a a
Target1:      b a b
Target2:        b a b

我需要知道什么时候发生，所以我可以根据一些标准在两个可能的目标之间进行选择。除了沿途追踪路径并跟踪所有可能导致成本最低的路径之外，还有其他方法吗？

我考虑过使用 Dynamic Time Warp相反，由于时间线首先是模型的一部分，但似乎由于成本矩阵被初始化为无穷大([0,0] 条目除外)，第一步将始终匹配第一个目标的帧到源的第一帧，导致目标在与源相同的时间戳开始。无论如何，使用 DTW 我仍然必须追踪导致相同最小成本的所有路径。

欢迎任何帮助或见解。

Answer 1

再想想你的问题，似乎对DTW或Levensthein有一点误解。两种算法都试图压缩和扩展序列以使它们相互匹配。因此，在 DTW 情况下，您的示例将具有以下解决方案:

Solution1:
  a a
 /| |
b a b

Solution2:
a a
| |\
b a b

Solution3:
a a
|\|\
b a b

如果您查看这些解决方案，您会注意到所有这些解决方案的成本都是 2，即在所有情况下，2 个 b 都被分配给 as。这些例子的意思是，在第一个序列中，与第二个序列相比，一个时间戳被压缩在一起。例如，在第一个解决方案中，b a 的前两个时间戳被压缩以形成与第二个序列的第一个 a 相对应的单个时间步长(第二个序列只是反转，第三种解决方案更复杂)。 DTW 旨在处理在某些部分以不同速度播放的序列，因此有“时间扭曲”类比。

如果您的时间步确实是固定的并且您只需要对齐它们，而不考虑任何实际的扭曲，您可以尝试所有对齐并计算成本。

像这样(假设 str2 是较短的):

for i = 0 to length( str1 ) - length( str2 ) do
  shift str2 by i to the left
  calculate number of different position between shifted str2 and str1
done
return i with lowest difference

假设您既需要移动又需要扭曲(某些东西可能已添加到开头并且时间步长可能不匹配)，然后考虑子序列 DTW。为此，您只需放宽边界条件即可。

假设您将字符串索引为 1 而不是 0，您可以这样编写 DTW:

diff( x, y ) = 1 if str1 at x != str2 at x 
               0 otherwise

cost( 0, 0 ) = 0;
cost( 0, * ) = infinity;
cost( *, 0 ) = infinity;
cost( x, y ) = min( cost( x-1, y-1 ), cost( x-1, y ), cost( y, y-1) ) + diff( x, y )

DTW-Cost 则为 cost( length( str1 ), length( str2 ) ) 并且您的路径可以从那里追溯到。对于子序列 DTW，您只需更改此:

diff( x, y ) = 1 if str1 at x != str2 at x 
               0 otherwise

cost( 0, 0 ) = 0;
cost( 0, * ) = 0;
cost( *, 0 ) = infinity; // yes this is correct and needed
cost( x, y ) = min( cost( x-1, y-1 ), cost( x-1, y ), cost( y, y-1) ) + diff( x, y )

然后您选择 DTW 成本作为 min( cost( x, length( str2 ) ) 并从 argmin( cost( x, length( str2 ) ) 追溯>。这假设你知道一个字符串是另一个的子字符串。如果你不知道这一点并且两者可能只有一个共同的扭曲中间你将不得不进行部分匹配，据我所知这仍然是一个开放的研究主题，因为需要选择一个无法明确定义的“最优性”概念。