Buscando secuencias enteras

Tengo un problema de búsqueda bastante complejo que he logrado reducir a la siguiente descripción. He estado buscando en Google pero no he podido encontrar un algoritmo que parezca encajar perfectamente con mi problema. En particular, la necesidad de omitir enteros arbitrarios. ¿Quizás alguien aquí puede señalarme algo?

Tome una secuencia de enteros A, por ejemplo (1 2 3 4)

Tome varias secuencias de enteros y pruebe si alguno de ellos coincide con A tal que.

1. A contiene todos los enteros en la secuencia probada
2. El orden de los enteros en la secuencia probada es el mismo en A
3. No nos interesan los enteros en A que no están en la secuencia de prueba
4. Queremos todas las secuencias de prueba coincidentes, no solo la primera.

Un ejemplo

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

B coincide con A

C coincide con A

D no coincide con A ya que el orden es diferente

E no coincide con A ya que contiene un número entero que no está en A

Espero que esta explicación sea lo suficientemente clara. Lo mejor que he logrado hacer es construir un árbol de las secuencias de prueba e iterar sobre A. La necesidad de poder omitir enteros conduce a muchas rutas de búsqueda sin éxito.

Gracias

Al leer algunas sugerencias, siento que tengo que aclarar un par de puntos que dejé demasiado vagos.

1. Se permiten números repetidos, de hecho, esto es bastante importante ya que permite que una sola secuencia de prueba coincida con A en varias formas

   A = (1234356), B = (236), las coincidencias pueden ser -23 --- 6 o -2--3-6

2. Espero que haya una gran cantidad de secuencias de prueba, al menos en miles y la secuencia A tenderá a tener una longitud máxima de quizás 20. Por lo tanto, simplemente tratar de hacer coincidir cada secuencia de prueba una por una iterando se vuelve extremadamente ineficiente.

Lo siento si esto no estaba claro.

Hmm, puedo pensar en dos posibles algoritmos: un escaneo lineal a través de la secuencia A , o la construcción de un diccionario con búsqueda constante de los índices en el tiempo.

Si está probando muchas subsecuencias potenciales B contra una sola secuencia más grande A , le sugiero que use la variante con el diccionario.

Escaneo lineal

Descripción

Mantenemos un cursor para la secuencia A . Entonces iterar a través de todos los elementos de la subsecuencia B . Para cada elemento, movemos el cursor hacia adelante en A hasta encontrar un elemento coincidente. Si no se encontró ningún elemento coincidente, entonces B no es una subsecuencia.

Esto siempre se ejecuta en O (seq.size) .

Pseudocódigo

Estilo imperativo:

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

Estilo funcional:

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

Implementación de ejemplo (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;

Búsqueda de diccionario

Descripción

Mapeamos los ítems de la secuencia A a sus índices. Luego buscamos índices adecuados para cada elemento en B , omitimos los índices que son demasiado pequeños y seleccionamos el índice más pequeño posible como límite inferior. Cuando no se encuentran índices, entonces B no es una subsecuencia.

Se ejecuta en algo como O (subseq.size · k) , donde k describe cuántos números duplicados hay seq. Más un O (tamaño seq.) sobrecarga

La ventaja de esta solución es que se puede llegar a una decisión negativa mucho más rápido (hasta el tiempo constante), una vez que haya pagado los gastos generales de la creación de la tabla de búsqueda.

Pseudocódigo:

Estilo imperativo:

# 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

Estilo funcional:

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

Implementación de ejemplo (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;

Variante de búsqueda de diccionario: codificación como máquina de estados finitos

Descripción

Podemos reducir aún más la complejidad algorítmica hasta O (tamaño subsecuente) si intercambiamos más memoria. En lugar de asignar elementos a sus índices, creamos un gráfico donde cada nodo representa un elemento en su índice. Los bordes muestran posibles transiciones, por ejemplo, la secuencia a, b, atendría los bordesa@1 → b@2, a@1 → a@3, b@2 → a@3 . Este gráfico es equivalente a una máquina de estados finitos.

Durante la búsqueda, mantenemos un cursor que inicialmente es el primer nodo del árbol. Luego caminamos el borde de cada elemento de la lista secundaria B . Si no existe tal borde, entonces B no es una sublista. Si después de todos los elementos el cursor contiene un nodo válido, entonces B es una sublista.

Pseudocódigo

Estilo imperativo:

# 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

Estilo funcional:

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

Implementación de ejemplo (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;

Aquí hay un enfoque práctico que evita "el trabajo duro" de implementar su propio algoritmo y también evita "reinventar la rueda": utilice una expresión regular motor de para el problema.

Simplemente coloque todos los números de A en una cadena y todos los números de B en una cadena separados por la expresión regular (.*). Agregue un ^personaje al principio y$ al final. Luego, deje que su motor de expresiones regulares favorito busque todas las coincidencias. Por ejemplo, cuando

A = (1234356), B = (236)

crear un registro exp para B como ^(.*)2(.*)3(.*)6(.*)$ . Ahora ejecuta una búsqueda global de expresiones regulares. Para averiguar en qué posiciones en A coinciden sus subsecuencias, simplemente verifique la longitud de los primeros 3 subcoincidencias.

Si su rango de enteros deja de 0 a 9, puede considerar codificarlos primero con letras simples para que esto funcione, o debe adaptar la idea usando un carácter de separación.

Por supuesto, la velocidad de ese enfoque dependerá mucho de la velocidad del motor de registro que esté utilizando, pero hay motores altamente optimizados disponibles, y supongo que será difícil implementar un algoritmo más rápido "listo para usar" .

Este algoritmo debería ser bastante eficiente si obtener la longitud e iterar la secuencia es eficiente.

1. Compara la longitud de ambas secuencias. Almacene el más largo sequencey el más corto ensubsequence
2. Comience al principio de ambas secuencias y repita hasta el final de sequence.
   1. Es el número en la posición actual sequenceigual al número en la posición actual desubsequence
   2. En caso afirmativo, mueva ambas posiciones una más
   3. Si no, mueva solo la posición de sequence uno más
3. Es la posición de subsequenceal final de lasequence
4. En caso afirmativo, las dos secuencias coinciden
5. Si no, las dos secuencias no coinciden