Discussion :

[aloysius_tim]

Bonjour a tous,

Je cherche a utiliser les expressions rationnelles en java (regel) afin de trouver si sont présent ou non des motifs géométriques.

Je m'explique, je suis dans un cadre ou on a un tableau de int a deux dimensions (soit des 0 soit des 1): tab[][] .

Je souhaiterai savoir s'il est présent dans ce tableau a double entrée un motif géométrique, par exemple un T formé uniquement par des 1. Donc au minimum 3 cases qui forment un T.
Un autre motif possible serait un I ou encore un L.

J'extrait donc mon tableau sous forme d'une chaine de caractère afin de pouvoir appliquer des expressions régulières dessus. Cependant, impossible de trouver le motif a rechercher...

Exemple:

Tableau de 1 et de 0 avec un motif T formé avec les 1
00000
01110
00100
00000

Extraction du tableau sous forme d'une chaine de caractere
00000011100010000000
Soit: 00000-01110-00100-00000 si l'on sépare chaque ligne.

Je voudrai maintenant appliquer une expression régulière dessus afin de trouver s'il contient un motif en T en L ou en I.

Si quelqu'un pouvait m'indiquer comment faire,

Merci d'avance

[joel.drigo]

Salut,

Premièrement, je ne mettrais pas de séparateur dans la flat string, parce que ça permet d'avoir le motif à n'importe quelle position, en ayant le même nombre de 0 de séparation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1110001000000000000000000

pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
11100
01000
00000
00000
00000

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

0111000100000000000000000

pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
01110
00100
00000
00000
00000

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

0000000000011100010000000

pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
00000
00000
01110
00100
00000

On voit que pour ce motif, on a donc :

• un nombre quelconque de 0
• puis trois fois 1
• puis trois fois 0
• puis une fois 1
• puis au moins un 0

En regex ça donne :

• un nombre quelconque de 0 : 0*
• puis trois fois 1 : 1{3}
• puis trois fois 0 : 0{3}
• puis une fois 1 : 1
• puis au moins un 0 : 0+

En code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
if (flat.matches("0*1{3}0{3}10+")) {
   System.out.println("Trouvé");
} else {
   System.out.println("Non trouvé");
}

• un nombre quelconque de 0 : 0*
• puis trois fois 1 : 111
• puis trois fois 0 : 000
• puis 1 : 1
• puis au moins un 0 : 0+

donc "0*111000100+"

On peut créer automatiquement l'expression régulière, à partir du motif à chercher, et de la largeur de ligne dans le tableau où se fait la recherche.

Si l'expression régulière ne doit pas dépendre de la largeur du tableau, on peut utilsier un groupe de capture : ""0*(0*)111(0*)\\1010\\20*"

• n
• 0* : un nombre quelconque de 0
• (0*) : un nombre quelconque de 0, capturé dans un groupe (premier groupe capturé)
• 111 : trois 1
• (0*) : un nombre quelconque de 0, capturé dans un groupe (second groupe capturé)
• \\1 : le groupe capturé 1 (donc le même nombre de 0 que trouvé pour ce groupe)
• 010 : un 0, puis un 1, puis un 0
• \\2 : le groupe capturé 2
• 0* : un nombre quelconque de 0

[CosmoKnacki]

je ne mettrais pas de séparateur dans la flat string, parce que ça permet d'avoir le motif à n'importe quelle position, en ayant le même nombre de 0 de séparation

Si tu fais ça, tu n'as plus aucun moyen de savoir si des 1 sont sur la même ligne ou pas. Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

0001110001000000000000000

qui vérifie pourtant la pattern, une fois disposé en tableau donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
00011
10001
00000
00000
00000

On ne peut donc pas se passer du délimiteur de ligne. J'ai choisi ici un saut de ligne, mais n'importe quoi peut faire l'affaire (sauf un 0 ou un 1).

