python - Encontrando patrones en la lista.

algorithm performance

Question

Actualmente estoy buscando una forma de encontrar patrones en una lista de enteros, pero el método que voy a usar sería aplicable a cadenas y otras listas con diferentes elementos, por supuesto. Ahora déjame explicarte lo que estoy buscando.

Quiero encontrar el patrón de repetición más largo en una lista de enteros. Por ejemplo,

[1, 2, 3, 4, 1, 2, 3]
# This list would give 1, 2, 3

Los patrones superpuestos deben ser descartados. ( No seguro )

[1, 1, 1, 1, 1]
# Should give 1, 1  Not 1, 1, 1, 1

Esto es lo que no me ayudó.

Encontrar patrones en una lista (No entendí la lógica detrás de la primera respuesta, muy poca explicación. Y la segunda respuesta resuelve el problema solo si el patrón se conoce antes de resolver).

Encontrar un patrón de enteros en una lista (se da un patrón y se desea el número de ocurrencias. Diferente de mi pregunta).

El problema de subsecuencia común más largo (la mayoría de las personas se ocuparon de este problema, sin embargo, no es cercano al mío. Necesito elementos consecutivos mientras busco un patrón. Sin embargo, en este caso, los elementos separados también se consideran subsecuencias).

Aquí lo que intenté.

def pattern(seq):
    n = len(seq)
    c = defaultdict(int) # Counts of each subsequence
    for i in xrange(n):
        for j in xrange(i + 1, min(n, n / 2 + i)): 
            # Used n / 2 because I figured if a pattern is being searched
            # It cant be longer that the half of the list.
            c[tuple(seq[i:j])] += 1      
    return c

Como ves, encuentra todas las sublistas y busca repeticiones. Encontré este enfoque un poco ingenuo (e ineficiente) y necesito una forma mejor. Por favor, ayúdame. Gracias por adelantado.

Nota 1: la lista está predeterminada, pero debido a la falla de mis algoritmos, solo puedo revisar algunas partes de la lista antes de congelar la computadora. Por lo tanto, el patrón que estoy tratando de encontrar puede ser mucho más largo que la mitad de la lista de búsqueda, incluso puede ser más largo que la propia lista de búsqueda porque estoy buscando solo una parte de la lista original. Si presenta un método mejor que Estoy usando, puedo buscar una parte más grande de la lista original para tener una mejor oportunidad de encontrar el patrón. (Si hay uno.)

Nota 2: Esta es una parte de la lista si desea probarlo usted mismo. Realmente parece que hay un patrón, pero no puedo estar seguro antes de probarlo con un código confiable. Lista de muestra

Nota 3: Me acerco a esto como un problema grave de la minería de datos. Y trataré de aprender si haces una explicación larga. Esto se siente como un problema mucho más importante que la LCS, sin embargo, la LCS es mucho más popular: D Este método que estoy tratando de encontrar es como los métodos que usan los científicos para encontrar patrones de ADN.

Answer 1

El código

Ignorando el requisito "sin superposición", aquí está el código que utilicé:

def pattern(seq):
        storage = {}
        for length in range(1,len(seq)/2+1):
                valid_strings = {}
                for start in range(0,len(seq)-length+1):
                        valid_strings[start] = tuple(seq[start:start+length])
                candidates = set(valid_strings.values())
                if len(candidates) != len(valid_strings.values()):
                        print "Pattern found for " + str(length)
                        storage = valid_strings
                else:
                        print "No pattern found for " + str(length)
                        return set(filter(lambda x: storage.values().count(x) > 1, storage.values()))
        return storage

Usando eso, encontré 8 patrones distintos de longitud 303 en su conjunto de datos. El programa se ejecutó bastante rápido, también.

Versión de pseudocódigo

define patterns(sequence):
    list_of_substrings = {}
    for each valid length:  ### i.e. lengths from 1 to half the list''s length
        generate a dictionary my_dict of all sub-lists of size length
        if there are repeats:
            list_of_substrings = my_dict
        else:
            return all repeated values in list_of_substrings
    return list_of_substrings  #### returns {} when there are no patterns

Answer 2

Tengo una respuesta. Funciona. (sin superposición) pero es para python3

      def get_pattern(seq):
        seq2=seq
        outs={}
        l=0
        r=0
        c=None
        for end in range(len(seq2)+1):
          for start in range(end):
            word=chr(1).join(seq2[start:end])
            if not word in outs:
              outs[word]=1
            else:
              outs[word]+=1
        for item in outs:
          if outs[item]>r or (len(item)>l and outs[item]>1):
            l=len(item)
            r=outs[item]
            c=item
        return c.split(chr(1))