Encontrar la secuencia repetitiva más larga en una cadena

Question

Necesito encontrar la secuencia más larga en una cadena con la advertencia de que la secuencia debe repetirse tres o más veces. Así, por ejemplo, si mi cadena es:

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

entonces me gustaría el valor "holamundo" para ser devueltos.

Yo sé de un par de maneras de lograr esto, pero el problema que estoy enfrentando es que la cadena real es absurdamente grande, así que estoy realmente en busca de un método que puede hacerlo en el momento oportuno.

Answer 1

Este problema es una variante del longest repeated substring problem y hay un algoritmo O (n) -time para resolverlo que usa suffix trees. La idea (como sugiere Wikipedia) es construir un árbol de sufijos (tiempo O (n)), anotar todos los nodos en el árbol con el número de descendientes (tiempo O (n) usando un DFS), y luego encontrar el árbol de sufijos (tiempo O (n)). nodo más profundo en el árbol con al menos tres descendientes (tiempo O (n) usando un DFS). Este algoritmo general toma tiempo O (n).

Dicho esto, los árboles de sufijo son muy difíciles de construir, por lo que es probable que desee encontrar una biblioteca de Python que implemente los árboles de sufijos antes de intentar esta implementación. Una búsqueda rápida en Google aparece this library, aunque no estoy seguro de si esta es una buena implementación.

Espero que esto ayude!

Answer 2

La primera idea que viene a la mente es la búsqueda con expresiones regulares cada vez más grandes:

import re 

text = 'fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' 
largest = '' 
i = 1 

while 1: 
    m = re.search("(" + ("\w" * i) + ").*\\1.*\\1", text) 
    if not m: 
     break 
    largest = m.group(1) 
    i += 1 

print largest # helloworld 

El código se ejecutó correctamente. La complejidad del tiempo parece ser al menos O (n^2).

Answer 3

Comencemos desde el final, cuente la frecuencia y deténgase tan pronto como aparezca el elemento más frecuente 3 o más veces.

from collections import Counter 
a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' 
times=3 
for n in range(1,len(a)/times+1)[::-1]: 
    substrings=[a[i:i+n] for i in range(len(a)-n+1)] 
    freqs=Counter(substrings) 
    if freqs.most_common(1)[0][1]>=3: 
     seq=freqs.most_common(1)[0][0] 
     break 
print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times) 

Resultado:

>>> sequence 'helloworld' of length 10 occurs 3 or more times 

Editar: si usted tiene la sensación de que está tratando con la entrada al azar y la subcadena común debe ser de pequeña longitud, es mejor empezar (si es necesario la velocidad) con pequeñas subseries y parar cuando no se puede encontrar ninguna que aparecen al menos 3 veces:

from collections import Counter 
a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' 
times=3 
for n in range(1,len(a)/times+1): 
    substrings=[a[i:i+n] for i in range(len(a)-n+1)] 
    freqs=Counter(substrings) 
    if freqs.most_common(1)[0][1]<3: 
     n-=1 
     break 
    else: 
     seq=freqs.most_common(1)[0][0] 
print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times) 

el mismo resultado anterior.

Answer 4

Use defaultdict para contar cada subcadena comenzando con cada posición en la cadena de entrada. El OP no estaba claro si las coincidencias superpuestas deberían o no deberían incluirse, este método de fuerza bruta las incluye.

from collections import defaultdict 

def getsubs(loc, s): 
    substr = s[loc:] 
    i = -1 
    while(substr): 
     yield substr 
     substr = s[loc:i] 
     i -= 1 

def longestRepetitiveSubstring(r, minocc=3): 
    occ = defaultdict(int) 
    # tally all occurrences of all substrings 
    for i in range(len(r)): 
     for sub in getsubs(i,r): 
      occ[sub] += 1 

    # filter out all substrings with fewer than minocc occurrences 
    occ_minocc = [k for k,v in occ.items() if v >= minocc] 

    if occ_minocc: 
     maxkey = max(occ_minocc, key=len) 
     return maxkey, occ[maxkey] 
    else: 
     raise ValueError("no repetitions of any substring of '%s' with %d or more occurrences" % (r,minocc)) 

impresiones:

('helloworld', 3) 

Answer 5

Si se invierte la cadena de entrada, luego alimentar a una expresión regular como (.+)(?:.*\1){2}
hay que darle la cadena más larga repitieron 3 veces.(Grupo de captura inversa 1 para la respuesta)

Editar:
Tengo que decir cancelar esta manera. Depende del primer partido. A menos que se pruebe contra una longitud de curr contra longitud máxima hasta el momento, en un ciclo iterativo, regex no funcionará para esto.