Algorithmen: Interessante diffing algorithm

Question

Dies kam in einer realen Situation, und ich dachte, ich würde es teilen, da es zu einigen interessanten Lösungen führen könnte. Im Wesentlichen muss der Algorithmus zwei Listen unterscheiden, aber lassen Sie mich eine genauere Definition des Problems geben.

mathematische Formulierung

Angenommen, Sie zwei Listen haben, L und R von denen jeder S Elemente aus irgendeinem Grunde liegenden Alphabet enthalten. Darüber hinaus haben diese Listen die Eigenschaft, dass die gemeinsamen Elemente, die sie erscheinen, um haben: das heißt, wenn L[i] = R[i*] und L[j] = R[j*] und i < j dann i * < j *. Die Listen müssen überhaupt keine gemeinsamen Elemente haben, und eines oder beide können leer sein. [Erläuterung: Sie dürfen keine Wiederholungen von Elementen annehmen.]

Das Problem ist es, eine Art „diff“ der Listen zu erzeugen, die als neue Liste geordneter Paare betrachtet werden können (x,y) wo x von L und y ist aus R, mit den folgenden Eigenschaften:

1. Wenn x in beiden Listen angezeigt wird, erscheint (x,x) im Ergebnis.
2. Wenn x in L, aber nicht in R erscheint, dann erscheint (x,NULL) im Ergebnis.
3. Wenn y in R, aber nicht in L angezeigt wird, erscheint (NULL,y) im Ergebnis.

und schließlich

• Die Ergebnisliste haben „die gleiche“ Bestellung als jedes der Eingangslisten: es Aktien, grob gesprochen, die gleiche Ordnungseigenschaft wie oben mit jedem der Listen einzeln (siehe Beispiel).

Beispiele

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)) 

Hat keine gute Algorithmen jemand dieses Problem zu lösen? Was ist die Komplexität?

Answer 1

Diffing sortierte Listen können in linearer Zeit durchgeführt werden, indem Sie beide Listen durchlaufen und den Abgleich durchführen. Ich werde versuchen, einige psuedo Java-Code in einem Update zu veröffentlichen.

Da wir den Sortieralgorithmus nicht kennen und keine Sortierung auf der Grundlage von Operatoren mit weniger als oder größer als bestimmen können, müssen wir die Listen ungeordnet betrachten. Da die Ergebnisse formatiert werden müssen, müssen Sie beide Listen scannen (zumindest bis Sie eine Übereinstimmung gefunden haben und dann können Sie ein Lesezeichen setzen und von dort aus erneut starten). Es wird immer noch O (n^2) -Leistung sein, oder genauer O (nm).

Answer 2

Dies ist ein ziemlich einfaches Problem, da Sie bereits eine geordnete Liste haben.

//this is very rough pseudocode 
stack aList; 
stack bList; 
List resultList; 
char aVal; 
char bVal; 

while(aList.Count > 0 || bList.Count > 0) 
{ 
    aVal = aList.Peek; //grab the top item in A 
    bVal = bList.Peek; //grab the top item in B 

    if(aVal < bVal || bVal == null) 
    { 
    resultList.Add(new Tuple(aList.Pop(), null))); 
    } 
    if(bVal < aVal || aVal == null) 
    { 
    resultList.Add(new Tuple(null, bList.Pop())); 
    } 
    else //equal 
    { 
    resultList.Add(new Tuple(aList.Pop(), bList.Pop())); 
    } 
} 

Hinweis ... dieser Code wird NICHT kompiliert. Es ist nur als Leitfaden gedacht.

EDIT am OP Basierend kommentiert

Wenn der Ordnungsalgorithmus nicht ausgesetzt ist, dann müssen die Listen ungeordnet angesehen werden. Wenn die Listen ungeordnet sind, hat der Algorithmus eine Zeitkomplexität von O (n^2), insbesondere O (nm), wobei n und m die Anzahl der Elemente in jeder Liste sind.

EDIT Algorithmus zur Lösung dieses

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

//pseudo code... will not compile 
//Note, this modifies aList and bList, so make copies. 
List aList; 
List bList; 
List resultList; 
var aVal; 
var bVal; 

