Wyszukiwanie sekwencji całkowitych

Mam dość skomplikowany problem wyszukiwania, który udało mi się zredukować do następującego opisu. Googlowałem, ale nie byłem w stanie znaleźć algorytmu, który wydaje się idealnie pasować do mojego problemu. W szczególności potrzeba pominięcia dowolnych liczb całkowitych. Może ktoś tutaj może mi coś wskazać?

Weźmy na przykład ciąg liczb całkowitych A (1 2 3 4)

Weź różne sekwencje liczb całkowitych i sprawdź, czy którakolwiek z nich pasuje do A w taki sposób.

1. A zawiera wszystkie liczby całkowite w testowanej sekwencji
2. Kolejność liczb całkowitych w badanej sekwencji jest taka sama w A
3. Nie dbamy o żadne liczby całkowite w A, które nie znajdują się w sekwencji testowej
4. Chcemy wszystkich pasujących sekwencji testowych, nie tylko pierwszej.

Przykład

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

B pasuje do A

C pasuje do A

D nie pasuje do A, ponieważ kolejność jest inna

E nie pasuje do A, ponieważ zawiera liczbę całkowitą spoza A

Mam nadzieję, że to wyjaśnienie jest wystarczająco jasne. Najlepsze, co udało mi się zrobić, to skonstruowanie drzewa sekwencji testowych i wykonanie iteracji nad A. Konieczność pominięcia liczb całkowitych prowadzi do wielu nieudanych ścieżek wyszukiwania.

Dzięki

Czytając kilka sugestii, uważam, że muszę wyjaśnić kilka kwestii, które pozostawiłem zbyt niejasne.

1. Powtarzane liczby są dozwolone, w rzeczywistości jest to dość ważne, ponieważ pozwala na dopasowanie jednej sekwencji testowej A na wiele sposobów

   A = (1234356), B = (236), dopasowania mogą wynosić -23 --- 6 lub -2--3-6

2. Oczekuję, że będzie bardzo duża liczba sekwencji testowych, przynajmniej w tysiącach, a sekwencja A będzie miała zwykle maksymalną długość może 20. 20. Po prostu próba dopasowania każdej sekwencji testowej jeden po drugim przez iterację staje się niezwykle nieefektywna.

Przepraszam, jeśli to nie było jasne.

Hmm, mogę wymyślić dwa możliwe algorytmy: liniowy skan sekwencji A lub zbudowanie słownika z ciągłym wyszukiwaniem indeksów.

Jeśli testujesz wiele potencjalnych podsekwencji B względem pojedynczej większej sekwencji A , sugerowałbym użycie wariantu ze słownikiem.

Skan liniowy

Opis

Utrzymujemy kursor dla sekwencji A . Następnie iterację wszystkich elementów w podciąg B . Dla każdego elementu przesuwamy kursor do przodu w A, aż znajdziemy pasujący element. Jeśli nie znaleziono pasującego elementu, B nie jest podsekwencją.

To zawsze działa w O (rozmiar sekw . ) .

Pseudo kod

Tryb rozkazujący:

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

Funkcjonalny styl:

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

Przykładowa implementacja (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;

Wyszukiwanie w słowniku

Opis

Mapujemy elementy sekwencji A na ich indeksy. Następnie wyszukujemy odpowiednie indeksy dla każdego elementu w B , pomijamy te, które są zbyt małe, i wybieramy najmniejszy możliwy indeks jako dolny limit. Gdy nie znaleziono żadnych wskaźników, B nie jest podsekwencją.

Działa w coś takiego jak O (rozmiar podsekcji · k) , gdzie k opisuje liczbę zduplikowanych liczb seq. Plus narzut O (rozmiar sek.)

Zaletą tego rozwiązania jest to, że decyzja negatywna może być podjęta znacznie szybciej (aż do stałego czasu), po zapłaceniu kosztów ogólnych związanych z budowaniem tabeli odnośników.

Pseudo kod:

Tryb rozkazujący:

# 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

Funkcjonalny styl:

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

Przykładowa implementacja (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;

Wariant wyszukiwania w słowniku: Kodowanie jako skończona maszyna stanowa

Opis

Możemy jeszcze bardziej zmniejszyć złożoność algorytmiczną do O (rozmiar podsekw.), Jeśli wymienimy więcej pamięci. Zamiast mapować elementy na ich indeksy, tworzymy wykres, w którym każdy węzeł reprezentuje element w jego indeksie. Krawędzie pokazują możliwe przejścia, np. Sekwencja a, b, abędzie miała krawędzie a@1 → b@2, a@1 → a@3, b@2 → a@3. Ten wykres jest równoważny skończonej maszynie stanów.

Podczas wyszukiwania utrzymujemy kursor, który początkowo jest pierwszym węzłem drzewa. Następnie spacer krawędzi dla każdego elementu w podmenu B . Jeśli taka krawędź nie istnieje, B nie jest listą podrzędną. Jeśli po wszystkich elementach kursor zawiera prawidłowy węzeł, wówczas B jest listą podrzędną.

Pseudo kod

Tryb rozkazujący:

# 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

Funkcjonalny styl:

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

Przykładowa implementacja (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;

Oto praktyczne podejście, które pozwala uniknąć „ciężkiej pracy” związanej z implementacją własnego algorytmu, a także pozwala „wymyślić koło”: użyj problemu z wyrażeniem regularnym .

Wystarczy umieścić wszystkie liczby A w ciągu, a wszystkie liczby B w ciągu oddzielone wyrażeniem regularnym (.*). Dodaj ^postać na początku i $na końcu. Następnie pozwól swojej ulubionej wyszukiwarce wyrażeń regularnych wyszukać wszystkie dopasowania. Na przykład kiedy

A = (1234356), B = (236)

utwórz reg exp dla B jak ^(.*)2(.*)3(.*)6(.*)$. Teraz uruchom globalne wyszukiwanie wyrażeń regularnych. Aby dowiedzieć się, w których pozycjach w A twoja podsekwencja pasuje, po prostu sprawdź długość pierwszych 3 podtekstów.

Jeśli zakres liczb całkowitych zawiera się w przedziale od 0 do 9, możesz najpierw rozważyć kodowanie pojedynczymi literami, aby to zadziałało, lub musisz dostosować pomysł za pomocą znaku separacji.

Oczywiście, szybkość tego podejścia będzie w dużym stopniu zależeć od prędkości używanego silnika reg exp, ale dostępne są wysoce zoptymalizowane silniki i myślę, że ciężko będzie wdrożyć szybszy algorytm „po wyjęciu z pudełka” .

Ten algorytm powinien być dość wydajny, jeśli uzyskanie długości i iteracja sekwencji jest wydajna.

1. Porównaj długość obu sekwencji. Przechowuj dłużej sequencei krócej wsubsequence
2. Zacznij od początku obu sekwencji i zapętlaj do końca sequence.
   1. Czy liczba w bieżącej pozycji jest sequencerówna liczbie w bieżącej pozycjisubsequence
   2. Jeśli tak, przesuń obie pozycje o jedną pozycję dalej
   3. Jeśli nie, przesuń tylko o sequencejedną pozycję dalej
3. Czy pozycja subsequencena końcusequence
4. Jeśli tak, dwie sekwencje są zgodne
5. Jeśli nie, dwie sekwencje się nie zgadzają