Tout d'abord : excellente question. Je pense qu'il peut être très instructif d'essayer d'amener les moteurs regex à leurs limites.
La solution .NET de base
Vous avez dit dans les commentaires que ce serait facile avec .NET, mais comme il n'y a pas encore de réponse à ce sujet, j'ai pensé en écrire une.
Vous pouvez résoudre les questions 1 et 2 à l'aide des groupes d'équilibrage et du lookbehind à longueur variable de .NET. La plupart du travail est effectué par les groupes d'équilibrage, mais le lookbehind à longueur variable est crucial pour pouvoir détecter les correspondances multiples commençant sur la même ligne.
Bref, voici le modèle :
(?<= # lookbehind counts position of X into stack
^(?:(?<a>).)* # push an empty capture on the 'a' stack for each character
# in front of X
) # end of lookbehind
X # match X
(?=.*\n # lookahead checks that there are two more Xs right below
(?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
# element onto 'b' and consume a character
(?(a)(?!)) # make sure that stack 'a' is empty
X.*\n # match X and the rest of the line
(?:(?<-b>).)* # while we can pop an element from stack 'b', and consume
# a character
(?(b)(?!)) # make sure that stack 'b' is empty
X # match a final X
) # end of lookahead
Ce modèle doit être utilisé avec RegexOptions.Multiline pour le ^ pour correspondre aux débuts de lignes (et évidemment avec RegexOptions.IgnorePatternWhitespace pour que le mode freespacing fonctionne).
Voici quelques commentaires supplémentaires :
En plaçant tout, sauf le X initial, dans des listes de contrôle, nous n'avons aucun problème de chevauchement des correspondances ou même de correspondances commençant sur la même ligne. Cependant, le lookbehind doit être de longueur variable, ce qui limite certainement toute solution de ce type à .NET.
Le reste repose sur une bonne maîtrise des groupes d'équilibrage. Je n'entrerai pas dans les détails ici, parce que cela rend le jeu plus difficile. des réponses assez longues en soi . (voir MSDN et cet article de blog pour plus d'informations)
Le lookbehind correspond juste ^.* donc tout jusqu'au début de la ligne, mais pour chaque . nous poussons une capture vide sur la pile a , comptant ainsi la position de notre X comme la taille de la pile.
Ensuite, après avoir consommé le reste de la ligne dans le lookahead, nous correspondons à nouveau juste .* mais avant de consommer chaque . nous sortons un élément de la pile a (ce qui conduit à l'échec, une fois a est vide) et pousser une capture vide sur b (afin de ne pas oublier le nombre de caractères qu'il doit y avoir pour la troisième ligne).
Pour s'assurer que nous vidons réellement la pile entière, nous utilisons (?(a)(?!)) . Il s'agit d'un modèle conditionnel, qui essaie de correspondre à (?!) si la pile a n'est pas vide (et est simplement ignoré sinon). Et (?!) est un lookahead négatif vide, qui échoue toujours. Par conséquent, cela encode simplement "est a non vide ? échouer. sinon, continuer".
Maintenant que nous savons que nous avons consommé exactement le bon nombre de caractères dans la nouvelle ligne, nous essayons de faire correspondre un fichier X et le reste de la ligne. Ensuite, nous répétons le même processus avec la pile b . Maintenant, il n'est pas nécessaire de pousser sur une nouvelle pile, car si cela fonctionne, nous avons terminé. Nous vérifions que b est vide après cela, et correspond à un troisième X .
Enfin, une note d'optimisation : ce modèle fonctionne toujours si toutes les répétitions sont enveloppées dans des groupes atomiques (émulant ainsi les quantificateurs possessifs, qui ne sont pas supportés par .NET) ! Cela permettrait d'économiser beaucoup de retours en arrière. En outre, si si nous plaçons au moins les quantificateurs empilables dans des groupes atomiques, nous pouvons nous débarrasser des deux éléments suivants (?(...)(?!)) (car ils ne sont nécessaires que dans les cas où la répétition précédente a dû revenir en arrière).
La solution .NET complète
(Seuls les plus courageux des aventuriers devraient me suivre dans la grotte très sombre dans laquelle je suis sur le point de descendre...)
Comme discuté dans les commentaires, cette solution a un inconvénient : elle compte les correspondances qui se chevauchent. Par exemple
..X..
..X..
..X..
..X..
Donne deux correspondances, une dans la première et une dans la deuxième ligne. Nous aimerions éviter cela, et ne signaler qu'une seule correspondance (ou deux s'il y a 6 à 8 lignes). X et trois s'il y a 9 à 11 X et ainsi de suite). De plus, nous voulons rapporter les matchs aux 1er, 4ème, 7ème, ... X .
Nous pouvons ajuster le schéma ci-dessus pour permettre cette solution en exigeant que le premier X est précédé d'un multiple entier de 3 autre X qui répondent à nos exigences. L'idée de base pour vérifier ceci utilise la même manipulation de pile que précédemment (sauf que nous déplaçons les choses entre 3 piles de sorte qu'après avoir trouvé trois X s nous nous retrouvons là où nous avons commencé). Pour ce faire, nous devons modifier un peu le lookbehind.
Il y a cependant un hic. Le lookbehind à longueur variable de .NET utilise une autre fonctionnalité unique à .NET, RightToLeftMode dans lequel le modèle est lu (et correspond) de droite à gauche. Normalement, cela ne doit pas nous déranger, mais lorsque nous combinons cela avec les groupes d'équilibrage, nous pourrions être dans une situation où nous aurions besoin d'une aide supplémentaire. pour quelques surprises désagréables . En particulier, lorsque nous examinons l'évolution de nos piles de capture, nous devons également construire (et lire) l'expression de droite à gauche (ou de bas en haut).
Ainsi, lorsque vous lisez l'expression suivante (et mes annotations), commencez à la fin du lookbehind le plus externe (vous devrez faire défiler un peu) - c'est-à-dire juste avant le seul élément de niveau supérieur X puis lire tout le chemin jusqu'en haut. Et puis continuez après le retour en arrière.
(?<=
# note that the lookbehind below does NOT affect the state of stack 'a'!
# in fact, negative lookarounds can never change any capturing state.
# this is because they have to fail for the engine to continue matching.
# and if they fail, the engine needs to backtrack out of them, in which
# case the previous capturing state will be restored.
(?<! # if we get here, there is another X on top of the last
# one in the loop, and the pattern fails
^ # make sure we reached the beginning of the line
(?(a)(?!)) # make sure that stack 'a' is empty
(?:(?<-a>).)* # while we can pop an element from stack 'a', and consume
# a character
X.*\n # consume the next line and a potential X
)
# at this point we know that there are less than 3 Xs in the same column
# above this position. but there might still be one or two more. these
# are the cases we now have to eliminate, and we use a nested negative
# lookbehind for this. the lookbehind simply checks the next row and
# asserts that there is no further X in the same column.
# this, together with the loop, below means that the X we are going to match
# is either the topmost in its column or preceded by an integer multiple of 3
# Xs - exactly what we are looking for.
(?:
# at this point we've advanced the lookbehind's "cursor" by exactly 3 Xs
# in the same column, AND we've restored the same amount of captures on
# stack 'a', so we're left in exactly the same state as before and can
# potentially match another 3 Xs upwards this way.
# the fact that stack 'a' is unaffected by a full iteration of this loop is
# also crucial for the later (lookahead) part to work regardless of the
# amount of Xs we've looked at here.
^ # make sure we reached the beginning of the line
(?(c)(?!)) # make sure that stack 'a' is empty
(?:(?<-c>)(?<a>).)* # while we can pop an element from stack 'c', push an
# element onto 'a' and consume a character
X.*\n # consume the next line and a potential X
(?(b)(?!)) # make sure that stack 'b' is empty
(?:(?<-b>)(?<c>).)* # while we can pop an element from stack 'b', push an
# element onto 'c' and consume a character
X.*\n # consume the next line and a potential X
(?(a)(?!)) # make sure that stack 'a' is empty
(?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
# element onto 'b' and consume a character
X.*\n # consume the next line and a potential X
)* # this non-capturing group will match exactly 3 leading
# Xs in the same column. we repeat this group 0 or more
# times to match an integer-multiple of 3 occurrences.
^ # make sure we reached the beginning of the line
(?:(?<a>).)* # push an empty capture on the 'a' stack for each
# character in front of X
) # end of lookbehind (or rather beginning)
# the rest is the same as before
X # match X
(?=.*\n # lookahead checks that there are two more Xs right below
(?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
# element onto 'b' and consume a character
(?(a)(?!)) # make sure that stack 'a' is empty
X.*\n # match X and the rest of the line
(?:(?<-b>).)* # while we can pop an element from stack 'b', and consume
# a character
(?(b)(?!)) # make sure that stack 'b' is empty
X # match a final X
) # end of lookahead
Démonstration de travail sur RegexHero.net.
J'ai intercalé toutes les explications correctes avec le motif cette fois. Ainsi, si vous lisez le modèle de la manière que j'ai recommandée ci-dessus, vous obtiendrez l'explication au moment où vous en aurez besoin...
C'était une sacrée bête. Mais il satisfait maintenant à l'ensemble des spécifications et montre à quel point la saveur regex de .NET est puissante. Et, bien que cela semble assez horrible, je pense (une fois que vous avez réalisé le truc de droite à gauche) que c'est beaucoup plus facile à comprendre qu'une solution comparable avec PCRE (utilisant la récursion ou autre).
Comme Kobi l'a mentionné dans un commentaire ci-dessous, cela pourrait être raccourci de beaucoup, si vous acceptez que vos résultats soient trouvés dans des captures multiples d'une seule correspondance (par exemple, si vous avez une colonne de 7 X s vous n'obtenez qu'un seul match, mais avec 2 captures dans un certain groupe). Vous pouvez le faire en répétant la partie principale (lookahead) une ou plusieurs fois et en capturant l'élément initial X (tout mettre dans un lookahead cependant). Ainsi, le lookbehind n'a pas besoin de compter les triples de X mais il doit seulement vérifier qu'il n'y a pas de première ligne X . Cela permettrait probablement de réduire de moitié la taille du motif.
La solution partielle de la PCRE
(Si seuls les plus courageux des aventuriers m'ont suivi dans la dernière solution, il ne me reste probablement que des fous pour le prochain voyage...)
Pour prouver ce que je viens de dire à propos de la comparaison entre la solution ci-dessus et le PCRE, voyons comment nous pouvons, même de loin, résoudre le problème complet en PCRE. Nous devrons travailler un peu plus dur sans les lookbehinds à longueur variable et les groupes d'équilibrage.
Qtax (l'OP) a fourni une solution brillante à sa première question (vérifier si la chaîne de caractères contient un quelconque X -colonne) en utilisant des groupes auto-référents pour compter. Il s'agit d'une solution très élégante et compacte. Mais comme chaque correspondance va du début de la ligne jusqu'à la colonne X qui commence la colonne, et les correspondances ne peuvent pas se chevaucher, nous ne pouvons pas obtenir plusieurs correspondances par ligne. Nous pourrions essayer de tout mettre dans un lookahead (de sorte que rien n'est réellement mis en correspondance), mais deux correspondances de largeur nulle ne commenceront jamais à la même position - nous n'obtiendrons donc toujours qu'une seule correspondance par ligne candidate.
Cependant, il est possible de résoudre au moins la première partie de la question 2 avec PCRE : compter le nombre de colonnes commençant dans chaque ligne (et donc le nombre total de lignes). X colonnes). Puisque nous ne pouvons pas obtenir ce compte sous la forme de correspondances individuelles (voir le paragraphe précédent), et nous ne pouvons pas obtenir ce compte sous la forme de groupes individuels ou de captures (puisque PCRE ne fournit qu'un nombre fixe et fini de captures, contrairement à .NET). Ce que nous pouvons faire à la place est de coder le nombre de colonnes dans les correspondances.
Voici comment : pour chaque ligne, nous vérifions si une colonne commence. Si c'est le cas, nous incluons un caractère dans un certain groupe de capture. Ensuite, avant de signaler une correspondance réussie, nous essayons de trouver autant de colonnes supplémentaires que possible - pour chacune d'entre elles, nous ajoutons un caractère à ce groupe particulier. Ce faisant, nous codons le nombre de colonnes commençant dans chaque ligne dans la longueur de cette capture particulière.
En fait, la réalisation de ce concept dans une regex est beaucoup plus compliquée qu'il n'y paraît à première vue (et cela semble déjà assez compliqué). Quoi qu'il en soit, voici ce qu'il en est :
^
(?:(?|
(?(5)(?![\s\S]*+\5))
(?!(?!)()())
(?=
(?:
.
(?=
.*+\n
( \3? . )
.*+\n
( \4? . )
)
)*?
X .*+\n
\3
X .*+\n
\4
)
()
|
(?(5)(?=[\s\S]*+\5)|(?!))
(?:
.
(?=
.*+\n
( \1? .)
.*+\n
( \2? .)
)
)+?
(?=
(?<=X).*+\n
(\1)
(?<=X).*+\n
(\2)
(?<=X)
)
(?=
([\s\S])
[\s\S]*
([\s\S] (?(6)\6))
)
){2})+
(En fait, c'est un peu plus simple que cela - voir la réponse de Qtax pour savoir comment simplifier cette approche. Je vais quand même laisser cette approche ici pour des raisons académiques, car certaines techniques très avancées et intéressantes peuvent être apprises à partir d'elle - voir le résumé à la fin).
Oui, il n'y a pas d'annotations. Je me suis dit que personne ne les lirait de toute façon, alors je vais plutôt essayer de décomposer cette expression en plusieurs parties (je vais opter pour une approche descendante).
Alors regardons la couche extérieure de l'oignon de l'enfer :
^
(?:(?|
checkForNextColumn
|
countAndAdvance
){2})+
Nos correspondances sont donc à nouveau ancrées sur les débuts de lignes. Ensuite, nous avons un (?:...{2})+ ce qui signifie un nombre pair de répétitions de quelque chose. Et ce quelque chose est une alternance de deux sous-modèles. Ces sous-modèles représentent les étapes que j'ai mentionnées ci-dessus. Le premier vérifie qu'il y a une autre colonne qui commence dans la ligne actuelle, le second enregistre un compte et prépare l'état du moteur pour une autre application du premier sous-modèle. Le contrôle est donc donné au second motif - le premier vérifie simplement la présence d'une autre colonne en utilisant un lookahead et est donc un motif de largeur nulle. C'est pourquoi je ne peux pas simplement tout emballer dans + mais doivent faire le {2})+ sinon le composant de largeur zéro ne serait essayé qu'une seule fois ; c'est une optimisation nécessaire appliquée par presque tous les moteurs pour éviter les boucles infinies avec des motifs comme (a*)+ .
Il y a encore un détail (très important) : J'ai utilisé (?|...) pour l'alternance. Dans ce type de regroupement, chaque alternative commence par le même numéro de groupe. Ainsi, dans /(?|(a)|(b))/ les deux a et b peuvent être capturés dans le groupe 1 . C'est l'astuce cruciale qui permet la "communication" entre les sous-modèles, puisqu'ils peuvent modifier les mêmes groupes.
Bref... nous avons donc ces deux sous-modèles. Nous aimerions nous assurer que le contrôle alterne vraiment entre eux. Pour que chaque groupe échoue si c'est le dernier qui correspond. Nous faisons cela en enveloppant le motif dans une magie de regroupement et de référencement :
^(?:(?|
(?(5)(?![\s\S]*+\5)) # if group 5 has matched before make sure that
# it didn't match empty
checkForNextColumn # contains 4 capturing groups
() # this is group 5, match empty
|
(?(5)(?=[\s\S]*+\5)|(?!)) # make sure that group 5 is defined and that it
# matched empty
advanceEngineState # contains 4 capturing groups
(?=
([\s\S]) # this is group 5, match non-empty
[\s\S]* # advance to the end very end of the string
([\s\S] (?(6)\6)) # add a character from the end of the string to
# group 6
)
){2})+
Ainsi, à la fin de chaque alternative, nous invaliderons la condition pour que cette alternative puisse même commencer à correspondre. À la fin de la deuxième alternative, nous inclurons également un caractère dans le groupe 6 en utilisant la technique décrite par Qtax. C'est l'étape du comptage. C'est-à-dire que le groupe 6 contiendra autant de caractères qu'il y a de colonnes commençant dans la ligne actuelle.
Maintenant checkForNextColumn ne sera en fait que la solution de Qtax dans un lookahead. Elle a cependant besoin d'une modification supplémentaire et pour la justifier, nous allons examiner les points suivants advanceEngineState d'abord.
Réfléchissons à la façon dont nous voudrions modifier l'état, pour que la solution de Qtax corresponde à une deuxième colonne dans une rangée. Disons que nous avons l'entrée
..X..X..
..X..X..
..X..X..
et nous voulons trouver la deuxième colonne. Cela peut être fait en commençant la recherche à partir de la position juste après la première colonne. X et avoir des groupes \1 et \2 déjà initialisé aux trois premiers caractères ( ..X ) des rangées 2 et 3, respectivement (au lieu qu'elles soient vides).
Maintenant, essayons de faire ça : faire correspondre tout jusqu'à et y compris le prochain X qui commence une colonne, puis remplir deux groupes avec les préfixes de ligne correspondants pour les utiliser dans la fonction checkForNextColumn modèle. C'est à nouveau à peu près le modèle de Qtax, sauf que nous comptons les X (au lieu de s'arrêter juste avant), et que nous devons ajouter les captures dans un groupe séparé. Voici donc advanceEngineState :
(?:
.
(?=
.*+\n
( \1? .)
.*+\n
( \2? .)
)
)+?
(?=
(?<=X) .*+\n
(\1)
(?<=X) .*+\n
(\2)
(?<=X)
)
Notez comment j'ai tourné le X en lookbehinds, pour aller un caractère plus loin, et comment je copie efficacement le contenu final de \1 en \3 et ceux de \2 en \4 .
Donc si nous utilisons maintenant la solution de Qtax comme checkForNextColumn dans un lookahead, en utilisant des groupes \3 et \4 au lieu de \1 et \2 nous devrions avoir terminé.
Mais comment faire pour que ces groupes \3 et \4 au lieu de \1 et \2 ? Nous pourrions commencer le modèle par ()() ce qui correspondrait toujours, sans affecter le curseur du moteur, mais augmenterait le nombre de groupes de 2. Cependant, cela pose un problème : cela remet les groupes à zéro. 1 et 2 à des chaînes vides, ce qui si nous trouvons une deuxième colonne, advanceEngineState sera dans un état incohérent (car la position globale du moteur a été avancée, mais les groupes de comptage sont à nouveau à zéro). Nous voulons donc faire entrer ces deux groupes dans le modèle, mais sans affecter ce qu'ils capturent actuellement. Nous pouvons le faire en utilisant quelque chose que j'ai déjà mentionné avec les solutions .NET : les groupes dans les lookarounds négatifs n'affectent pas le contenu capturé (parce que le moteur doit revenir en arrière hors du lookaround pour continuer). Nous pouvons donc utiliser (?!(?!)()()) (un lookahead négatif qui ne peut jamais faire échouer le motif) pour inclure deux jeux de parenthèses dans notre motif, qui ne sont jamais utilisés. Cela nous permet de travailler avec des groupes 3 et 4 dans notre premier sous-modèle, tout en conservant les groupes 1 et 2 intacte pour la prochaine itération du second sous-modèle. En conclusion, ceci est checkForNextColumn :
(?!(?!)()())
(?=
(?:
.
(?=
.*+\n
( \3? . )
.*+\n
( \4? . )
)
)*?
X .*+\n
\3
X .*+\n
\4
)
Qui, pour la plupart, semble vraiment familier.
C'est donc ça. En le comparant à d'autres données, on obtiendra un groupe 6 qui contient une capture pour chaque ligne où une colonne commence - et la longueur de la capture nous dira combien de colonnes ont commencé là.
Oui, cela fonctionne vraiment (démo en direct).
Notez que cette solution (comme la solution de base de .NET) surcomptera les colonnes qui sont plus de 3 X s long. Je suppose qu'il est possible de corriger ce nombre avec des lookaheads (d'une manière similaire au lookbehind de la solution .NET complète), mais ceci est laissé comme un exercice au lecteur.
Il est un peu dommage que le problème de base de cette solution soit déjà très alambiqué et gonfle la solution (75% des lignes ne sont pour la plupart que des copies de la solution de Qtax). Parce que le cadre environnant a quelques techniques et leçons vraiment intéressantes :
- Nous pouvons avoir de multiples sous-modèles qui accomplissent des tâches spécifiques de correspondance/comptage, et les faire "communiquer" par le biais de groupes de capture mutuels, en les plaçant dans une
(?|...) en alternance et en boucle.
- Nous pouvons forcer les alternatives de largeur nulle à être exécutées encore et encore en les enveloppant dans un quantificateur fini tel que
{2} avant de tout mettre dans + .
- Les numéros de groupe peuvent être ignorés dans un sous-modèle (sans affecter le contenu capturé) en les plaçant dans un lookahead négatif infaillible tel que
(?!(?!)()) .
- Le contrôle peut passer d'un sous-modèle à l'autre en capturant quelque chose ou rien dans un certain groupe qui est vérifié lors de l'entrée dans l'alternance.
Cela permet des calculs très puissants (j'ai vu des affirmations selon lesquelles PCRE est en fait Turing-complet) - bien que ce soit certainement la mauvaise approche pour une utilisation productive. Mais essayer de comprendre (et de trouver) de telles solutions peut être un exercice de résolution de problèmes très stimulant et en quelque sorte gratifiant.
0 votes
Quelqu'un peut-il utiliser PHP (fonctions internes) pour calculer N lignes, et la longueur de chacune ? Il existe peut-être un moyen de générer "automatiquement" une regex comme je l'ai fait. ici sous la rubrique "briser les lois de l'expression géographique" ?
1 votes
@HamZa, cela devrait être à propos d'une seule expression régulière générale qui est indépendante de l'entrée. De telles astuces seraient donc de la triche ;-)
1 votes
Sans modifier l'entrée (rotation par exemple) et sans générer "automatiquement" des solutions, je dirais que bonne chance :-)
1 votes
@HamZa défi accepté ;-) 1 est facile dans .NET au moins, et PCRE pourrait être possible aussi. 2. par contre, je ne suis pas sûr que ce soit possible.
0 votes
Fait
$image =~ /(?{ whatever_you_need });se qualifier ? :)0 votes
@briandfoy avez-vous lu la question ? Plus précisément la première ligne, puis les deux questions finales elles-mêmes, auxquelles je ne pense pas que vous puissiez répondre (et démontrer) sans regex. "Il s'agit d'une question sur les *possibilités des saveurs modernes de regex. "*. Je ne sais pas comment être plus clair. Si vous souhaitez poster du code, vous pouvez le faire à la question dont le lien figure dans le premier paragraphe.
0 votes
Yep, désolé. On dirait que j'ai raté la première phrase.
3 votes
Fait
XXXXcomptent comme 0, 1 ou 2 séquences de 3Xs ?0 votes
@ikegami, horizontal ? 0, car la question ne porte que sur la verticale. Je suppose que l'idée originale est que les matches qui se chevauchent ne doivent pas être comptés. (Maintenant que j'y pense, ce serait difficile.) Si vous pouvez faire une solution purement regex qui compte, même avec des chevauchements, ce serait néanmoins intéressant.
0 votes
Pour votre exemple, pourquoi ne pas inverser la disposition de la matrice de façon à ce que les colonnes situées au-dessous les unes des autres se trouvent sur la même ligne - vous pouvez alors facilement vérifier avec une regex. Ça vous paraît juste ?
3 votes
@hakre il y a déjà deux réponses qui le suggèrent. cependant, il ne s'agit pas d'une solution uniquement regex. cette question est plus de nature académique pour voir jusqu'où les limites de certaines saveurs regex peuvent être poussées. bien sûr... si vous pouvez transposer l'image en utilisant regex seul ce serait impressionnant aussi ;)
0 votes
Pourquoi ne pas avoir opté pour un filtre de Sobel, qui est pour moi comme un regex d'image (avec une matrice ((0,0,0),(1,1,1),(0,0,0)) par exemple).
0 votes
Cette question a été ajoutée à la FAQ sur les expressions régulières de Stack Overflow sous la rubrique "Advanced Regex-Fu".
0 votes
@Qtax Hey mon pote, je me souviens de toi sur IRC il y a plusieurs années :) Je veux juste dire merci pour un excellent post. J'ai posté une solution entièrement fonctionnelle à la question 2 ci-dessous... J'espère que vous aurez la chance de la voir !