是否存在稀疏编辑距离算法？

Question

假设你有两个长度为100,000的字符串,包含0和1.您可以在大约10 ^ 10次操作中计算其编辑距离.

如果每个字符串只有100个,其余的都是零,那么我可以用100个整数表示每个字符串,说明它们的位置.

使用这种稀疏表示是否有更快的算法来计算编辑距离？更好的是算法也使用100 ^ 2空间而不是10 ^ 10空间.

为了给测试一些东西,考虑这两个字符串,每个字符串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检查一下.完成,phew.

你可以通过注意在最坏的情况下你将击中所有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,使用HashMap中.这将提供一个仍然非常快的最终解决方案(虽然速度会慢10倍),并且还避免将长字符串保留在内存中(直到它可以在Arduino上运行).我不认为这是必要的.

需要注意的是原来的解决方案并没有使用10 ^ 10的空间.你提到"甚至更好,小于10 ^ 10的空间",暗示10 ^ 10的空间是可以接受的.不幸的是,即使有足够的RAM,迭代虽然该空间需要10 ^ 10的时间,这绝对是不可接受的.我的解决方案都没有使用10 ^ 10空间:只有2*10 ^ 5来保持字符串 - 如上所述,这可以避免.10 ^ 10字节,10 GB供参考.

编辑:正如maniek所说,你只需要检查abs(i - j) > 105,因为剩下的100个插入需要等同i,j并将操作次数拉到200以上.