Pour alléger, je n'ai pas doublé les antislashes (il faudra donc le faire dans le code Java). Ces patterns sont destinées à la méthode matches, c'est pourquoi, les ancres \A et \z n'y figurent pas. Pour les utiliser avec une autre méthode, il faut penser à les rajouter au besoin.

Pour le I, c'est assez simple, on capture l'espace entre deux 1 en imposant une nouvelle ligne et en incluant le 1 suivant, puis on répète la backréférence:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[0\n]*1(0*\n0*1)\1+[0\n]*

Pour le L, c'est comme pour le I, il faut juste vérifier qu'il y a au moins un 1 supplémentaire qui suit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[0\n]*1(0*\n0*1)\1+1+[0\n]*

Pour le T c'est plus difficile:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(?:0+\n)*(0*)(1+)1\2(0*)(\n\1(0+)1\5\3)\4*(?:\n0+)*

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(?:0+\n)*    # on écoule les éventuelles lignes de zéros
(0*)         # on capture les zéros avant le chapeau du T (groupe 1)
(1+)         # on capture les uns avant le 1 médian (groupe 2)
1            # 1 médian
\2           # on utilise une backréférence au groupe 2 (il doit y avoir le même nombre de 1 pour que ce soit symétrique)
(0*)         # on capture les zéros aprés le chapeau du T (groupe 3) (jusqu'à la fin de la ligne)
(            # on capture la première ligne de la tige (groupe 4)
  \n
  \1         # on a autant de zéros qu'avant le chapeau
  (0+)       # plus autant de zéros qu'il y a de 1 avant le 1 médian (groupe 5)
  1          # le 1 de la tige
  \5         # autant de zéros qu'il y a de 1 après le 1 médian (donc autant que dans le groupe 5)
  \3         # autant de zéros qu'après le chapeau 
)
\4*          # on répète le groupe 4, jusqu'à arriver au bout de la tige
(?:\n0+)*    # on complète avec les éventuelles lignes de zéros

(?:0+\n)* et (?:\n0+)* permettent respectivement de s'assurer qu'on est bien au début ou à la fin d'une ligne.

On peut aussi passer certains quantificateurs en possessifs pour accélérer l'échec de la pattern:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(?:0+\n)*+(0*)(1+)1\2(0*)(\n\1(0+)1\5\3)\4*+(?:\n0+)*

Une représentation des groupes de capture et de leur backréférences pour bien visualiser

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
00000000000            XXXXXXXXXXX
00111110000            1122X223333
00001000000            1155X553333    => ligne capturée dans le groupe 4   
00001000000            44444444444
00001000000            44444444444
00000000000            XXXXXXXXXXX
00000000000            XXXXXXXXXXX

NB: on peut aussi l'écrire comme ça:(?:0+\n)*(0*)(1+)1\2(0*)(?:\n\1(0+)1\4\3)+(?:\n0+)*NB2: toutes ces patterns s'appuient sur le fait que les lignes ont la même longueur. Il est également possible de le faire si ce n'est pas le cas, mais les patterns sont plus complexes.

[joel.drigo]

Si tu fais ça, tu n'as plus aucun moyen de savoir si des 1 sont sur la même ligne ou pas. Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

0001110001000000000000000

qui vérifie pourtant la pattern, une fois disposé en tableau donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
00011
10001
00000
00000
00000

Ah, oui, c'est vrai je n'avais pas pensé à ce cas.

EDIT: je ne comprends pas comment, en ligne 10 (pour la regex du T) :

(0+)       # plus autant de zéros qu'il y a de 1 avant le 1 médian (groupe 5)

pour moi, il y a au moins un 0, mais autant que de 1 que dans le groupe 2 ? Ça fonctionne implicitement parce qu'on borde la ligne avec \1 et \2 et qu'on s'assure de la symétrie avec le \5, ou alors il y aurait une raison pour laquelle ce fragment de regexp capture effectivement le même nombre de 0 que de 1 avant le 1 médian ?