Suche nach ganzzahligen Sequenzen

Ich habe ein ziemlich komplexes Suchproblem, das ich auf die folgende Beschreibung reduzieren konnte. Ich habe gegoogelt, aber keinen Algorithmus gefunden, der zu meinem Problem zu passen scheint. Insbesondere die Notwendigkeit, beliebige ganze Zahlen zu überspringen. Vielleicht kann mich hier jemand auf etwas hinweisen?

Nehmen Sie zum Beispiel eine Folge von ganzen Zahlen A (1 2 3 4)

Nehmen Sie verschiedene Folgen von ganzen Zahlen und testen Sie, ob eine davon mit A übereinstimmt.

1. A enthält alle Ganzzahlen in der getesteten Sequenz
2. Die Reihenfolge der ganzen Zahlen in der getesteten Sequenz ist in A gleich
3. Wir kümmern uns nicht um Ganzzahlen in A, die nicht in der Testsequenz enthalten sind
4. Wir wollen alle passenden Testsequenzen, nicht nur die ersten.

Ein Beispiel

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B entspricht A

C entspricht A

D stimmt nicht mit A überein, da die Reihenfolge unterschiedlich ist

E stimmt nicht mit A überein, da es eine Ganzzahl enthält, die nicht in A enthalten ist

Ich hoffe, dass diese Erklärung klar genug ist. Ich habe es am besten geschafft, einen Baum der Testsequenzen zu erstellen und über A zu iterieren. Das Erfordernis, Ganzzahlen überspringen zu können, führt zu vielen erfolglosen Suchpfaden.

Vielen Dank

Wenn ich einige Vorschläge lese, habe ich das Gefühl, dass ich ein paar Punkte klarstellen muss, die ich zu vage gelassen habe.

1. Wiederholte Zahlen sind zulässig, was in der Tat sehr wichtig ist, da eine einzelne Testsequenz auf mehrere Arten mit A übereinstimmen kann

   A = (1234356), B = (236), Übereinstimmungen könnten entweder -23 --- 6 oder -2--3-6 sein

2. Ich erwarte, dass es eine sehr große Anzahl von Testsequenzen gibt, mindestens zu Tausenden, und Sequenz A wird tendenziell eine maximale Länge von 20 haben. Daher wird es extrem ineffizient, einfach zu versuchen, jede Testsequenz einzeln durch Iterieren abzugleichen.

Entschuldigung, wenn das nicht klar war.

Hmm, ich kann mir zwei mögliche Algorithmen vorstellen: Einen linearen Scan durch die A- Sequenz oder das Erstellen eines Wörterbuchs mit einer zeitlich konstanten Suche der Indizes.

Wenn Sie viele mögliche Teilsequenzen B gegen eine einzelne größere Sequenz A testen , würde ich vorschlagen, dass Sie die Variante mit dem Wörterbuch verwenden.

Linearer Scan

Beschreibung

Wir pflegen einen Cursor für die Sequenz A . Dann wiederholen wir durch alle Elemente in der Subsequenz B . Für jeden Artikel bewegen wir den Cursor in A vorwärts, bis wir einen passenden Artikel gefunden haben. Wenn kein passendes Element gefunden wurde, ist B keine Untersequenz.

Dies läuft immer in O (seq.size) .

Pseudocode

Imperativer Stil:

def subsequence? seq, subseq:
  i = 0
  for item in subseq:
    i++ while i < seq.size and item != seq[i]
    return false if i == seq.size
  return true

Funktionsstil:

let rec subsequence? = function
| _ [] -> true
| [] _ -> false
| cursor::seq item::subseq ->
  if   cursor = item
  then subsequence? seq subseq
  else subsequence? seq item::subseq

Beispielimplementierung (Perl):

use strict; use warnings; use signatures; use Test::More;