while(aList.Count > 0) 
{ 
    aVal = aList.Pop(); 
    for(int bIndex = 0; bIndex < bList.Count; bIndex++) 
    { 
     bVal = bList.Peek(); 
     if(aVal.RelevantlyEquivalentTo(bVal) 
     { 
     //The bList items that come BEFORE the match, are definetly not in aList 
     for(int tempIndex = 0; tempIndex < bIndex; tempIndex++) 
     { 
      resultList.Add(new Tuple(null, bList.Pop())); 
     } 
     //This 'popped' item is the same as bVal right now 
     resultList.Add(new Tuple(aVal, bList.Pop())); 

     //Set aVal to null so it doesn't get added to resultList again 
     aVal = null; 

     //Break because it's guaranteed not to be in the rest of the list 
     break; 
     } 
    } 
    //No Matches 
    if(aVal != null) 
    { 
     resultList.Add(new Tuple(aVal, null)); 
    } 
} 
//aList is now empty, and all the items left in bList need to be added to result set 
while(bList.Count > 0) 
{ 
    resultList.Add(new Tuple(null, bList.Pop())); 
} 

die Ergebnismenge wird

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

Ergebnis ((a, null), (b sein, , b), (null, q), (c , c), (d, d), (null, g), (e, e))

Answer 3

Keine wirkliche greifbare Antwort, nur vage Intuition. Weil Sie den Ordnungsalgorithmus nicht kennen, nur dass die Daten in jeder Liste geordnet sind, klingt er vage wie die Algorithmen, die zum "Diff" von Dateien verwendet werden (z. B. in Beyond Compare) und Zeilenabfolgen zusammenpassen. Oder auch vage ähnlich wie Regexp-Algorithmen.

Es kann auch mehrere Lösungen geben. (egal, wenn es keine wiederholten Elemente gibt, die streng geordnet sind. Ich dachte zu viel in Richtung der Dateivergleiche)

Answer 4

Ich glaube nicht, dass Sie genug Informationen haben. Alles, was Sie behauptet haben, ist, dass Elemente, die übereinstimmen, in der gleichen Reihenfolge übereinstimmen, aber das erste übereinstimmende Paar zu finden, ist eine Operation O (nm), es sei denn, Sie haben eine andere Ordnung, die Sie bestimmen können.

Answer 5

Der schlechteste Fall, wie er definiert wurde und nur Gleichheit verwendet, muss O (n * m) sein. Betrachten wir die beiden folgenden Listen:

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

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

Angenommen, es gibt genau eine Übereinstimmung zwischen diesen beiden "geordneten" Listen. Es wird O (n * m) -Vergleiche erfordern, da kein Vergleich existiert, der später andere Vergleiche überflüssig macht.

Also, jeder Algorithmus, den Sie sich vorstellen, wird O (n * m) oder schlechter sein.

Answer 6

Es gibt eine Möglichkeit, dies in O (n) zu tun, wenn Sie eine Kopie einer der Listen in einer anderen Datenstruktur erstellen möchten. Dies ist ein klassisches Zeit/Raum-Kompromiss.

Erstellen Sie eine Hash-Map der Liste R, wobei der Schlüssel das Element und der Wert der ursprüngliche Index in das Array ist; In C++ könnten Sie unordered_map von tr1 oder boost verwenden.

Behalten Sie einen Index auf den unverarbeiteten Teil der Liste R, initialisiert auf das erste Element.

Für jedes Element in Liste L, überprüfen Sie die Hash-Zuordnung für eine Übereinstimmung in Liste R. Wenn Sie keine finden, Ausgabe (L-Wert, NULL). Wenn es eine Übereinstimmung gibt, holen Sie sich den entsprechenden Index aus der Hash-Map.Für jedes nicht verarbeitete Element in Liste R bis zum übereinstimmenden Index, Ausgabe (NULL, R-Wert). Für die Übereinstimmung, Ausgabe (Wert, Wert).

Wenn Sie das Ende der Liste L erreicht haben, gehen Sie durch die restlichen Elemente der Liste R und geben Sie (NULL, R-Wert) aus.

Bearbeiten: Hier ist die Lösung in Python. Für diejenigen, die sagen, diese Lösung hängt von der Existenz einer guten Hashing-Funktion ab - natürlich tut es dies. Das Original-Poster kann die Frage, ob es sich um ein Problem handelt, um weitere Einschränkungen erweitern, aber bis dahin werde ich eine optimistische Haltung einnehmen.

def FindMatches(listL, listR): 
    result=[] 
    lookupR={} 
    for i in range(0, len(listR)): 
     lookupR[listR[i]] = i 
    unprocessedR = 0 
    for left in listL: 
     if left in lookupR: 
      for right in listR[unprocessedR:lookupR[left]]: 
       result.append((None,right)) 
      result.append((left,left)) 
      unprocessedR = lookupR[left] + 1 
     else: 
      result.append((left,None)) 
    for right in listR[unprocessedR:]: 
     result.append((None,right)) 
    return result 

>>> FindMatches(('d'),('a','b','c')) 
[('d', None), (None, 'a'), (None, 'b'), (None, 'c')] 
>>> FindMatches(('a','b','c','d','e'),('b','q','c','d','g','e')) 
[('a', None), ('b', 'b'), (None, 'q'), ('c', 'c'), ('d', 'd'), (None, 'g'), ('e','e')] 

Answer 7

Dies ist genau wie Sequenzabgleich, können Sie den Needleman-Wunsch Algorithmus, es zu lösen verwenden. Der Link enthält den Code in Python. Stellen Sie nur sicher, dass Sie die Bewertung so festlegen, dass eine Nichtübereinstimmung negativ ist und eine Übereinstimmung positiv ist und eine Ausrichtung mit einem Leerzeichen beim Maximieren 0 ist. Der Algorithmus läuft in O (n * m) Zeit und Raum, aber die Raumkomplexität davon kann verbessert werden.

Bewertungsfunktion

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); 
    } 
} 

-Code

#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; 
} 

Beispiel 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 

Answer 8

verschiedene l.el SELECT ement, r.element
FROM LeftList l
OUTER RightList r
ON l.element = r.element
ORDER BY l.id JOIN, r.id

die ID jedes Elements annimmt, dessen Ordnungs . Und natürlich, dass Ihre Listen in einer relationalen Datenbank enthalten sind :)