La mejor manera de determinar si una secuencia se encuentra en otra secuencia en Python

Question

Esta es una generalización del problema "string contains substring" para (más) tipos arbitrarios.

Dada una secuencia (como una lista o tupla), ¿cuál es la mejor manera de determinar si hay otra secuencia dentro de ella? Como beneficio adicional, debe devolver el índice del elemento donde la subsecuencia comienza:

Ejemplo de uso (Secuencia de Secuencia):

>>> seq_in_seq([5,6], [4,'a',3,5,6]) 
3 
>>> seq_in_seq([5,7], [4,'a',3,5,6]) 
-1 # or None, or whatever 

Hasta el momento, sólo se basan en la fuerza bruta y parece lento, feo y torpe.

Answer 1

En segundo lugar, el algoritmo de Knuth-Morris-Pratt. Por cierto, su problema (y la solución KMP) es exactamente la receta 5.13 en Python Cookbook 2da edición. Puede encontrar el código relacionado al http://code.activestate.com/recipes/117214/

Se encuentra todo las subsecuencias correctas en una secuencia determinada, y debe ser utilizado como un iterador:

>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,6]): print s 
3 
>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,7]): print s 
(nothing) 

Answer 2

La fuerza bruta puede estar bien para patrones pequeños.

Para las más grandes, mira Aho-Corasick algorithm.

Answer 3

Lo mismo que señor cadena coincidente ... Knuth-Morris-Pratt string matching

Answer 4

>>> def seq_in_seq(subseq, seq): 
...  while subseq[0] in seq: 
...   index = seq.index(subseq[0]) 
...   if subseq == seq[index:index + len(subseq)]: 
...    return index 
...   else: 
...    seq = seq[index + 1:] 
...  else: 
...   return -1 
... 
>>> seq_in_seq([5,6], [4,'a',3,5,6]) 
3 
>>> seq_in_seq([5,7], [4,'a',3,5,6]) 
-1 

Lo siento, no soy un experto algoritmo, que es justo lo más rápido que mi mente puede pensar por el momento, al menos creo que se ve agradable (para mí) y me divertí codificándolo. ;-)

Lo más probable es que sea lo mismo que hace su enfoque de fuerza bruta.

Answer 5

Aquí es otra implementación KMP:

from itertools import tee 

def seq_in_seq(seq1,seq2): 
    ''' 
    Return the index where seq1 appears in seq2, or -1 if 
    seq1 is not in seq2, using the Knuth-Morris-Pratt algorithm 

    based heavily on code by Neale Pickett <neale@woozle.org> 
    found at: woozle.org/~neale/src/python/kmp.py 

    >>> seq_in_seq(range(3),range(5)) 
    0 
    >>> seq_in_seq(range(3)[-1:],range(5)) 
    2 
    >>>seq_in_seq(range(6),range(5)) 
    -1 
    ''' 
    def compute_prefix_function(p): 
     m = len(p) 
     pi = [0] * m 
     k = 0 
     for q in xrange(1, m): 
      while k > 0 and p[k] != p[q]: 
       k = pi[k - 1] 
      if p[k] == p[q]: 
       k = k + 1 
      pi[q] = k 
     return pi 

    t,p = list(tee(seq2)[0]), list(tee(seq1)[0]) 
    m,n = len(p),len(t) 
    pi = compute_prefix_function(p) 
    q = 0 
    for i in range(n): 
     while q > 0 and p[q] != t[i]: 
      q = pi[q - 1] 
     if p[q] == t[i]: 
      q = q + 1 
     if q == m: 
      return i - m + 1 
    return -1 

Answer 6

Aquí hay un enfoque de fuerza bruta O(n*m) (similar a @mcella's answer). Puede ser más rápido que la implementación del algoritmo Knuth-Morris-Pratt en Python puro O(n+m) (ver @Gregg Lind answer) para small secuencias de entrada.

#!/usr/bin/env python 
def index(subseq, seq): 
    """Return an index of `subseq`uence in the `seq`uence. 

    Or `-1` if `subseq` is not a subsequence of the `seq`. 

    The time complexity of the algorithm is O(n*m), where 

     n, m = len(seq), len(subseq) 

    >>> index([1,2], range(5)) 
    1 
    >>> index(range(1, 6), range(5)) 
    -1 
    >>> index(range(5), range(5)) 
    0 
    >>> index([1,2], [0, 1, 0, 1, 2]) 
    3 
    """ 
    i, n, m = -1, len(seq), len(subseq) 
    try: 
     while True: 
      i = seq.index(subseq[0], i + 1, n - m + 1) 
      if subseq == seq[i:i + m]: 
       return i 
    except ValueError: 
     return -1 

if __name__ == '__main__': 
    import doctest; doctest.testmod() 

Me pregunto qué tan grande es la pequeña en este caso?

Answer 7

Un enfoque simple: Convierta cadenas y confíe en la coincidencia de cadenas.

ejemplo usando listas de cadenas:

>>> f = ["foo", "bar", "baz"] 
>>> g = ["foo", "bar"] 
>>> ff = str(f).strip("[]") 
>>> gg = str(g).strip("[]") 
>>> gg in ff 
True 

ejemplo usando tuplas de cadenas:

>>> x = ("foo", "bar", "baz") 
>>> y = ("bar", "baz") 
>>> xx = str(x).strip("()") 
>>> yy = str(y).strip("()") 
>>> yy in xx 
True 

ejemplo usando listas de números:

>>> f = [1 , 2, 3, 4, 5, 6, 7] 
>>> g = [4, 5, 6] 
>>> ff = str(f).strip("[]") 
>>> gg = str(g).strip("[]") 
>>> gg in ff 
True 

Answer 8

otro enfoque, utilizando conjuntos:

set([5,6])== set([5,6])&set([4,'a',3,5,6]) 
True 

Answer 9

estoy un poco tarde a la fiesta, pero aquí es algo sencillo utilizando cuerdas:

>>> def seq_in_seq(sub, full): 
...  f = ''.join([repr(d) for d in full]).replace("'", "") 
...  s = ''.join([repr(d) for d in sub]).replace("'", "") 
...  #return f.find(s) #<-- not reliable for finding indices in all cases 
...  return s in f 
... 
>>> seq_in_seq([5,6], [4,'a',3,5,6]) 
True 
>>> seq_in_seq([5,7], [4,'a',3,5,6]) 
False 
>>> seq_in_seq([4,'abc',33], [4,'abc',33,5,6]) 
True 

Como señaló Ilya V. Schurov, la encontrar método en este caso no va devuelve los índices correctos con cadenas de caracteres múltiples o números de varios dígitos.