algorithm - 是否有稀疏编辑距离算法？

Question

假设您有两个长度为 100,000 的字符串，其中包含零和一。你可以计算他们的edit distance在大约 10^10 次操作中。

如果每个字符串只有 100 个，其余的都是零，那么我可以使用 100 个整数来表示每个字符串，说明它们在哪里。

Is there a much faster algorithm to compute the edit distance using this sparse representation? Even better would be an algorithm that also uses 100^2 space instead of 10^10 space.

为了给出一些测试，考虑这两个字符串，每个字符串有 10 个。整数表示每个字符串中的位置。

[9959, 10271, 12571, 21699, 29220, 39972, 70600, 72783, 81449, 83262]

[9958, 10270, 12570, 29221, 34480, 37952, 39973, 83263, 88129, 94336]

在算法方面，如果我们有两个长度为 n 的稀疏二进制字符串。每个由 k 表示每个整数，是否存在 O(k^2)时间编辑距离算法？

Answer 1

当然!有这么多 0 的可能操作太少了。我的意思是，答案最多是200。

看一眼

10001010000000001
vs       ||||||
10111010100000010

用管道查看所有的零。你最终删除哪一个有关系吗？不。那是关键。

解决方案 1

让我们考虑正常的 n*m 解决方案:

dp(int i, int j) {
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j), dp(i-1, j-1), dp(i, j-1) );
}

如果几乎每个字符都是 0，那么什么会占用最多的时间？

if( str1[i-1] == str1[j-1] ) { // They will be equal so many times, (99900)^2 times!
    return dp(i-1, j-1);
}

我可以想象成千上万的递归。您真正需要的逻辑只是约 200 个关键点。你可以忽略其余的。一个简单的修改将是

if( str1[i-1] == str1[j-1] ) {
    if( str1[i-1] == 1 )
        return dp(i-1, j-1); // Already hit a critical point

    // rightmost location of a 1 in str1 or str2, that is <= i-1
    best = binarySearch(CriticalPoints, i-1);
    return dp(best + 1, best + 1); // Use that critical point
    // Important! best+1 because we still want to compute the answer at best
    // Without it, we would skip over in a case where str1[best] is 1, and str2[best] is 0.
}

CriticalPoints 将是包含 str1 或 str2 中每个 1 的索引的数组。确保在二进制搜索之前对其进行排序。记住那些 gochya 的。我的逻辑是:好的，我需要确保在索引 best 处计算答案本身，所以让我们使用 best + 1作为参数。但是，如果 best == i - 1 ，我们陷入了一个循环。我会尽快处理 str1[i-1] == 1查看。完成，呸。

您可以通过注意，在最坏的情况下，您将命中所有 200*100000 个构成临界点的 i 和 j 组合，并且当这些临界点调用 min(a, b, c) 时，您可以快速检查正确性。 ，它只进行三个递归函数调用。如果这些函数中的任何一个是关键点，那么它就是我们已经计算过的那些 200*100000 的一部分，我们可以忽略它。如果不是，那么在 O(log(200)) 中，它会在另一个关键点上进行一次调用(现在，我们知道这是我们已经计算过的 200*100000 的一部分)。因此，每个临界点最坏的情况是 3*log(200)时间不包括对其他关键点的调用。同样，第一个函数调用将落入 log(200) 中的临界点。时间。因此，我们的上限为 O(200*100000*3*log(200) + log(200))。

此外，请确保您的备忘录表是一个哈希图，而不是一个数组。 10^10 内存不适合您的计算机。

解决方案 2

您知道答案最多为 200，因此请避免自己计算超过这么多深度的操作。

dp(int i, int j) { // O(100000 * 205), sounds good to me.
    if( abs(i - j) > 205 )
        return 205; // The answer in this case is at least 205, so it's irrelevant to calculating the answer because when min is called, it wont be smallest.
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j), dp(i-1, j-1), dp(i, j-1) );
}

这个很简单，但我把它留给解决方案二，因为这个解决方案似乎是凭空出现的，而不是分析问题并找出慢的部分在哪里以及如何优化它。不过，请将其保存在您的工具箱中，因为您应该编写此解决方案的代码。

解决方案 3

就像解决方案 2 一样，我们可以这样做:

dp(int i, int j, int threshold = 205) {
    if( threshold == 0 )
        return 205;
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j, threshold - 1), dp(i-1, j-1, threshold - 1), dp(i, j-1, threshold - 1) );
}

您可能会担心 dp(i-1, j-1) 会下降，但阈值使 i 和 j 保持接近，因此它计算解决方案 2 的子集。这是因为每次 i 和 j 变得更远时阈值都会递减分开。 dp(i-1, j-1, threshold)会使它与解决方案 2 相同(因此，这个稍微快一些)。

空间

这些解决方案将很快为您提供答案，但如果您也想要空间优化解决方案，替换它很容易str1[i]与 (i in Str1CriticalPoints) ? 1 : 0 ，使用哈希图。这将提供一个仍然非常快的最终解决方案(虽然会慢 10 倍)，并且还避免将长字符串保留在内存中(到可以在 Arduino 上运行的程度)。我不认为这是必要的。

请注意，原始解决方案不使用 10^10 空间。您提到“更好，小于 10^10 空间”，暗示 10^10 空间是可以接受的。不幸的是，即使有足够的 RAM，迭代该空间也需要 10^10 时间，这绝对是 Not Acceptable 。我的解决方案都没有使用 10^10 空间:只有 2 * 10^5 来保存字符串 - 如上所述可以避免。 10^10 Bytes 10 GB 供引用。

编辑:正如 maniek 笔记，您只需要检查 abs(i - j) > 105 ，因为剩余 100 次插入需要等同于 i和 j会将操作数拉到 200 以上。