Python regex trouve toutes les correspondances qui se chevauchent?

98

J'essaie de trouver toutes les séries de nombres à 10 chiffres dans une plus grande série de nombres en utilisant re dans Python 2.6.

Je suis facilement capable de ne saisir aucune correspondance qui se chevauche, mais je veux chaque correspondance de la série numérique. Par exemple.

dans "123456789123456789"

Je devrais obtenir la liste suivante:

[1234567891,2345678912,3456789123,4567891234,5678912345,6789123456,7891234567,8912345678,9123456789]

J'ai trouvé des références à un "lookahead", mais les exemples que j'ai vus ne montrent que des paires de nombres plutôt que des groupements plus grands et je n'ai pas été en mesure de les convertir au-delà des deux chiffres.

python regex overlapping danspants
la source
6
Les solutions présentées ne fonctionneront pas lorsque les correspondances qui se chevauchent commencent au même point, par exemple, la correspondance entre "a | ab | abc" et "abcd" ne retournera qu'un seul résultat. Y a-t-il une solution pour cela qui n'implique pas d'appeler match () plusieurs fois, en gardant manuellement la trace de la limite de «fin»?
Vítor De Araújo
@ VítorDeAraújo: les expressions rationnelles qui se chevauchent (a|ab|abc)peuvent généralement être réécrites comme des expressions régulières qui ne se chevauchent pas avec des groupes de capture imbriqués, par exemple (a(b(c)?)?)?, où nous ignorons tout sauf le groupe de capture le plus à l'extérieur (c'est-à-dire le plus à gauche) lors du déballage d'une correspondance; c'est certes un peu douloureux et moins lisible. Ce sera également une regex plus performante pour correspondre.
smci

Réponses:

175

Utilisez un groupe de capture dans une anticipation. La recherche anticipée capture le texte qui vous intéresse, mais la correspondance réelle est techniquement la sous-chaîne de largeur zéro avant la recherche anticipée, donc les correspondances ne se chevauchent pas techniquement:

import re 
s = "123456789123456789"
matches = re.finditer(r'(?=(\d{10}))',s)
results = [int(match.group(1)) for match in matches]
# results: 
# [1234567891,
#  2345678912,
#  3456789123,
#  4567891234,
#  5678912345,
#  6789123456,
#  7891234567,
#  8912345678,
#  9123456789]
viande_mécanique
la source
2
Ma réponse est au moins 2 fois plus rapide que celle-ci. Mais cette solution est délicate, je l'approuve.
eyquem
16
Explication = au lieu de rechercher le motif (10 chiffres), il recherche tout ce qui est SUIVI PAR le motif. Il trouve donc la position 0 de la chaîne, la position 1 de la chaîne et ainsi de suite. Ensuite, il saisit le groupe (1) - le motif correspondant et en fait une liste. Très cool.
Tal Weiss
Je ne savais pas que vous pouviez utiliser des groupes correspondants dans les lookaheads, qui ne sont normalement pas censés être inclus dans une correspondance (et les sous-groupes correspondants n'apparaissent en effet pas dans la correspondance complète). Comme cette technique semble toujours fonctionner dans Python 3.4, je suppose qu'elle est considérée comme une fonctionnalité plutôt qu'un bogue.
JAB
10
J'ai rejoint StackOverflow, répondu aux questions et amélioré ma réputation juste pour pouvoir voter pour cette réponse. Je suis coincé avec Python 2.4 pour le moment, donc je ne peux pas utiliser les fonctions regex plus avancées de Python 3, et c'est juste le genre de supercherie bizarre que je recherchais.
TheSoundDefense
2
Pourriez-vous ajouter plus d'explications au code. Ce n'est pas le meilleur moyen selon Stack Overflow, d'avoir juste du code dans une réponse. Cela aidera certainement les gens.
Akshay Hazari
77

Vous pouvez également essayer d'utiliser le module tiersregex (non re), qui prend en charge les correspondances qui se chevauchent.

>>> import regex as re
>>> s = "123456789123456789"
>>> matches = re.findall(r'\d{10}', s, overlapped=True)
>>> for match in matches: print match
...
1234567891
2345678912
3456789123
4567891234
5678912345
6789123456
7891234567
8912345678
9123456789
David C
la source
17

J'adore les expressions régulières, mais elles ne sont pas nécessaires ici.

Simplement

s =  "123456789123456789"

n = 10
li = [ s[i:i+n] for i in xrange(len(s)-n+1) ]
print '\n'.join(li)

résultat

1234567891
2345678912
3456789123
4567891234
5678912345
6789123456
7891234567
8912345678
9123456789
eyquem
la source
10
Les expressions régulières ne sont pas nécessaires ici uniquement parce que vous appliquez les connaissances spéciales «dans une plus grande série de nombres», de sorte que vous savez déjà que chaque position 0 <= i < len(s)-n+1est garantie pour être le début d'une correspondance à 10 chiffres. Aussi je pense que votre code pourrait être accéléré, ce serait intéressant de coder le golf pour la vitesse.
smci