¿Cómo puedo saber si una cadena se repite en Python?
Estoy buscando una manera de probar si una cadena determinada se repite o no en toda la cadena.
Ejemplos:
[
'0045662100456621004566210045662100456621', # '00456621'
'0072992700729927007299270072992700729927', # '00729927'
'001443001443001443001443001443001443001443', # '001443'
'037037037037037037037037037037037037037037037', # '037'
'047619047619047619047619047619047619047619', # '047619'
'002457002457002457002457002457002457002457', # '002457'
'001221001221001221001221001221001221001221', # '001221'
'001230012300123001230012300123001230012300123', # '00123'
'0013947001394700139470013947001394700139470013947', # '0013947'
'001001001001001001001001001001001001001001001001001', # '001'
'001406469760900140646976090014064697609', # '0014064697609'
]
son cuerdas que se repiten, y
[
'004608294930875576036866359447',
'00469483568075117370892018779342723',
'004739336492890995260663507109',
'001508295625942684766214177978883861236802413273',
'007518796992481203',
'0071942446043165467625899280575539568345323741',
'0434782608695652173913',
'0344827586206896551724137931',
'002481389578163771712158808933',
'002932551319648093841642228739',
'0035587188612099644128113879',
'003484320557491289198606271777',
'00115074798619102416570771',
]
son ejemplos de aquellos que no lo hacen.
Las secciones repetidas de las cadenas que me dan pueden ser bastante largas, y las cadenas en sí pueden tener 500 o más caracteres, por lo que recorrer cada carácter tratando de crear un patrón y luego verificar el patrón frente al resto de la cadena parece terriblemente lento. Multiplique eso por potencialmente cientos de cadenas y no veo ninguna solución intuitiva.
He analizado un poco las expresiones regulares y parecen buenas para cuando sabes lo que estás buscando, o al menos la longitud del patrón que estás buscando. Desafortunadamente, no sé ninguno de los dos.
¿Cómo puedo saber si una cadena se repite y, de ser así, cuál es la subsecuencia repetida más corta?
Aquí hay una solución concisa que evita expresiones regulares y bucles lentos en Python:
def principal_period(s):
i = (s+s).find(s, 1, -1)
return None if i == -1 else s[:i]
Consulte la respuesta de Community Wiki iniciada por @davidism para obtener resultados comparativos. En resumen,
La solución de David Zhang es la clara ganadora, superando a todas las demás al menos 5 veces para el conjunto de ejemplos grande.
(Las palabras de esa respuesta, no las mías).
Esto se basa en la observación de que una cuerda es periódica si y sólo si es igual a una rotación no trivial de sí misma. Felicitaciones a @AleksiTorhamo por darse cuenta de que luego podemos recuperar el período principal del índice de la primera aparición de sin (s+s)[1:-1]y por informarme sobre los argumentos opcionales starty endde Python string.find.
Aquí hay una solución que usa expresiones regulares.
import re
REPEATER = re.compile(r"(.+?)\1+$")
def repeated(s):
match = REPEATER.match(s)
return match.group(1) if match else None
Iterando sobre los ejemplos de la pregunta:
examples = [
'0045662100456621004566210045662100456621',
'0072992700729927007299270072992700729927',
'001443001443001443001443001443001443001443',
'037037037037037037037037037037037037037037037',
'047619047619047619047619047619047619047619',
'002457002457002457002457002457002457002457',
'001221001221001221001221001221001221001221',
'001230012300123001230012300123001230012300123',
'0013947001394700139470013947001394700139470013947',
'001001001001001001001001001001001001001001001001001',
'001406469760900140646976090014064697609',
'004608294930875576036866359447',
'00469483568075117370892018779342723',
'004739336492890995260663507109',
'001508295625942684766214177978883861236802413273',
'007518796992481203',
'0071942446043165467625899280575539568345323741',
'0434782608695652173913',
'0344827586206896551724137931',
'002481389578163771712158808933',
'002932551319648093841642228739',
'0035587188612099644128113879',
'003484320557491289198606271777',
'00115074798619102416570771',
]
for e in examples:
sub = repeated(e)
if sub:
print("%r: %r" % (e, sub))
else:
print("%r does not repeat." % e)
... produce esta salida:
'0045662100456621004566210045662100456621': '00456621'
'0072992700729927007299270072992700729927': '00729927'
'001443001443001443001443001443001443001443': '001443'
'037037037037037037037037037037037037037037037': '037'
'047619047619047619047619047619047619047619': '047619'
'002457002457002457002457002457002457002457': '002457'
'001221001221001221001221001221001221001221': '001221'
'001230012300123001230012300123001230012300123': '00123'
'0013947001394700139470013947001394700139470013947': '0013947'
'001001001001001001001001001001001001001001001001001': '001'
'001406469760900140646976090014064697609': '0014064697609'
'004608294930875576036866359447' does not repeat.
'00469483568075117370892018779342723' does not repeat.
'004739336492890995260663507109' does not repeat.
'001508295625942684766214177978883861236802413273' does not repeat.
'007518796992481203' does not repeat.
'0071942446043165467625899280575539568345323741' does not repeat.
'0434782608695652173913' does not repeat.
'0344827586206896551724137931' does not repeat.
'002481389578163771712158808933' does not repeat.
'002932551319648093841642228739' does not repeat.
'0035587188612099644128113879' does not repeat.
'003484320557491289198606271777' does not repeat.
'00115074798619102416570771' does not repeat.
La expresión regular (.+?)\1+$se divide en tres partes:
(.+?)es un grupo coincidente que contiene al menos uno (pero el menor número posible) de cualquier personaje (porque+?no es codicioso ).\1+comprueba al menos una repetición del grupo coincidente en la primera parte.$comprueba el final de la cadena para garantizar que no haya contenido adicional que no se repita después de las subcadenas repetidas (y el usore.match()garantiza que no haya texto que no se repita antes de las subcadenas repetidas).
En Python 3.4 y posteriores, puede eliminar $and use re.fullmatch()en su lugar, o (en cualquier Python al menos desde 2.3) ir al otro lado y usarlo re.search()con regex ^(.+?)\1+$, todo lo cual depende más del gusto personal que de cualquier otra cosa.
Se puede hacer la observación de que para que una cadena se considere repetida, su longitud debe ser divisible por la longitud de su secuencia repetida. Dado eso, aquí hay una solución que genera divisores de longitud desde 1hasta n / 2inclusive, divide la cadena original en subcadenas con la longitud de los divisores y prueba la igualdad del conjunto de resultados:
from math import sqrt, floor
def divquot(n):
if n > 1:
yield 1, n
swapped = []
for d in range(2, int(floor(sqrt(n))) + 1):
q, r = divmod(n, d)
if r == 0:
yield d, q
swapped.append((q, d))
while swapped:
yield swapped.pop()
def repeats(s):
n = len(s)
for d, q in divquot(n):
sl = s[0:d]
if sl * q == s:
return sl
return None
EDITAR: En Python 3, el /operador ha cambiado para realizar división flotante de forma predeterminada. Para obtener la intdivisión de Python 2, puedes usar el //operador en su lugar. Gracias a @ TigerhawkT3 por informarme sobre esto.
El //operador realiza división de enteros tanto en Python 2 como en Python 3, por lo que actualicé la respuesta para admitir ambas versiones. La parte donde probamos para ver si todas las subcadenas son iguales ahora es una operación de cortocircuito usando ally una expresión generadora.
ACTUALIZACIÓN: En respuesta a un cambio en la pregunta original, el código ahora se ha actualizado para devolver la subcadena repetida más pequeña si existe y Nonesi no. @godlygeek sugirió usarlo divmodpara reducir la cantidad de iteraciones en el divisorsgenerador, y el código también se actualizó para que coincida con eso. Ahora devuelve todos los divisores positivos de nen orden ascendente, exclusivo de nsí mismo.
Actualización adicional para un alto rendimiento: después de varias pruebas, llegué a la conclusión de que simplemente probar la igualdad de cadenas tiene el mejor rendimiento de cualquier solución de corte o iterador en Python. Por lo tanto, tomé una hoja del libro de @ TigerhawkT3 y actualicé mi solución. Ahora es 6 veces más rápido que antes, notablemente más rápido que la solución de Tigerhawk pero más lento que la de David.
A continuación se muestran algunos puntos de referencia para las diversas respuestas a esta pregunta. Hubo algunos resultados sorprendentes, incluido un rendimiento tremendamente diferente según la cuerda que se probó.
Algunas funciones se modificaron para que funcionen con Python 3 (principalmente reemplazándolas /con //para garantizar la división de enteros). Si ve algo mal, desea agregar su función o desea agregar otra cadena de prueba, haga ping a @ZeroPiraeus en la sala de chat de Python .
En resumen: hay una diferencia de aproximadamente 50 veces entre las soluciones de mejor y peor rendimiento para el gran conjunto de datos de ejemplo proporcionados por OP aquí (a través de este comentario). La solución de David Zhang es la clara ganadora, superando a todas las demás en aproximadamente 5 veces para el conjunto de ejemplos grande.
Un par de respuestas son muy lentas en casos extremadamente grandes de "no coincidencias". De lo contrario, las funciones parecen estar igualadas o claramente ganadoras según la prueba.
Aquí están los resultados, incluidos los gráficos realizados con matplotlib y seaborn para mostrar las diferentes distribuciones:
Corpus 1 (ejemplos suministrados - conjunto pequeño)
mean performance:
0.0003 david_zhang
0.0009 zero
0.0013 antti
0.0013 tigerhawk_2
0.0015 carpetpython
0.0029 tigerhawk_1
0.0031 davidism
0.0035 saksham
0.0046 shashank
0.0052 riad
0.0056 piotr
median performance:
0.0003 david_zhang
0.0008 zero
0.0013 antti
0.0013 tigerhawk_2
0.0014 carpetpython
0.0027 tigerhawk_1
0.0031 davidism
0.0038 saksham
0.0044 shashank
0.0054 riad
0.0058 piotr
Corpus 2 (ejemplos suministrados - conjunto grande)
mean performance:
0.0006 david_zhang
0.0036 tigerhawk_2
0.0036 antti
0.0037 zero
0.0039 carpetpython
0.0052 shashank
0.0056 piotr
0.0066 davidism
0.0120 tigerhawk_1
0.0177 riad
0.0283 saksham
median performance:
0.0004 david_zhang
0.0018 zero
0.0022 tigerhawk_2
0.0022 antti
0.0024 carpetpython
0.0043 davidism
0.0049 shashank
0.0055 piotr
0.0061 tigerhawk_1
0.0077 riad
0.0109 saksham
Corpus 3 (casos extremos)
mean performance:
0.0123 shashank
0.0375 david_zhang
0.0376 piotr
0.0394 carpetpython
0.0479 antti
0.0488 tigerhawk_2
0.2269 tigerhawk_1
0.2336 davidism
0.7239 saksham
3.6265 zero
6.0111 riad
median performance:
0.0107 tigerhawk_2
0.0108 antti
0.0109 carpetpython
0.0135 david_zhang
0.0137 tigerhawk_1
0.0150 shashank
0.0229 saksham
0.0255 piotr
0.0721 davidism
0.1080 zero
1.8539 riad
Las pruebas y los resultados sin procesar estaban disponibles https://bitbucket.org/snippets/schesis/nMnR/benchmarking-answers-to-httpantes de que se cancelara el servicio.
