algorithm - 动态编程测验或比较两个文本 block

Question

任务定义:

我尝试编写自己的 diff util。我想实现内联搜索。

表示我有两段文字。我必须将第一段 (p1) 中的字符串限制为第二段 (p2) 中的字符串，以使限制字符串中的常用词总和最大。

重要的一点是，你不能替换字符串:我的意思是如果你将 p1[i] 限制为 p2[j]，那么如果 k < i，你就不能将 p1[k] 限制为 p2[v]和 v < j.

小例子:

输入:

你有两个段落:

"Very very very very"         "Very very very"
"bla bla bla"                 "Very very very very very"
"looks like a very dump text" "One more sentence"
"simple text"                 "looks like a peace of ..."
                              "quite simple"
                              "bla bla bla bla"

...和矩阵，其中 matrix[i][j] = 字符串 p1[i] 和 p2[j] 中的常用词数

3 4 0 0 0 0
0 0 0 0 0 3
0 0 0 3 0 0
0 0 0 0 1 0

输出:

你需要用下一种方式来限制它们:

----------------               "Very very very"
"Very very very very"          "Very very very very very"
"bla bla bla"                  ----------------
----------------               "One more sentence"
"looks like a very dump text"  "looks like a peace of ..."
"simple text"                  "quite simple"
----------------               "bla bla bla bla"

或者你可以形成下一个矩阵:

(具有约束的字符串的索引)

p1Indexes: [0, 2, 3]p2Indexes: [1, 3 ,4]

问题:

这个任务的有效算法是什么？

[非必读] 遇到的困难:

1. 如何将索引集合传递给下一次迭代:我的意思是您需要在每次迭代时复制所有索引
2. 如果你想使用动态规划，你不仅需要存储一个公共(public)单词数，还需要为每个可能的迭代存储两个索引集合。

解决方案:

public void genConditionLCS() {
    int i = -1;
    int j = -1;
    while (true) {
        int[] indexes = nextIndexes(i+1, j+1);
        i = indexes[0];
        j = indexes[1];
        if (i == -1 || j == -1) break;
        firstParagraphIndexes.add(i); 
        secondParagraphIndexes.add(j);
    }
}
private int[] nextIndexes(int i, int j) {
    if ((i > (lcs.length-1)) || (j > (lcs[0].length-1)))
        return new int[] {-1, -1};
    int a = maxBenefit(i + 1, j);
    int b = maxBenefit(i, j + 1);
    int c = maxBenefit(i + 1, j + 1) + lcs[i][j];
    if ((a == 0) && (b == 0) && (c == 0))
        return new int[]{-1, -1};
    else if (a >= b && a >= c)
        return nextIndexes(i+1, j);
    else if (b >= a && b >= c)
        return nextIndexes(i, j+1);
    else //if (c >= a && c >= b)
        return new int[]{i, j};
}

private int maxBenefit(int i, int j) {
    if ((i > lcs.length - 1) || (j > lcs[0].length - 1)) return 0;
    int res = maxBenefit[i][j];
    if (res == -1) {
        int a = maxBenefit(i + 1, j);
        int b = maxBenefit(i, j + 1);
        int c = maxBenefit(i + 1, j + 1) + lcs[i][j];
        res = max(a, b, c);
        maxBenefit[i][j] = res;
    }
    return res;
}

Answer 1

给定数组 a[m] 和 b[n] 并给定成本函数:benefit(i, j) 计算元素 i 和 j 之间的公共(public)单词数，您的问题可以表述为 max_benefit(i, j) 这意味着 i 和 j 对齐/匹配，你需要找出剩余部分的最大 yield 和对齐，即: max(benefit(i + 1, j + 1 ) + max_benefit(i + 2, j + 2), benefit(i + 2, j + 1) + max_benefit(i + 3, j + 1), benefit(i + 3, j + 1) + max_benefit(i + 4, j + 1), ..., yield (i + 1, j + 2) + max_benefit(i + 2, j + 3), yield (i + 1, j + 3) + max_benefit(i + 1, j + 4), ...)

现在，当您第一次为任何一对索引计算 max_benefit 时，请存储结果，这样您就不需要重新计算它。 IE。在计算之前检查您是否有储值；如果不是，计算它并存储该值。

遇到困难:

1. 您可以将数组引用用作全局变量/类成员，或者您可以将数组引用作为 2 个额外参数传递:e。 G。 max_benefit(i, j, a, b) 和 benefit(i, j, a, b)。大多数语言都不会复制数组。
2. 查看此答案的主要部分，您只是递归地计算和存储值，这样您就不会重新计算。