sub is_subsequence_i ($seq, $subseq) {
  my $i = 0;
  for my $item (@$subseq) {
    $i++ while $i < @$seq and $item != $seq->[$i];
    return 0 if $i == @$seq;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  return 1 if @$subseq == 0;
  return 0 if @$seq == 0;
  my ($cursor, @seq) = @$seq;
  my ($item, @subseq) = @$subseq;
  return is_subsequence_f(\@seq, $cursor == $item ? \@subseq : $subseq);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Wörterbuch-Suche

Beschreibung

Wir ordnen die Elemente der Sequenz A ihren Indizes zu. Dann suchen wir geeignete Indizes für jedes Element in B , überspringen die zu kleinen Indizes und wählen den kleinstmöglichen Index als Untergrenze. Wenn keine Indizes gefunden werden, ist B keine Untersequenz.

Läuft in so etwas wie O (subseq.size · k) , wobei k beschreibt, wie viele doppelte Zahlen enthalten sind seq. Dazu ein O- Overhead (seq.size)

Der Vorteil dieser Lösung besteht darin, dass eine negative Entscheidung viel schneller (bis hin zu einer konstanten Zeit) getroffen werden kann, wenn Sie den Aufwand für die Erstellung der Nachschlagetabelle bezahlt haben.

Pseudocode:

Imperativer Stil:

# preparing the lookup table
dict = {}
for i, x in seq:
  if exists dict[x]:
    dict[x].append(i)
  else:
    dict[x] = [i]

def subsequence? subseq:
  min_index = -1
  for x in subseq:
    if indices = dict[x]:
      suitable_indices = indices.filter(_ > min_index)
      return false if suitable_indices.empty?
      min_index = suitable_indices[0]
    else:
      return false
  return true

Funktionsstil:

let subsequence? subseq =
  let rec subseq-loop = function
  | [] _ -> true
  | x::subseq min-index ->
    match (map (filter (_ > min-index)) data[x])
    | None -> false
    | Some([]) -> false
    | Some(new-min::_) -> subseq-loop subseq new-min
  in
    subseq-loop subseq -1

Beispielimplementierung (Perl):

use strict; use warnings; use signatures; use Test::More;

sub build_dict ($seq) {
  my %dict;
  while (my ($i, $x) = each @$seq) {
    push @{ $dict{$x} }, $i;
  }
  return \%dict;
}

sub is_subsequence_i ($seq, $subseq) {
  my $min_index = -1;
  my $dict = build_dict($seq);
  for my $x (@$subseq) {
    my $indices = $dict->{$x} or return 0;
    ($min_index) = grep { $_ > $min_index } @$indices or return 0;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  my $dict = build_dict($seq);
  use feature 'current_sub';
  return sub ($subseq, $min_index) {
    return 1 if @$subseq == 0;
    my ($x, @subseq) = @$subseq;
    my ($new_min) = grep { $_ > $min_index } @{ $dict->{$x} // [] } or return 0;
    __SUB__->(\@subseq, $new_min);
  }->($subseq, -1);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Dictionary-Lookup-Variante: Codierung als endliche Zustandsmaschine

Beschreibung

Wir können die algorithmische Komplexität weiter auf O (subseq.size) reduzieren, wenn wir mehr Speicher einsetzen. Anstatt Elemente ihren Indizes zuzuordnen, erstellen wir ein Diagramm, in dem jeder Knoten ein Element an seinem Index darstellt. Die Kanten zeigen mögliche Übergänge, zB hätte die Sequenz a, b, adie Kanten a@1 → b@2, a@1 → a@3, b@2 → a@3. Dieser Graph entspricht einer endlichen Zustandsmaschine.

Während der Suche pflegen wir einen Cursor, der anfangs der erste Knoten des Baums ist. Wir gehen dann die Kante für jedes Element in der Unterliste B . Wenn keine solche Kante existiert, ist B keine Unterliste. Wenn der Cursor nach allen Elementen einen gültigen Knoten enthält, ist B eine Unterliste.

Pseudocode

Imperativer Stil:

# preparing the graph
graph = {}
for x in seq.reverse:
  next_graph = graph.clone
  next_graph[x] = graph
  graph = next_graph

def subseq? subseq:
  cursor = graph
  for x in subseq:
    cursor = graph[x]
    return false if graph == null
  return true

Funktionsstil:

let subseq? subseq =
  let rec subseq-loop = function
  | [] _ -> true
  | x::subseq graph -> match (graph[x])
    | None -> false
    | Some(next-graph) -> subseq-loop subseq next-graph
  in
    subseq-loop subseq graph

Beispielimplementierung (Perl):

use strict; use warnings; use signatures; use Test::More;

sub build_graph ($seq) {
  my $graph = {};
  for (reverse @$seq) {
    $graph = { %$graph, $_ => $graph };
  }
  return $graph;
}

sub is_subsequence_i ($seq, $subseq) {
  my $cursor = build_graph($seq);
  for my $x (@$subseq) {
    $cursor = $cursor->{$x} or return 0;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  my $graph = build_graph($seq);
  use feature 'current_sub';
  return sub ($subseq, $graph) {
    return 1 if @$subseq == 0;
    my ($x, @subseq) = @$subseq;
    my $next_graph = $graph->{$x} or return 0;
    __SUB__->(\@subseq, $next_graph);
  }->($subseq, $graph);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Hier ist ein praktischer Ansatz, der "die harte Arbeit" des Implementierens Ihres eigenen Algorithmus vermeidet und auch "das Rad neu erfinden" vermeidet: Verwenden Sie eine reguläre Ausdrucksmaschine für das Problem.

Setzen Sie einfach alle Zahlen von A in eine Zeichenfolge und alle Zahlen von B in eine durch den regulären Ausdruck getrennte Zeichenfolge (.*). Fügen Sie ^am Anfang und $am Ende ein Zeichen hinzu . Lassen Sie dann Ihre Lieblingsmaschine für reguläre Ausdrücke nach allen Übereinstimmungen suchen. Zum Beispiel, wenn

A = (1234356), B = (236)

erstelle eine reg exp für B like ^(.*)2(.*)3(.*)6(.*)$. Führen Sie nun eine globale reguläre Suche durch. Um herauszufinden, an welchen Positionen in A Ihre Subsequenz übereinstimmt, überprüfen Sie einfach die Länge der ersten 3 Submatches.

Wenn Ihr ganzer Zahlenbereich von 0 bis 9 reicht, können Sie in Betracht ziehen, diese zuerst mit einzelnen Buchstaben zu codieren, damit dies funktioniert, oder Sie müssen die Idee mit einem Trennzeichen anpassen.

Natürlich hängt die Geschwindigkeit dieses Ansatzes stark von der Geschwindigkeit der von Ihnen verwendeten reg exp-Engine ab, aber es sind hochoptimierte Engines verfügbar, und ich denke, es wird schwierig sein, einen schnelleren Algorithmus "out of the box" zu implementieren. .

Dieser Algorithmus sollte sehr effizient sein, wenn die Länge und die Iteration der Sequenz effizient sind.

1. Vergleichen Sie die Länge beider Sequenzen. Je länger sequenceund je kürzer lagernsubsequence
2. Beginnen Sie am Anfang beider Sequenzen und wiederholen Sie die Schleife bis zum Ende von sequence.
   1. Ist die Zahl an der aktuellen Position sequencegleich der Zahl an der aktuellen Position vonsubsequence
   2. Wenn ja, verschieben Sie beide Positionen noch einmal
   3. Wenn nicht, verschieben Sie nur die Position sequenceeines weiteren
3. Ist die Position subsequenceam Ende dessequence
4. Wenn ja, stimmen die beiden Sequenzen überein
5. Wenn nicht, stimmen die beiden Sequenzen nicht überein