Estoy buscando un algoritmo (posiblemente implementado en Python) capaz de encontrar la secuencia más REPETITIVA en una cadena. Donde para REPETITIVO, me refiero a cualquier combinación de caracteres que se repite una y otra vez sin interrupción (repetición en tándem).
El algoritmo que estoy buscando no es el mismo que el de "encontrar la palabra más común" . De hecho, el bloque repetitivo no necesita ser la palabra más común (subcadena) en la cadena.
Por ejemplo:
s = 'asdfewfUBAUBAUBAUBAUBAasdkBAjnfBAenBAcs' > f(s) 'UBAUBAUBAUBAUBA' #the "most common word" algo would return 'BA'Desafortunadamente, no tengo idea de cómo abordar esto. Cualquier ayuda es bienvenida.
ACTUALIZAR
Un pequeño ejemplo adicional para aclarar que quiero que me devuelvan la secuencia con el mayor número de repeticiones, cualquiera que sea su componente básico.
g = 'some noisy spacer' s = g + 'AB'*5 + g + '_ABCDEF'*2 + g + 'AB'*3 > f(s) 'ABABABABAB' #the one with the most repetitions, not the max lenEjemplos de @rici:
s = 'aaabcabc' > f(s) 'abcabc' s = 'ababcababc' > f(s) 'ababcababc' #'abab' would also be a solution here # since it is repeated 2 times in a row as 'ababcababc'. # The proper algorithm would return both solutions.Con la combinación de re.findall() (usando un patrón de expresión regular específico) y max() :
import re # extended sample string s = 'asdfewfUBAUBAUBAUBAUBAasdkjnfencsADADADAD sometext' def find_longest_rep(s): result = max(re.findall(r'((\w+?)\2+)', s), key=lambda t: len(t[0])) return result[0] print(find_longest_rep(s))La salida:
UBAUBAUBAUBAUBAEl patrón fundamental:
((\w+?)\2+) :(....) - el grupo capturado más externo que es el primer grupo capturado(\w+?) - cualquier secuencia de caracteres que no sea un espacio en blanco incluida en el segundo grupo capturado; +? - cuantificador, coincidencias entre una y una cantidad ilimitada de veces, la menor cantidad de veces posible, ampliando según sea necesario\2+ : coincide con el mismo texto que coincidió más recientemente con el segundo grupo de capturaAquí está la solución basada en ((\w+?)\2+) expresiones regulares pero con mejoras adicionales:
import re from itertools import chain def repetitive(sequence, rep_min_len=1): """Find the most repetitive sequence in a string. :param str sequence: string for search :param int rep_min_len: minimal length of repetitive substring :return the most repetitive substring or None """ greedy, non_greedy = re.compile(r'((\w+)\2+)'), re.compile(r'((\w+?)\2+)') all_rep_seach = lambda regex: \ (regex.search(sequence[shift:]) for shift in range(len(sequence))) searched = list( res.groups() for res in chain(all_rep_seach(greedy), all_rep_seach(non_greedy)) if res) if not sequence: return None cmp_key = lambda res: res[0].count(res[1]) if len(res[1]) >= rep_min_len else 0 return max(searched, key=cmp_key)[0]Puedes probarlo así:
def check(seq, expected, rep_min_len=1): result = repetitive(seq, rep_min_len) print('%s => %s' % (seq, result)) assert result == expected, expected check('asdfewfUBAUBAUBAUBAUBAasdkBAjnfBAenBAcs', 'UBAUBAUBAUBAUBA') check('some noisy spacerABABABABABsome noisy spacer_ABCDEF_ABCDEFsome noisy spacerABABAB', 'ABABABABAB') check('aaabcabc', 'aaa') check('aaabcabc', 'abcabc', rep_min_len=2) check('ababcababc', 'ababcababc') check('ababcababcababc', 'ababcababcababc')Características clave:
((\w+)\2+) y no codiciosas ((\w+)\2+?) ;Lo que está buscando es un algoritmo para encontrar la repetición en tándem primitiva 'más grande' en una cadena. Aquí hay un artículo que describe un algoritmo de tiempo lineal para encontrar todas las repeticiones en tándem en una cadena y, por extensión, todas las repeticiones en tándem primitivas. Gusfield. Algoritmos de tiempo lineal para encontrar y representar todas las repeticiones en tándem en una cadena