Was ist der effizienteste Weg, um übereinstimmende Sequenzen von Zellen in zwei (oder mehr) Arrays zu finden?

Question

Beispiel 1

Lassen Sie uns sagen, ich habe zwei Arrays:

('n','v','a','n','i','n','n','v','a','n') 
('a','n','n','n','v','a','n','v','n') 

Und ich möchte alle die passenden Sequenzen zwischen den beiden (vielleicht über zwei Zellen lang oder so), die nicht Unter sind finden Übereinstimmungen mit anderen längeren Übereinstimmungen. Hier ist, was ich als matches:

('n','n','v','a','n') = Position 5 in der Anordnung 1 und die Position 3 in der Matrix 2

Array 1: ('n', 'V', 'a', 'n', 'i ''n', 'n', 'V', 'a', 'n')

Array 2: ('a', 'n', 'n', 'n',' v‘, 'a', 'n', 'V', 'n')

Beispiel 2

Hier

haben wir mehr als eine Sequenz, aber sie sind kürzer, wie folgt:

('a','n','i','n') = Position 2 in arraay 1 und die Position 0 in der Matrix 2

('v','i','n') = Position 7 in der Anordnung 1 und die Position 5 in der Matrix 2

Array 1: ('n', 'v', 'a', 'n', 'i', 'n', 'a', 'V', 'i', 'n')

Array 2: ('a', 'n', 'i', 'n', 'p', 'v', 'i', 'n', 'v', 'n')

Zusammenfassung

Es gibt mehr als einen Treffer in beiden Beispielen, aber sie alle existieren innerhalb der größeren Spiele in mindestens eines der Arrays.

Also was ist der effizienteste (eine Balance aus wenig Speicher und hoher Geschwindigkeit, denke mobile Geräte) Code, der dies erreichen könnte? JavaScript-Codebeispiele wären großartig!

Answer 1

Hier ist mein JavaScript-Versuch auf der allgemeinen LCS, O(mn) Zeit und Raum, Version. Da wir Zeile für Zeile gehen, könnte der Speicherplatz reduziert werden, indem nur zwei Zeilen wiederverwendet werden, wobei die zweite Kopie nach der ersten Kopie kopiert wird.

var example1 = [['n','v','a','n','i','n','n','v','a','n'] 
       ,['a','n','n','n','v','a','n','v','n']], 

    example2 = [['n','v','a','n','i','n','n','v','i','n'] 
       ,['a','n','i','n','v','i','n','v','n']]; 

function f(as){ 
    var M = new Array(as[0].length), 
     result = []; 

    for (var i=0; i<as[0].length; i++){ 
    M[i] = new Array(as[1].length).fill(0); 

    for (var j=0; j<as[1].length; j++){ 
     if (as[0][i] == as[1][j]){ 
     M[i][j] = M[i-1] && M[j-1] ? 1 + M[i-1][j-1] : 1; 
     } 
     if ((i == as[0].length - 1 || j == as[1].length - 1) && M[i][j] > 2){ 
     result.push([i - M[i][j] + 1,j - M[i][j] + 1,M[i][j]]); 
     } else if (i > 1 && j > 1 && M[i][j] < M[i-1][j-1] && M[i-1][j-1] > 2){ 
     result.push([i - M[i-1][j-1],j - M[i-1][j-1],M[i-1][j-1]]); 
     } 
    } 
    } 

    return result; 
} 

console.log(JSON.stringify(f(example2))); // [[2,0,4],[6,3,4]] 

Answer 2

Hier ist ein O (n) O (n + k) Lösung für zwei Strings A und B deren Längen Summe n ist, und welche k solche maximale Anpassungsstrings:

1. bauen ein generalised suffix tree on Ihre zwei Strings A und B. (Dies ist nur ein gewöhnlicher Suffixbaum auf der einzelnen Zeichenkette A$B#, wobei $ und # einzelne Zeichen sind, die nirgendwo in A oder B erscheinen.) Dies kann in O (n) Zeit unter Verwendung von z. Ukkonens Algorithmus.
2. Durchführen einer von unten nach oben DFS durch diesen Baum, der an jedem Knoten zwei Dinge tut:
   • bestimmt und Aufzeichnungen, ob ein Blatt auf dem Suffix A unterhalb dieses Knotens entspricht, ist, und ob es Blatt, das einem Suffix von B unter diesem Knoten entspricht. (Übung: Beantworten dieser Frage für ein Blatt?)
   • Wenn Blätter beider Arten vorhanden sind, und gilt dies nicht auch für alle untergeordneten Knoten, und melden Sie dann die diesem Knoten entsprechende Teilzeichenfolge als Lösung an. (Wenn die Bedingung auch für einiges Kind hält, dann die Teilkette auf diesen Knoten entspricht, ist ein Teil der Teilkette auf dieses Kind entspricht, und Sie wollen nur maximal Strings.)

Dies wird auch bequem arbeiten für kleinere Zahlen> = 3 von Strings: Berechnen und speichern Sie die Menge der Eingabezeichenfolgen, die Blätter unter dem aktuellen Knoten haben, und "Feuer", wenn diese Menge voll wird.

Answer 3

Wenn die beiden Arrays haben Längen m und n, ich glaube nicht, dass Sie möglicherweise besser als O(mn) im allgemeinen Fall tun können. Angenommen, Sie haben Arrays mit wechselnden a s aber ansonsten deutliche Zeichen, wie diese

[a, b, a, c, a, d, a, e, a, f, a, g] 
[a, h, a, i, a, j, a, k, a, l, a, m] 

Die Anzahl der Spiele (m/2)*(n/2) ist. Wenn Sie sie alle finden möchten, kann Ihr Algorithmus bestenfalls O(mn) sein. Sie können es in O(mn) Zeit wie folgt tun: Stellen Sie sich eine Reihe hinter der anderen, wie dieses Gleiten:

[a, b, c, d, e] 
      [f, g, h, i, j] 

    [a, b, c, d, e] 
      [f, g, h, i, j] 

     [a, b, c, d, e] 
      [f, g, h, i, j] 

        ... 
         [a, b, c, d, e] 
      [f, g, h, i, j] 

Es gibt m + n - 1 möglichen Positionen. Für jede Position müssen Sie über die Paare von ausgerichteten Zeichen iterieren (es gibt im schlimmsten Fall min(m, n) dieser Paare) und die längsten Ketten übereinstimmender Zeichen finden. Das hat Zeit Komplexität

O((m + n) * min(m, n)) = O(mn) 

Diese Lösung hat den Nachteil, dass die einzige wirklich auf die Länge der Arrays, nicht auf den Inhalt genommen Zeit abhängt. Zum Beispiel dauert es immer noch O(nm) Zeit, auch wenn die Arrays gleich sind (wenn es eindeutig nur O(n) Zeit dauert, um dies zu überprüfen und die eine Antwort zurückzugeben). Wie in der anderen Antwort angegeben, gibt es viel klügere Lösungen, die viel weniger Zeit benötigen, wenn die Anzahl der übereinstimmenden Sequenzen gering ist.