assertions négatives

Version imprimable

17/08/2010, 00h09
SSJ17Vegeta

assertions négatives

Bonjour à tous,

Je vous expose ici un problème d'expression régulière en apparence assez simple mais sur lequel je bloque depuis quelques temps : regex builders, assistants, rien n'y fait, pas moyen... :aie:

Le problème :
Je dois analyser un fichier texte complet et remplacer toutes les occurences d'un mot donné (ex: toto) par une certaine valeur (ex: titi), mais uniquement si ce mot n'est pas compris entre crochets ou accolades, directement ou indirectement (c'est-à-dire que dans l'exemple [un_mot toto tutu], toto ne doit pas être inclus).

Les solutions envisagées
J'ai lu quelques articles notamment sur les assertions négatives, pensant qu'une expression du genre (?<!\[)+(.*)toto(.*)+(?!\]) ferait l'affaire, en essayant plusieurs variantes, mais rien n'y a fait, même si leur usage m'a permis de m'approcher du résultat.

Votre aide serait donc grandement appréciée, aussi je vous en remercie d'avance :mrgreen:

Bonjour,

y'a forcément moyen avec les regex, mais sinon tu peux faire une fonction maison :)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
$chaine = 'dfsd toto[fgdfg toto dfds]dfg [d toto toto][toto';
 
function killToto($chaine, $replaceBy){
 
	$sortie = '';
	$isKillPossible = false;		
 
	$countChaine = strlen($chaine);
	$i=0;
 
	while(true){
		if($i > $countChaine)
			break;
 
		$c = substr($chaine, $i, 1);
 
		if($c == '['){
			$isKillPossible = true;
			$sortie .= $c;
		}elseif($c == ']'){
			$isKillPossible = false;
			$sortie .= $c;
		}elseif(strtolower($c) == 't' && $isKillPossible == true && strtolower(substr($chaine, $i, 4)) == 'toto' && verifNext($chaine, $i)){
			$sortie .= $replaceBy;
			$i += 4;
			continue;
		}else{
			$sortie .= $c;
		}
 
		$i++;
 
	}
 
	return $sortie;
 
}
 
function verifNext($chaine, $i){
 
	$countChaine = strlen($chaine);
 
	while(true){
 
		if($i > $countChaine)
			return false;
 
		if(substr($chaine, $i, 1) == ']')
			return true;
 
		$i++;
	}
 
}
 
echo killToto($chaine, 'ok');
 
