Gibt es Algorithmen, um ein Feld nach bestimmten Mustern zu kategorisieren?

Question

Für ein einfaches Problem mit einer Array-Länge von zunächst 5 (in der Praxis könnte die Array-Länge 20 betragen )

Ich habe eine vordefiniert eine Reihe von Mustern, wie AAAAB, AAABA, BAABC, BCAAA, ... . Jedes Muster hat die gleiche Länge wie das Eingabefeld . Ich bräuchte eine Funktion, die ein beliebiges Integer-Array als Eingabe nimmt und Folgendes zurückgibt todos die Muster, auf die es passt. ( ein Array kann mehreren Mustern entsprechen ) so schnell wie möglich.

" A " bedeutet, dass in dem Muster alle Zahlen an den Positionen von A gleich sind. z.B. AAAAA bedeutet einfach, dass alle Zahlen gleich sind, {1, 1, 1, 1, 1} passt zu AAAAA .

" B "bedeutet, dass die Zahl an den Positionen B nicht gleich der Zahl an der Position A ist (d. h. ein Platzhalter für eine Zahl, die nicht A ist). Die durch B dargestellten Zahlen müssen nicht gleich sein. . z.B. ABBAA bedeutet, dass die Zahlen 1, 4 und 5 gleich, sagen wir, x sind und die Zahlen 2 und 3 nicht gleich x sind. {2, 3, 4, 2, 2} passt zu ABBAA .

" C " bedeutet, dass diese Position eine beliebige Zahl sein kann (d. h. ein Platzhalter für eine Zahl). {1, 2, 3, 5, 1} passt zu ACBBA , {1, 1, 3, 5, 1} passt auch ACBBA

Ich bin auf der Suche nach einem effizienten (in Bezug auf die Anzahl der Vergleiche) Algorithmus. Er muss nicht optimal sein, sollte aber nicht zu weit vom Optimum entfernt sein. Ich denke, es ist eine Art von Entscheidungsbaum...

Eine sehr einfache, aber ineffiziente Methode ist die folgende:

• Versuchen Sie, jedes Muster mit der Eingabe abzugleichen. say AABCA gegen {a, b, c, d, e} . Sie prüft, ob (a=b=e && a!=c) .

• Wenn die Anzahl der Muster n ist die Länge des Musters/Arrays m dann ist die Komplexität etwa O(n*m)

Aktualisierung:

Sie können gerne bessere Formulierungen für die Frage vorschlagen da ich nicht weiß, wie ich die Frage einfach und ohne Verwirrung verständlich machen kann.

Ein idealer Algorithmus müsste in irgendeiner Form vorbereitet werden, z. B. durch Umwandlung der Mustermenge in einen Entscheidungsbaum. Damit die Komplexität nach Die Vorverarbeitung kann für einige spezielle Mustersätze auf etwa O(log n * log m) reduziert werden (nur eine Vermutung).

Einige Zahlen, die vielleicht hilfreich sind: die vordefinierten Mustersätze sind ungefähr 30. Die Anzahl der Eingabefelder, die abgeglichen werden müssen, beträgt etwa 10 Millionen.

Zum Beispiel, wenn AAAAA y AAAAC befinden sich beide in dem vordefinierten Mustersatz. Wenn dann AAAAA Streichhölzer, AAAAC auch Spiele. Ich bin auf der Suche nach einem Algorithmus, der das erkennen kann.

Aktualisierung 2

Die Antwort von @Gareth Rees liefert eine O(n)-Lösung, allerdings unter der Annahme, dass es nicht viele " C "s. (sonst ist der Speicherplatz riesig und viele unnötige Vergleiche)

Ich würde mich auch über Ideen freuen, wie man mit Situationen umgehen kann, in denen es viele " C "s, sagen wir, für ein Eingabefeld der Länge 20, gibt es mindestens 10 " C "s für jedes vordefinierte Muster.

Answer 1

Hier ist eine Idee, die mit O(2 n ) Vorbereitung und Lagerung für O( n )-ähnliche Laufzeit. Wenn Ihre Arrays nicht länger sind als die Wortgröße Ihres Rechners (Sie deuten an, dass 20 eine typische Größe wäre), oder wenn es nicht zu viele Vorkommen von C in den Mustern, könnte diese Idee für Sie funktionieren. (Wenn keine dieser Bedingungen erfüllt ist, vermeiden Sie es!)

1. (Vorbereitender Schritt, einmalig) Erstellen eines Wörterbuchs d Zuordnung von Zahlen zu Mustersätzen. Für jedes Muster p und jede Teilmenge S des Vorkommens von C in diesem Muster, lassen Sie n die Zahl sein, die ein gesetztes Bit hat, das jedem A im Muster, und für jedes Vorkommen von C en S . hinzufügen p zur Menge der Muster d [ n ].

2. (Die übrigen Schritte werden jedes Mal durchgeführt, wenn ein neues Feld mit den Mustern abgeglichen werden muss). Ein Wörterbuch erstellen e Zuordnung von Zahlen zu Zahlen.

3. Sea j über die Indizes des Arrays laufen, und für jeden j :

   1. Sea i das sein j -te Ganzzahl im Array.

   2. Wenn i steht nicht im Wörterbuch e gesetzt e [ i ] = 0.

   3. Satz e [ i ] = e [ i ] + 2 j 1 wobei die Länge des Arrays angegeben wird.

4. Jetzt sind die Schlüssel von e sind die unterschiedlichen Zahlen i im Array, und der Wert e [ i ] hat ein gesetztes Bit, das jedem Vorkommen von i in dem Array. Für jeden Wert e [ i ], die im Wörterbuch zu finden ist d alle Muster aus der Menge d [ e [ i ]] mit dem Array übereinstimmen.

(Anmerkung: In der Praxis würde man die Bitsets andersherum aufbauen, und 2 j bei Schritt 3.3 anstelle von 2 j 1 aber ich habe den Algorithmus der Übersichtlichkeit halber so beschrieben).

Hier ist ein Beispiel. Angenommen, wir haben die Muster AABBA y ACBBA . In der Vorverarbeitungsphase AABBA wird zu der Zahl 25 (11001 in binärer Form), und ACBBA wird zu den Zahlen 25 (11001 in binärer Form) und 17 (10001 in binärer Form), für die beiden möglichen Teilmengen der Vorkommen von C in dem Muster. Also das Wörterbuch d sieht so aus:

• 17 { ACBBA }
• 25 { AABBA , ACBBA }

Nach der Verarbeitung des Arrays {1, 2, 3, 5, 1} erhalten wir e \= {1 17, 2 8, 3 4, 5 2}. Der Wert e [1] = 17 findet sich in d Diese Eingabe entspricht also dem Muster ACBBA .

Nach der Verarbeitung des Arrays {1, 1, 2, 3, 1} erhalten wir e \= {1 25, 2 4, 3 2}. Der Wert e [1] = 25 findet sich in d Diese Eingabe entspricht also den Mustern AABBA y ACBBA .

Answer 2

Ermittelt den Index des ersten A im Muster, ermittelt den Wert für diese Position und geht dann in einer Schleife durch die Positionen.

Um zu prüfen, ob das Array array mit dem Muster in der Zeichenkette pattern steht das Ergebnis in der booleschen match :

int index = pattern.IndexOf('A');
int value = array[index];
bool match = true;
for (int i = 0; i < array.Length; i++) {
  if (pattern[i] != 'C' && i != index) {
    if ((pattern[i] == 'A') != (array[i] == value)) {
      match = false;
      break;
    }
  }
}