Je cherche un moyen de tester si une chaîne donnée se répète ou non pour toute la chaîne.
Exemples:
[
'0045662100456621004566210045662100456621', # '00456621'
'0072992700729927007299270072992700729927', # '00729927'
'001443001443001443001443001443001443001443', # '001443'
'037037037037037037037037037037037037037037037', # '037'
'047619047619047619047619047619047619047619', # '047619'
'002457002457002457002457002457002457002457', # '002457'
'001221001221001221001221001221001221001221', # '001221'
'001230012300123001230012300123001230012300123', # '00123'
'0013947001394700139470013947001394700139470013947', # '0013947'
'001001001001001001001001001001001001001001001001001', # '001'
'001406469760900140646976090014064697609', # '0014064697609'
]
sont des chaînes qui se répètent, et
[
'004608294930875576036866359447',
'00469483568075117370892018779342723',
'004739336492890995260663507109',
'001508295625942684766214177978883861236802413273',
'007518796992481203',
'0071942446043165467625899280575539568345323741',
'0434782608695652173913',
'0344827586206896551724137931',
'002481389578163771712158808933',
'002932551319648093841642228739',
'0035587188612099644128113879',
'003484320557491289198606271777',
'00115074798619102416570771',
]
sont des exemples de ceux qui ne le font pas.
Les sections répétitives des chaînes qui me sont données peuvent être assez longues et les chaînes elles-mêmes peuvent contenir 500 caractères ou plus, donc parcourir chaque caractère en essayant de créer un modèle puis en vérifiant le modèle par rapport au reste de la chaîne semble terriblement lent. Multipliez cela par des centaines de chaînes et je ne vois aucune solution intuitive.
J'ai un peu examiné les expressions rationnelles et elles semblent bonnes lorsque vous savez ce que vous recherchez, ou au moins la longueur du motif que vous recherchez. Malheureusement, je ne connais ni l'un ni l'autre.
Comment savoir si une chaîne se répète et si c'est le cas, quelle est la sous-séquence répétée la plus courte?
Réponses:
Voici une solution concise qui évite les expressions régulières et les boucles in-Python lentes:
Voir la réponse du Wiki de la communauté lancée par @davidism pour les résultats de référence. En résumé,
(Les mots de cette réponse, pas les miens.)
Ceci est basé sur l'observation qu'une chaîne est périodique si et seulement si elle est égale à une rotation non triviale d'elle-même. Félicitations à @AleksiTorhamo pour avoir réalisé que nous pouvons alors récupérer la période principale de l'index de la première occurrence de
s
in(s+s)[1:-1]
, et pour m'avoir informé des optionsstart
etend
arguments de Pythonstring.find
.la source
.find()
ou à la.index()
place dein
, par exemple.(s+s).find(s, 1, -1)
.(s+s).find(s, 1, -1)
sera (très légèrement) plus rapide que(s+s)[1:-1].find(s)
, au moins pour les chaînes plus grandes, car le découpage signifie que vous devez créer une autre copie de (presque) la chaîne entière."abcd"
le caractère à droite et collez-la à gauche pour obtenir"dabc"
. Cette procédure est appelée rotation d'une chaîne vers la droite de 1 caractère . Répétez plusieursn
fois pour faire pivoter une chaîne vers la droite den
caractères. Maintenant, observez que si nous avons une chaîne dek
caractères, la rotation vers la droite de n'importe quel multiplek
laisse la chaîne inchangée. Une rotation non triviale d'une chaîne est une rotation dont le numéro de caractère n'est pas un multiple de la longueur de la chaîne.Voici une solution utilisant des expressions régulières.
En répétant les exemples de la question:
... produit cette sortie:
L'expression régulière
(.+?)\1+$
est divisée en trois parties:(.+?)
est un groupe correspondant contenant au moins un (mais aussi peu que possible) de n'importe quel caractère (car il+?
n'est pas gourmand ).\1+
vérifie au moins une répétition du groupe correspondant dans la première partie.$
vérifie la fin de la chaîne pour s'assurer qu'il n'y a pas de contenu supplémentaire non répétitif après les sous-chaînes répétées (et l'utilisationre.match()
garantit qu'il n'y a pas de texte non répétitif avant les sous-chaînes répétées).Dans Python 3.4 et versions ultérieures, vous pouvez supprimer
$
et utiliser à lare.fullmatch()
place, ou (dans n'importe quel Python au moins aussi loin que 2.3), aller dans l'autre sens et utiliserre.search()
avec l'expression régulière^(.+?)\1+$
, qui sont tous plus à votre goût qu'autre chose.la source
Vous pouvez faire l'observation que pour qu'une chaîne soit considérée comme répétitive, sa longueur doit être divisible par la longueur de sa séquence répétée. Étant donné que, voici une solution qui génère des diviseurs de la longueur de
1
àn / 2
inclus, divise la chaîne d'origine en sous-chaînes avec la longueur des diviseurs et teste l'égalité de l'ensemble de résultats:EDIT: En Python 3, l'
/
opérateur a changé pour faire la division flottante par défaut. Pour obtenir laint
division de Python 2, vous pouvez utiliser l'//
opérateur à la place. Merci à @ TigerhawkT3 d'avoir porté cela à mon attention.L'
//
opérateur effectue une division entière dans Python 2 et Python 3, j'ai donc mis à jour la réponse pour prendre en charge les deux versions. La partie où nous testons pour voir si toutes les sous-chaînes sont égales est maintenant une opération de court-circuit utilisantall
et une expression de générateur.MISE À JOUR: En réponse à une modification de la question d'origine, le code a maintenant été mis à jour pour renvoyer la plus petite sous-chaîne répétitive si elle existe et
None
si elle n'existe pas. @godlygeek a suggéré d'utiliserdivmod
pour réduire le nombre d'itérations sur ledivisors
générateur, et le code a également été mis à jour pour correspondre à cela. Il renvoie maintenant tous les diviseurs positifs den
dans l'ordre croissant, à l'exclusion den
lui - même.Mise à jour supplémentaire pour des performances élevées: après plusieurs tests, je suis arrivé à la conclusion que le simple test d'égalité de chaîne a les meilleures performances de toute solution de découpage ou d'itérateur en Python. Ainsi, j'ai pris une feuille du livre de @ TigerhawkT3 et mis à jour ma solution. Il est maintenant plus de 6 fois plus rapide qu'auparavant, sensiblement plus rapide que la solution de Tigerhawk mais plus lent que celui de David.
la source
(n/2)
incluse.n / 2
endivisors()
êtren // 2
?Voici quelques repères pour les différentes réponses à cette question. Il y a eu des résultats surprenants, notamment des performances très différentes selon la chaîne testée.
Certaines fonctions ont été modifiées pour fonctionner avec Python 3 (principalement en les remplaçant
/
par//
pour assurer une division entière). Si vous voyez quelque chose de mal, que vous souhaitez ajouter votre fonction ou que vous souhaitez ajouter une autre chaîne de test, envoyez une requête ping à @ZeroPiraeus dans le salon de discussion Python .En résumé: il y a environ 50 fois la différence entre les solutions les plus performantes et les moins performantes pour le grand ensemble d'exemples de données fournis par OP ici (via ce commentaire). La solution de David Zhang est clairement gagnante, surpassant toutes les autres d'environ 5 fois pour le grand ensemble d'exemples.
Deux ou trois des réponses sont très lentes dans des cas de non-correspondance extrêmement importants. Sinon, les fonctions semblent être également égales ou clairement gagnantes selon le test.
Voici les résultats, y compris les graphiques réalisés à l'aide de matplotlib et de seaborn pour montrer les différentes distributions:
Corpus 1 (exemples fournis - petit ensemble)
Corpus 2 (exemples fournis - grand ensemble)
Corpus 3 (cas de bord)
Les tests et les résultats bruts sont disponibles ici .
la source
Solution non regex:
Solution non regex plus rapide, grâce à @ThatWeirdo (voir commentaires):
La solution ci-dessus est très rarement plus lente que l'original de quelques pour cent, mais elle est généralement beaucoup plus rapide - parfois beaucoup plus rapide. Il n'est toujours pas plus rapide que le davidisme pour les cordes plus longues, et la solution regex de zéro est supérieure pour les cordes courtes. Il sort le plus rapidement (selon le test du davidisme sur github - voir sa réponse) avec des chaînes d'environ 1000-1500 caractères. Quoi qu'il en soit, il est de manière fiable le deuxième plus rapide (ou mieux) dans tous les cas que j'ai testés. Merci, ThatWeirdo.
Tester:
Résultats:
la source
repeat('aa')
retoursNone
len(string[0:i])
est toujours égal ài
(dans ce cas au moins). Le remplacement de ceux-ci, ainsi que l'enregistrementlen(string)
et lesstring[0:i]
variables peuvent accélérer les choses. Aussi IMO, c'est une excellente solution, génial;)Tout d'abord, divisez la chaîne par deux tant qu'il s'agit d'un doublon en "2 parties". Cela réduit l'espace de recherche s'il y a un nombre pair de répétitions. Ensuite, en travaillant vers l'avant pour trouver la plus petite chaîne répétitive, vérifiez si le fractionnement de la chaîne complète par une sous-chaîne de plus en plus grande entraîne uniquement des valeurs vides. Seules les sous-chaînes jusqu'à
length // 2
doivent être testées, car tout ce qui se passerait n'aurait aucune répétition.Cela renvoie la correspondance la plus courte ou Aucune s'il n'y a pas de correspondance.
la source
Le problème peut également être résolu
O(n)
dans le pire des cas avec la fonction préfixe.Remarque, il peut être plus lent dans le cas général (UPD: et est beaucoup plus lent) que d'autres solutions qui dépendent du nombre de diviseurs de
n
, mais trouvent généralement échoue plus tôt, je pense que l'un des mauvais cas pour eux seraaaa....aab
, où il y en an - 1 = 2 * 3 * 5 * 7 ... *p_n - 1
a
.Tout d'abord, vous devez calculer la fonction de préfixe
alors soit il n'y a pas de réponse, soit la période la plus courte est
et il suffit de vérifier si
k != n and n % k == 0
(sik != n and n % k == 0
alors la réponse ests[:k]
, sinon il n'y a pas de réponseVous pouvez vérifier la preuve ici (en russe, mais le traducteur en ligne fera probablement l'affaire)
la source
prefix_function()
n'est pas valide Python: vous avez manquantes sur vos deux pointswhile
etif
déclarations, et au&&
lieu deand
. Après avoir corrigé ceux-ci, il échoue àUnboundLocalError: local variable 'i' referenced before assignment
cause de la lignefor i in range(i, n):
.prefix_function()
pour renvoyer des résultats similaires aux autres réponses - soit la sous-chaîne la plus courte ouNone
- je vais l'inclure dans une référence révisée que je mets en place.Cette version essaie uniquement les longueurs de séquence candidates qui sont des facteurs de la longueur de chaîne; et utilise l'
*
opérateur pour créer une chaîne complète à partir de la séquence candidate:Merci à TigerhawkT3 d'avoir remarqué que
length // 2
sans+ 1
ne correspondrait pas à l'abab
affaire.la source
range
limite delength//2
, tout comme je l'ai fait - vous devez changer celalength//2+1
si vous voulez attraper des chaînes qui sont exactement doublées (par exemple'aabaab'
).Voici une solution simple, sans regex.
Pour les sous-chaînes de
s
départ à partir de l'index zéro, de longueurs 1 àlen(s)
, vérifiez si cette sous-chaînesubstr
est le motif répété. Cette vérification peut être effectuée en concaténantsubstr
avec elle-même lesratio
temps, de sorte que la longueur de la chaîne ainsi formée est égale à la longueur des
. Par conséquentratio=len(s)/len(substr)
.Renvoie la première fois qu'une telle sous-chaîne est trouvée. Cela fournirait la plus petite sous-chaîne possible, s'il en existe une.
la source
J'ai commencé avec plus de huit solutions à ce problème. Certains étaient basés sur l'expression régulière (correspondance, findall, split), certains de découpage et de test de chaînes, et certains avec des méthodes de chaîne (find, count, split). Chacun avait des avantages en termes de clarté de code, de taille de code, de vitesse et de consommation de mémoire. J'allais poster ma réponse ici quand j'ai remarqué que la vitesse d'exécution était classée comme importante, j'ai donc fait plus de tests et d'amélioration pour arriver à ceci:
Cette réponse semble similaire à quelques autres réponses ici, mais elle a quelques optimisations de vitesse que d'autres n'ont pas utilisées:
xrange
est un peu plus rapide dans cette application,s[:n]
directement, nous évitons de créer une variable dans chaque boucle.Je serais intéressé de voir comment cela fonctionne dans les tests standard avec du matériel commun. Je pense qu'il sera bien en deçà de l'excellent algorithme de David Zhang dans la plupart des tests, mais devrait être assez rapide sinon.
J'ai trouvé ce problème très contre-intuitif. Les solutions que je pensais rapides seraient lentes. Les solutions qui paraissaient lentes étaient rapides! Il semble que la création de chaînes de Python avec l'opérateur multiply et les comparaisons de chaînes soient hautement optimisées.
la source
statistics
module), j'ai donc dû changer votre/
s en//
s et remplacezxrange()
parrange()
(qui se comporte comme 2.xxrange()
dans 3.x).//
dans 3.x est une division entière (tout comme le comportement 2.x de/
), tandis que 3.x/
est une division flottante (qui, j'en suis sûr, serait beaucoup plus lente même si elle ne cassait pas votre solution en provoquant une tentative d'utilisation) un flotteur comme index). Comme mentionné, 3.xrange()
est la même chose que 2.xxrange()
; aucun équivalent de 2.xrange()
n'existe dans 3.x. Je ne pense donc pas que ce soit la cause de tout écart entre l'indice de référence et les délais que vous avez faits. C'est probablement juste que 3.x est globalement plus lent que 2.x (ou peut-être que votre machine est plus rapide que la mienne).Cette fonction s'exécute très rapidement (testée et c'est plus de 3 fois plus rapide que la solution la plus rapide ici sur des chaînes avec plus de 100k caractères et la différence s'accentue plus le motif répétitif est long). Il essaie de minimiser le nombre de comparaisons nécessaires pour obtenir la réponse:
Notez que par exemple pour une chaîne de longueur 8, il ne vérifie que les fragments de taille 4 et il n'a pas besoin de tester davantage car le motif de longueur 1 ou 2 entraînerait la répétition du motif de longueur 4:
la source
Dans la réponse de David Zhang, si nous avons une sorte de tampon circulaire, cela ne fonctionnera pas: en
principal_period('6210045662100456621004566210045662100456621')
raison du démarrage621
, où j'aurais aimé qu'il crache:00456621
.En étendant sa solution, nous pouvons utiliser les éléments suivants:
la source
Voici le code en python qui vérifie la répétition de la sous-chaîne dans la chaîne principale donnée par l'utilisateur .
Entrée :
Sortie :
Entrée :
Sortie :
la source