//Affiche
dfsd toto[fgdfg ok dfds]dfg [d ok ok][toto

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
$reg="~(?:<)(?>titi)(?>>)~";
$chaine="<titi>titititi<titi>titititititi<titi>titititititi";
$res=preg_replace($reg,'<b style="color:red">TOTO</b>',$chaine);
?>		
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
</head>
<body>
<?php
echo $res;
	?>
</body>
</html>

SpaceFrog, peux tu expliquer ta RE ~(?:<)(?>titi)(?>>)~ stp.

Je ne la comprends pas et en l’essayant sous Python, j’obtiens le message d’erreur:
error: unexpected end of pattern

Madfrix, ton code est impressionant mais étant donné que « y'a forcément moyen avec les regex » , il vaut mieux à mon avis chercher une vraie solution avec regex.

Pour ma part , j’ai rapidement trouvé une solution hier soir en Python, mais elle n’est valable que pour une modif tenant compte seulement des crochets.

Le principe en est de splitter la chaîne selon les segments ’[.........]’ : on obtient ainsi deux types de segments, qui alternent dans une liste.

Il suffit alors de ne faire le remplacement des 'totoi' que dans les segments autres que les ’[..............]’ , ce qui est facile puisqu’en parcourant la liste de la chaîne splittée, les segments ’[.................]’ sont tous avec des index impairs dans la liste (premier élément de la liste a index 0 ) et donc n’ont pas leurs totoi substitués tandis que les autres sont d’index pairs et ont leur 'totoi' remplacés.

Ensuite on recolle l’ensemble des segments.

Dans ce code, il y a deux regex:
une pour détecter les segments ’[....................]’ : (\[[^[\]]*\])

et l’autre pour détecter les mots ’totoi’ : (\W|\A)(toto\d)(\W|\Z)

les \W de part et d’autre signifient que ne sont considérés comme mots 'toto0', 'toto1', 'toto2' etc que les 'totoi' qui ne font pas partie d’un mot plus long
Les \A et \Z sont là parce que le mot 'totoi' peut être au début ou à la fin du segment résultant de la découpe par split().
Code:

1 2 3 4 5 6 7 8 9 10 11 12 ch = '''ab toto0 cd fg[h kj toto1 mnh ] uk toto2 [ju toto3] pa toto4[toto5 vfr] fd toto6 qw [toto7 nhft [jkiu toto8 k]toto9 nb [ard toto0 pototo1 f[ru toto2 n]''' import re pat = re.compile('(\[[^[\]]*\])') pat_totod = re.compile('(\W|\A)(toto\d)(\W|\Z)') print ch,'\n' print pat.split(ch),'\n' print ''.join( pat_totod.sub('\\1EDGAR\\3',u) if i%2==0 else u for i,u in enumerate( pat.split(ch) ) )
Code:

1 2 3 4 5 6 7 ab toto0 cd fg[h kj toto1 mnh ] uk toto2 [ju toto3] pa toto4[toto5 vfr] fd toto6 qw [toto7 nhft [jkiu toto8 k]toto9 nb [ard toto0 pototo1 f[ru toto2 n] ['ab toto0 cd fg', '[h kj toto1 mnh ]', ' uk toto2 ', '[ju toto3]', ' pa toto4', '[toto5 vfr]', '\nfd toto6 qw [toto7 nhft ', '[jkiu toto8 k]', 'toto9 nb [ard toto0 pototo1 f', '[ru toto2 n]', ''] ab EDGAR cd fg[h kj toto1 mnh ] uk EDGAR [ju toto3] pa EDGAR[toto5 vfr] fd EDGAR qw [EDGAR nhft [jkiu toto8 k]EDGAR nb [ard EDGAR pototo1 f[ru toto2 n]
Le problème de ce code, c’est que ça ne traite que par rapport aux crochets et que rajouter la prise en compte des accolades, ça corse le problème et jusqu’à présent j’ai calé.
J’ai une vague idée ce matin, il faut que je vois ça.

Il faut aussi remarquer que les résultats dépendent de la façon dont on définit la RE pour capturer les segments ’[...................]’.

J’ai fait en sorte qu’entre les deux crochets extrèmes d’un segment ’[........................]’ , il n’y ait pas de signe ’]’ ni de ’[’. On pourrait en décider autrement. Mais comme ce n’est pas précisé dans la question, j’ai fait un choix.

Est-ce qu’on pourrait avoir une directive sur ce point stp SSJ17Vegeta.

PS

J’aurais bien essayé de coder en PHP mais j’ai retéléchargé et réinstallé WAMP5 et je n’arrive plus à exécuter des codes comme avant.

J’ai un fichier C:\wamp\www\fichier.php dans www directory, mais quand je vais dans http://localhost/ je ne le vois pas. Il me semble que c’était bien ainsi que je faisais avant: aller dans http://localhost/. Est-ce correct ?

D’autre part, les fichiers doivent-ils bien avoir l’extension .php ?

17/08/2010, 12h38
SpaceFrog

je pense qu'en python il faut echapper les < ou >

en fait la reg devrait être

Code:

$reg="~(?:<)(?>titi)(?>(?:>))~";

(?:<) => groupe non capturant < ouvrant
(?>titi) suivi de titi
(?>(?:>)) suivi d'un groupe non capturant > fermant
17/08/2010, 16h38
eyquem
En python les assertions s’écrivent:
Code:

1 2 3 4 5 ?= assertion positive en avant ?! assertion négative en avant ?<= assertion positive en arrière ?<! assertion négative en arrière
Ta RE se traduit par " (?:\[)(?=titi)(?=(?:\])) " en Python si je comprends bien.

J’ai mis des [ et ] à la place des < et > puisque SSJ17Vegeta parle de crochets et accolades.

Je ne comprends pas ta logique.
Le mot titi n’est pas censé se trouver juste après un crochet ouvrant comme l'exprime (?:\[)(?=titi)

En plus s’il n’y a que des (?: ) et (?= ) , je ne vois pas ce qui est capturé.

En outre, en Python une assertion ne définit pas un groupe capturant. Est-ce différent en PHP ?

Est-ce que tu as fait tourner ton code, SpaceFrog ?
Quel résultat obtiens tu sur avec les chaînes suivantes ?

'''ab toto0 cd fg[h kj toto1 mnh ] uk toto2 [ju toto3] pa toto4[toto5 vfr]
fd toto6 qw [toto7 nhft [jkiu toto8 k]toto9 nb [ard toto0 pototo1 f[ru toto2 n]'''

'''ab toto0 cd fg[h kj toto1 mnh ] uk toto2 gt{jh toto3 bg} ff
de { bbfe toto4++ {ngt toto5} vu [gtre { gt toto6 y]mju} hh
fd {ggdug toto7 fdg[ {kju toto8 sd[ gtre ==toto9 {[toto0 ku} gf
{{{ gtr [lkj toto1 bg]]]]] { gt toto2}}[{}} gtr toto3]}
[ju toto3] pa{j toto4[ toto5 v}fr{]{ kiu ]{kju toto6 toto7 {} toto8]
fd toto6 qw [toto7 nhft [jkiu toto8 k]toto9 nb [ard toto0 pototo1 f[ru toto2 n]'''

Ça risque de ne pas vous intéresser beaucoup, mais voici un code en Python qui répond au problème posé: remplacement de tous les totoi (j’ai mis des numéros aprés les toto pour mieux se repérer) par EDGAR sauf entre deux crochets ou entre deux accolades.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
ch = '''ab toto0 cd fg[h kj toto1 mnh ] uk toto2 gt{jh toto3 bg} ff
de { bbfe toto4++ {ngt toto5} vu [gtre { gt toto6 y]mju} hh
fd {ggdug toto7 fdg[ {kju toto8 sd[ gtre ==toto9 {[toto0 ku} gf
{{{ gtr [lkj toto1 bg]]]]] { gt toto2}}[{}} gtr toto3]}
[ju toto3] pa{j toto4[ toto5 v}fr{]{ kiu ]{kju toto6 toto7 {} toto8]
fd toto6 qw [toto7 nhft [jkiu toto8 k]toto9 nb [ard toto0 pototo1 f[ru toto2 n]'''
print ch,'\n'
 
import re
patcro = re.compile('(\[[^[\]]*\])')
patacc = re.compile('(\{[^{\}]*\})')
pat_totod = re.compile('(\W|\A)(toto\d)(\W|\Z)')
 
li = []
for m in patcro.finditer(ch):
    li.append( (m.start(),'D') )
    li.append( (m.end(),'F') )
for m in patacc.finditer(ch):
    li.append( (m.start(),'D') )
    li.append( (m.end(),'F') )
li.sort()
print '\n',li
 
li2 = []
deb,what = li[0][0],'D'
for pos,deouef in li:
    if deouef=='D' and what=='F':
        li2.append((deb,fin))
        deb = pos
        what = 'D'
    if deouef=='F':
        fin = pos                    
        what = 'F'
 
li2 = tuple(li2)
print '\n',li2
 
def yesorno(m):
    if any( u<m.start()<v for u,v in li2):
        return m.group()
    else:
        return 'EDGAR'.join(m.group(1,3))
 
chtr = pat_totod.sub(yesorno,ch)
print '\n',chtr

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ab toto0 cd fg[h kj toto1 mnh ] uk toto2 gt{jh toto3 bg} ff
de { bbfe toto4++ {ngt toto5} vu [gtre { gt toto6 y]mju} hh
fd {ggdug toto7 fdg[ {kju toto8 sd[ gtre ==toto9 {[toto0 ku} gf
{{{ gtr [lkj toto1 bg]]]]] { gt toto2}}[{}} gtr toto3]}
[ju toto3] pa{j toto4[ toto5 v}fr{]{ kiu ]{kju toto6 toto7 {} toto8]
fd toto6 qw [toto7 nhft [jkiu toto8 k]toto9 nb [ard toto0 pototo1 f[ru toto2 n] 
 
 
[(14, 'D'), (31, 'F'), (43, 'D'), (56, 'F'), (78, 'D'), (89, 'F'), (93, 'D'), (99, 'D'), (112, 'F'), (116, 'F'), (169, 'D'), (180, 'F'), (192, 'D'), (206, 'F'), (211, 'D'), (222, 'F'), (223, 'D'), (224, 'D'), (226, 'F'), (238, 'F'), (240, 'D'), (250, 'F'), (253, 'D'), (261, 'D'), (271, 'F'), (275, 'F'), (299, 'D'), (301, 'F'), (333, 'D'), (347, 'F'), (376, 'D'), (388, 'F')]
 
((14, 31), (43, 56), (78, 89), (93, 116), (169, 180), (192, 206), (211, 222), (223, 238), (240, 250), (253, 275), (299, 301), (333, 347))
 
ab EDGAR cd fg[h kj toto1 mnh ] uk EDGAR gt{jh toto3 bg} ff
de { bbfe EDGAR++ {ngt toto5} vu [gtre { gt toto6 y]mju} hh
fd {ggdug EDGAR fdg[ {kju EDGAR sd[ gtre ==EDGAR {[toto0 ku} gf
{{{ gtr [lkj toto1 bg]]]]] { gt toto2}}[{}} gtr toto3]}
[ju toto3] pa{j toto4[ toto5 v}fr{]{ kiu ]{kju EDGAR toto7 {} EDGAR]
fd EDGAR qw [EDGAR nhft [jkiu toto8 k]toto9 nb [ard EDGAR pototo1 f[ru EDGAR n]

Comme il peut y avoir des répétitions, des chevauchements..., ça pose quelques difficultés algorithmiques.
D’où ce code long.
Je me demande vraiment comment il faudrait faire pour que ce soit plus court. Ce code ne me satisfait pas. Mais bon, c’est pour livrer l’idée.

18/08/2010, 12h42
SSJ17Vegeta

Bonjour à tous, et avant tout merci de votre réactivité ;-)

Je vais essayer de reprendre dans l'ordre et de resituer le besoin ^^

En fait, le but est de chercher/remplacer dans une série de fichiers, récursivement à travers les répertoires. Je n'ai pas de contrainte de langage, même si je suis plus à l'aise avec PhP avec lequel j'ai l'habitude (mais qui sera probablement moins performant qu'un script Bash ou un programme C :mrgreen: ). L'intérêt des regexp ici est que c'est une solution assez générique, pour peu que l'API du langage cible gère les expressions POSIX.

Madfrix, ton algo est très intéressant, malgré le fait qu'il n'utilise pas une regexp, il est clair, et facilement adaptable pour mes besoins. Au cas où je n'aurais pas de regexp fonctionnelle pour mon cas de figure, je m'orienterai probablement vers cette solution.

eyquem, pour compléter un peu le problème que tu as soulevé dans ton premier post, j'ai effectivement à faire à des doubles crochets [[maValeur]] et des doubles accolades {{maValeur}}, toto pouvant être suivi ou précédé de n'importe quel caractère, mes excuses pour ne pas l'avoir précisé plus tôt :oops: Je teste la dernière solution que tu as exprimé et je te donne un retour ;-)
18/08/2010, 18h44
eyquem

Je pense avoir touvé une idée pour faire ce qu’il faut en 6 ou 7 lignes. Je n’ai pas eu le temps de terminer.
Je posterai ça ce soir

Pas facile comme problème.

Voici un code plus court.
Mes excuses pour ce code en Python:
- je n’arrive plus à faire tourner des programmes en PHP
- je ne connais pas suffisamment PHP pour savoir adapter ce code en PHP et si PHP en est seulement capable: il y a une fonction sub() qui fait des remplacements avec ce que lui fournit une fonction auxiliaire (ici définie à la volée mais j’aurais pu écrire chnew = re.sub('((?<=\W)|(?<=\A))(toto\d\d)(?=\W|\Z)', frempl, ch) avec la fonction frempl() définie à part)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ch = 'toto00 ab toto01 cdg[h kj toto02 toto03 mnh ] uk toto04 gt '+\ '{jh toto05 bg} fde bbfe toto06++ {ngt toto07} vu [[gtre '+\ ' gt toto08 y]]mju} hfd {ggdug toto09 fdg[ {kju toto10 sd[ ge '+\ 're ==toto11 {[toto12 ku} gf{{{ gtr [lkj toto13 bg]]]]] { ip '+\ '{ gt toto14}}[{}} gtr toto15]} [ju toto16] pa{j toto17[ toto18 '+\ 'v}fr{]{ kiu ]{kju toto19 toto20 {} toto21] fd toto22 qw [toto23 '+\ 'nhft [jku toto24 k]toto25 nb [ard toto26 pototo27 f[ru toto28] n toto29' print ch,'\n' import re pat = re.compile('|'.join(('(\[|\])', '(\{|\})', '(?:(?<=\W)|(?<=\A))(toto\d\d)(?=(?:[^\w\]][^\]]*?)?\[|\Z)', '(?:(?<=\W)|(?<=\A))(toto\d\d)(?=(?:[^\w\}][^\}]*?)?\{|\Z)', '(?:(?<=\W)|(?<=\A))(toto\d\d)(?=\W|\Z)'))) # si group(3) de pat existe, 'toto\d\d' n'est pas enferme dans des crochets # car il y a un autre '[' en aval avant le prochain ']' . # Idem pour accolades et groupe(4) dook = {'[':1 , ']':-1 , '{':1 , '}':-1 , None:0 } cro,acc,li = 0,0,[] for m in pat.finditer(ch) : cro += dook[m.group(1)] acc += dook[m.group(2)] if m.group(3) or m.group(4) or (m.group(5) and cro<1 and acc<1): li.append(m.start()) chnew = re.sub('((?<=\W)|(?<=\A))(toto\d\d)(?=\W|\Z)', lambda m: 'HELLO' if m.start() in li else m.group(), ch) print chnew
Principe:

- constitution de la liste li des positions des mots ’totoii’ ('toto00', 'toto01', 'tot02', etc) qui doivent être remplacés:
boucle for m in pat.finditer(ch) :

- substitution des mots en question par la chaîne remplaçante:
instruction re.sub(....)

Pour ces deux étapes, utilisation de regex. donc ça répond à ton souhait.

La boucle for m in pat.finditer(ch) : ne s’arrête qu’aux positions intéressantes:

- aux caractères ’[’ et ’]’ pour incrémenter cro

- aux caractères ’{’ et ’}’ pour incrémenter acc

- aux chaînes ’totoii’:
Si à cette position de la chaîne totale traitée cro<1, cela veut dire que tous les crochets ouvrant existant en amont ont été refermés par au moins le même nombre de crochets fermant existant en amont aussi, donc la chaîne ’totoii’ à la position courante n’est pas enfermée entre un crochet ouvrant et un fermant.

Idem pour les accolades.

Ces positions sont donc enregistrées.

Mais il y a des cas où quelles que soient les valeurs de cro et acc à une position de ’totoii’ , c’est à dire même s’il y a au moins un crochet ou une accolade ouvrante en amont du ’totoii’ , la position doit quand même être enregistrée car il y a un autre crochet ouvrant ’[’ (ou une accolade ouvrante ’{’) en aval avant tout crochet ou accolade fermant(e). Ce qui fait que la chaîne ’totii’ n’est de toutes les façons pas enfermée entre crochets ou accolades, dans ce cas aussi.

lambda m: 'HELLO' if m.start() in li else m.group()
est une fonction définie à la volée qui autorise un remplacement par ’HELLO’ si la position du match m examiné se trouve dans la liste li des chaînes ’totoii’ à remplacer. Sinon , le remplacement se fait avec la chaîne ’totoii’ trouvée, qui est dans m.group() , donc il n’y a en fait aucun remplacement effectif.

Je suis obligé de passer par ces complications pour une raison:
en Python, les assertions en arrière n’acceptent pas des chaînes de longueur non fixée:
(?<!\[[\]]*?) n’est par exemple pas autorisé.

Et même (?<=\A|\Z) ou (?<=[\A\W]) ne le sont pas.

D’où la nécessité de faire le compte de ce qui a précédé une chaine ’totoii’ en utilisant des objets auxiliaires cro et acc.

Si en PHP il n’y a pas cette limitation sur les possibilités des assertions en arrière, il devrait être possible d’écrire un code plus simple et plus direct.
Mais je n’arrive plus à faire tourner de programme PHP suite à une réinstallation de WAMP5 et je n’ai pas pu essayer.

Noter qu’avec les RE et l’algorithme que j’ai utilisés,
dans jhgadf [ gghfs [ hgfttrk toto45 [ gg ju ]
'toto45' n’est pas entre deux crochets ouvrant-fermant, et donc peut être remplacé.
On pourrait décider le contraire.

Bonjour,

voilà un truc tout con et qui marche :)
Le principe : quand on y arrive pas en un coup on le fait en plusieurs fois :mouarf:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 $chaine = 'dfsd toto[toto df sdtotf tOtotOTO xdf] toto titi'; $reg2 = '#\[(([^\]])*)toto(([^\]])*)\]#i'; while(preg_match($reg2, $chaine)) $chaine = preg_replace($reg2, "[$1tutu$3]", $chaine); echo $chaine; // dfsd toto[tutu df sdtotf tutututu xdf] toto titi

30/08/2010, 17h21
floanne

Bonjour.

Si tu as des chaines de ce type :

Code:

[ bla bla bla [bla bla] toto [Bla bla] ]

Alors tu n'as pas de solution en une seul regex.

Pourquoi ? Car tes expression sont régulière, donc tu ne peux pas compté les crochets pour savoir si tu es encore dans un bloc ou non. Et on voit bien dans cette exemple que si tu ne compte pas tu es mort.

Avec perl tu peux te débrouiller avec des regex récurcives mais bon tu vas te casser la tête... Et puis du coup techniquement c'est plus des regex...

Je te conseille de faire un automate où tu compte les crochets ouvrants et fermants (avec un petit compteur que tu incrémante quand tu rencontre [ et que tu décrémante quant tu rencontre ] ). Si ton compteur est à 0 tu remplace sinon non.

A plus, Florent.
01/09/2010, 15h06
s.n.a.f.u

L'exemple 3 de la page de manuel présente une fonction de remplacement récursif en php : http://fr.php.net/manual/fr/function...e-callback.php

A n'utiliser qu'en cas de possibilité de multiples crochets.
Si la profondeur est connue et fixe, il est préférable de s'appuyer sur ce paradigme.

Enfin, s'il y a le choix de l'outil, je pense que perl sera le plus puissant pour résoudre ce problème.