buscando secuencias de enteros

14

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 ajustarse a mi problema de manera limpia. En particular, la necesidad de omitir enteros arbitrarios. Tal vez alguien aquí pueda indicarme 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 de tal manera 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 importa ningún número entero en A que no esté en la secuencia de prueba
  4. Queremos todas las secuencias de prueba coincidentes, no solo las primeras.

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 números enteros conduce a muchas rutas de búsqueda fallidas.

Gracias

Leyendo algunas sugerencias, siento que debo aclarar un par de puntos que dejé demasiado vagos.

  1. Se permiten números repetidos, de hecho, esto es muy importante ya que permite que una única secuencia de prueba coincida con A de varias maneras

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

  2. Espero que haya un número muy grande 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 tratando de hacer coincidir cada secuencia de prueba una por una la iteración se vuelve extremadamente ineficiente.

Lo siento si esto no estaba claro.

    
pregunta David Gibson 12.11.2013 - 13:30

3 respuestas

18

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

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

Exploración lineal

Descripción

Mantenemos un cursor para la secuencia A . Luego iteramos a través de todos los elementos en la subsecuencia B . Para cada elemento, movemos el cursor hacia adelante en A hasta que hayamos encontrado un elemento coincidente. Si no se encontró un elemento coincidente, 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 en el diccionario

Descripción

Asignamos los elementos 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, B no es una subsecuencia.

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

La ventaja de esta solución es que se puede llegar a una decisión negativa mucho más rápido (hasta un tiempo constante), una vez que haya pagado los gastos generales de la construcció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 del diccionario: codificación como máquina de estados finitos

Descripción

Podemos reducir aún más la complejidad algorítmica hasta O (subseq.size) 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, a tendría los bordes [email protected][email protected], [email protected][email protected], [email protected][email protected] . 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 en 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 lista secundaria.

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;
    
respondido por el amon 12.11.2013 - 14:37
6

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

Simplemente ponga todos los números de A en una cadena y todos los números de B en una cadena separada por la expresión regular (.*) . Agregue un carácter ^ al principio y $ al final. Entonces deja que tu motor de expresiones regulares favorito busque todas las coincidencias. Por ejemplo, cuando

A = (1234356), B = (236)

crea una exp. reg para B como ^(.*)2(.*)3(.*)6(.*)$ . Ahora ejecuta una búsqueda global de expresiones regulares. Para averiguar en qué posiciones de A coincide su subsecuencia, simplemente verifique la longitud de las primeras 3 subparecciones.

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

Por supuesto, la velocidad de ese enfoque dependerá en gran medida de la velocidad del motor reg exp que esté utilizando, pero hay motores altamente optimizados disponibles, y creo que será difícil implementar un algoritmo más rápido "fuera de la caja".

    
respondido por el Doc Brown 12.11.2013 - 17:46
0

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

  1. Compara la longitud de ambas secuencias. Almacene más tiempo en sequence y el más corto en subsequence
  2. Comience al principio de ambas secuencias y haga un bucle hasta el final de sequence .
    1. Es el número en la posición actual de sequence igual al número en la posición actual de subsequence
    2. En caso afirmativo, mueva ambas posiciones una más
    3. Si no, mueve solo la posición de sequence one
  3. Es la posición de subsequence al final de sequence
  4. Si es así, las dos secuencias coinciden
  5. Si no, las dos secuencias no coinciden
respondido por el MarcDefiant 12.11.2013 - 14:38

Lea otras preguntas en las etiquetas