算法:有趣的差分算法

Question

这是在现实世界中出现的，我想我应该分享一下，因为它可能会带来一些有趣的解决方案。本质上，算法需要区分两个列表，但让我给出一个更严格的问题定义。

数学公式

假设您有两个列表，L和R，每个列表都包含来自底层字母表S的元素。此外，这些列表具有它们所显示的公共元素按顺序显示的属性:也就是说，如果是L[i] = R[i*]和L[j] = R[j*]，以及i < j，那么i* < j*。列表根本不需要任何公共元素，其中一个或两者都是空的。澄清:你可以假设没有重复的元素。

问题是生成一种列表的"diff“，它可以被视为有序对的新列表( (x,y) )，其中x来自L，y来自R，具有以下属性：

1. 如果x出现在两个列表中，那么(x,x)将出现在结果中。
2. 如果x出现在L中，但没有出现在R中，那么(x,NULL)就会出现在结果中。
3. 如果y出现在R中，但没有出现在L中，那么(NULL,y)就会出现在结果中。

最后

• 结果列表与每个输入列表具有“相同”排序:粗略地说，它与每个列表共享相同的排序属性(参见示例)。

示例

L = (d)
R = (a,b,c)
Result = ((NULL,d), (a,NULL), (b,NULL), (c,NULL))

L = (a,b,c,d,e)  
R = (b,q,c,d,g,e)
Result = ((a,NULL), (b,b), (NULL,q), (c,c), (d,d), (NULL,g), (e,e))

有人有什么好的算法来解决这个问题吗？复杂程度有多大？

Answer 1

最坏的情况，如定义的并且只使用相等，必须是O(n*m)。考虑以下两项清单：

A[] = {a，b，c，d，e，f，g}

B[] = {h，i，j，k，l，m，n}

假设这两个“有序”列表之间完全存在一个匹配。它将进行O(n*m)比较，因为不存在其他比较，因此以后不需要进行其他比较。

所以，你想出的任何算法都是O(n*m)，或者更糟。

Answer 2

Diffing有序列表可以通过遍历列表并在执行过程中进行匹配，在线性时间内完成。我将尝试在更新中发布一些psuedo Java代码。

由于我们不知道排序算法，并且不能根据小于或大于运算符来确定任何排序，所以我们必须考虑无序列表。此外，考虑到结果是如何格式化的，您将面临两个列表的扫描(至少在找到匹配之前，然后您可以在那里进行书签并重新开始)。它仍然是O(n^2)性能，或者更确切地说是O(nm)。

Answer 3

这就像序列对齐一样，您可以使用尼德曼-温施算法来解决它。该链接包括Python中的代码。只需确保设置得分，使失配为负值，匹配为正，与空白对齐时最大化为0。该算法在O(n * m)时间和空间上运行，但其空间复杂度有所提高。

评分函数

int score(char x, char y){
    if ((x == ' ') || (y == ' ')){
        return 0;
    }
    else if (x != y){
        return -1;
    }
    else if (x == y){
        return 1;
    }
    else{
        puts("Error!");
        exit(2);
    }
}

码

#include <stdio.h>
#include <stdbool.h>

int max(int a, int b, int c){
    bool ab, ac, bc;
    ab = (a > b);
    ac = (a > c);
    bc = (b > c);
    if (ab && ac){
        return a;
    }
    if (!ab && bc){
        return b;
    }
    if (!ac && !bc){
        return c;
    }
}

int score(char x, char y){
    if ((x == ' ') || (y == ' ')){
        return 0;
    }
    else if (x != y){
        return -1;
    }
    else if (x == y){
        return 1;
    }
    else{
        puts("Error!");
        exit(2);
    }
}


void print_table(int **table, char str1[], char str2[]){
    unsigned int i, j, len1, len2;
    len1 = strlen(str1) + 1;
    len2 = strlen(str2) + 1;
    for (j = 0; j < len2; j++){
        if (j != 0){
            printf("%3c", str2[j - 1]);
        }
        else{
            printf("%3c%3c", ' ', ' ');
        }
    }
    putchar('\n');
    for (i = 0; i < len1; i++){
        if (i != 0){
            printf("%3c", str1[i - 1]);
        }
        else{
            printf("%3c", ' ');
        }
        for (j = 0; j < len2; j++){
            printf("%3d", table[i][j]);
        }
        putchar('\n');
    }
}

int **optimal_global_alignment_table(char str1[], char str2[]){
    unsigned int len1, len2, i, j;
    int **table;
    len1 = strlen(str1) + 1;
    len2 = strlen(str2) + 1;
    table = malloc(sizeof(int*) * len1);
    for (i = 0; i < len1; i++){
        table[i] = calloc(len2, sizeof(int));
    }
    for (i = 0; i < len1; i++){
        table[i][0] += i * score(str1[i], ' ');
    }
    for (j = 0; j < len1; j++){
        table[0][j] += j * score(str1[j], ' ');
    }
    for (i = 1; i < len1; i++){
        for (j = 1; j < len2; j++){
            table[i][j] = max(
                table[i - 1][j - 1] + score(str1[i - 1], str2[j - 1]),
                table[i - 1][j] + score(str1[i - 1], ' '),
                table[i][j - 1] + score(' ', str2[j - 1])
            );
        }
    }
    return table;
}

void prefix_char(char ch, char str[]){
    int i;
    for (i = strlen(str); i >= 0; i--){
        str[i+1] = str[i];
    }   
    str[0] = ch;
}

void optimal_global_alignment(int **table, char str1[], char str2[]){
    unsigned int i, j;
    char *align1, *align2;
    i = strlen(str1);
    j = strlen(str2);
    align1 = malloc(sizeof(char) * (i * j));
    align2 = malloc(sizeof(char) * (i * j));
    align1[0] = align2[0] = '\0';
    while((i > 0) && (j > 0)){
        if (table[i][j] == (table[i - 1][j - 1] + score(str1[i - 1], str2[j - 1]))){
            prefix_char(str1[i - 1], align1);
            prefix_char(str2[j - 1], align2);
            i--;
            j--;
        }
        else if (table[i][j] == (table[i - 1][j] + score(str1[i-1], ' '))){
            prefix_char(str1[i - 1], align1);
            prefix_char('_', align2);
            i--;
        }
        else if (table[i][j] == (table[i][j - 1] + score(' ', str2[j - 1]))){
            prefix_char('_', align1);
            prefix_char(str2[j - 1], align2);
            j--;
        }
    }
    while (i > 0){
        prefix_char(str1[i - 1], align1);
        prefix_char('_', align2);
        i--;
    }
    while(j > 0){
        prefix_char('_', align1);
        prefix_char(str2[j - 1], align2);
        j--;
    }
    puts(align1);
    puts(align2);
}

int main(int argc, char * argv[]){
    int **table;
    if (argc == 3){
        table = optimal_global_alignment_table(argv[1], argv[2]);
        print_table(table, argv[1], argv[2]);
        optimal_global_alignment(table, argv[1], argv[2]);
    }
    else{
        puts("Reqires to string arguments!");
    }
    return 0;
}

样本IO

$ cc dynamic_programming.c && ./a.out aab bba
__aab
bb_a_
$ cc dynamic_programming.c && ./a.out d abc
___d
abc_
$ cc dynamic_programming.c && ./a.out abcde bqcdge
ab_cd_e
_bqcdge