Algorithme de séparation de pavé [Résolu]

[emmachane]

Bonjour,

Je cherche à mettre en place un algorithme pour tenter de résoudre le cas suivant :

Fichier en entrée composé de la séquence ci-dessous

Code :

1
2
3
4
5
6
7
8
9
10
11
 
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
...
...

Je dois isoler les pavés comme suit :

Tout pavé commençant par A et se terminant par Z doit aller dans une fichier "liste"

Tout pavé commençant par A et ne se terminant pas par Z doit aller dans une fichier "poubelle"

Tout pavé ne commençant pas par A et qui se termine par Z doit aller dans une fichier "poubelle"

Exemple
Fichier en entrée

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
-- Pavé 1
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
-- Pavé 2
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
--Pavé 3
BXXXXX
BXXXXX
ZXXXXX
-- Pavé 4
AXXXXX
BXXXXX
BXXXXX

A la sortie, je dois avoir deux fichiers :
1- fichier liste qui contiendra les pavés 1 & 2
2- fichier poubelle qui contiendra les pavés 3 & 4

Toute la difficulté ( de mon point de vue) réside dans la séquence de rupture d'un pavé.

Si vous avez une idée, ça serait avec plaisir

Bon après-midi

[frp31]

pour multiplier les manipulation sed devrait être efficace.

/du_mot/,/au_mot/commande

permettra la sélection par paragraphe

\i pour l'insertion de -- Pavé X

et jouer la redirection vers le fichier résultat.

[Alek-C]

@frp31 : je ne pense pas que cela résolve son problème (ou en tout cas, pas aussi simplement que tu le laisses entendre )... comment identifies-tu que tu es dans un pavé qui commence par A* et finit par Z* avec sed ?

@emmachane : tu dois pouvoir t'en sortir avec awk, mais pour ce genre de traitement, j'utiliserais perl que je connais mieux. Une version un peu "rapide" serait par exemple ci-dessous.

Edit : si ton problème, c'est l'algo, voici une version basique qui peut marcher

1) lecture d'une ligne
1.1) si c'est un début de pavé (commence par "-- Pav..."), est-ce que la ligne précédente commençait par Z ?
1.1.1) si oui, j'affiche le buffer
1.1.2) j'enregistre la ligne dans le buffer (en écrasant son contenu)
1.2) sinon (ce n'est pas le début d'un pavé)
1.2.1) si je détecte une erreur (par exemple : la ligne précédente était un début de pavé et la ligne courante ne commence pas par A), je vide le buffer
1.2.2) si le buffer est déjà vide, je ne le remplis pas
1.2.2) si il n'y a pas d'erreur (cf. 1.2.1) ou si on est en train de capturer un pavé (buffer non vide), je concatène la ligne courante avec le buffer
2) je mémorise la ligne lue pour pouvoir la comparer

La traduction rapide en perl :

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
$ cat pave.txt
-- Pavé 1
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
-- Pavé 2
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
-- Pavé 3
BXXXXX
BXXXXX
ZXXXXX
-- Pavé 4
AXXXXX
BXXXXX
BXXXXX
$ perl -ne  'if (/^-- Pav/) {print $text if ($oldligne=~/^Z/);$text=$_;} else {$text=($oldligne =~ /^-- Pav/ && /^A/ || $oldligne !~ /^-- Pav/ && $text)?$text.$_:"";} $oldligne=$_;' pave.txt
-- Pavé 1
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
-- Pavé 2
AXXXXX
BXXXXX
BXXXXX
ZXXXXX

L'exercice de compréhension est laissée à la charge du lecteur

[zipe31]

Salut,

Envoyé par Alek-C

@frp31 : je ne pense pas que cela résolve son problème (ou en tout cas, pas aussi simplement que tu le laisses entendre )... comment identifies-tu que tu es dans un pavé qui commence par A* et finit par Z* avec sed ?

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
61
62
$ ls                      
fich.sed  plop

$ cat plop                      
AXXXXX D1                       
BXXXXX                          
BXXXXX                          
ZXXXXX F1                       
AXXXXX D2                       
BXXXXX                          
BXXXXX                          
ZXXXXX F2                       
BXXXXX D3                       
BXXXXX                          
ZXXXXX F3                       
AXXXXX D4                       
BXXXXX                          
BXXXXX 
                         
$ cat fich.sed                  
#n

/^A/{
:z
N
$ by
/.*\nZ/! bz
w liste
}

/^A/!{
:k
N
/.*\nZ/! bk
:y
w poubelle
}

$ sed -f fich.sed plop

$ ls
fich.sed  liste  plop  poubelle

$ cat liste
AXXXXX D1
BXXXXX
BXXXXX
ZXXXXX F1
AXXXXX D2
BXXXXX
BXXXXX
ZXXXXX F2

$ cat poubelle
BXXXXX D3
BXXXXX
ZXXXXX F3
AXXXXX D4
BXXXXX
BXXXXX

$

[Alek-C]

Envoyé par zipe31

Salut,

Code :

Ouais bon, ben n'empêche que c'était pas aussi simple que ça
(j'avoue, je connais très mal sed... je vais essayer de comprendre )

Edit: et si le fichier contient des séparateurs de blocs, ça marche toujours ?
Parce que je comprends de ce que tu fais que tu chopes toutes les lignes comprises entre une ligne commençant par A et une commençant par Z. Mais moi, je comprends de son exemple que les pavés sont également délimités par un repère (les lignes avec --Pavé...), et que si ta ligne commençant par A fait partie du pavé 3 et celle finissant par Z est dans le pavé 4 (ou si la ligne commençant par A n'est pas la première du pavé 3), il ne faut rien afficher :o
C'est pour ça que je me suis un peu fait ch... en perl mais c'est sur que si ça n'est pas le cas, c'est plus simple !

[zipe31]

Re-

Envoyé par Alek-C

Ouais bon, ben n'empêche que c'était pas aussi simple que ça
(j'avoue, je connais très mal sed... je vais essayer de comprendre )

Envoyé par Alek-C

L'exercice de compréhension est laissée à la charge du lecteur

[emmachane]

Merci pour vos réponses, je vais les tester. Je souhaite apporter une précision sur le fichier en entrée. Il est identique à :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
AXXXXX                       
BXXXXX                          
BXXXXX                          
ZXXXXX                       
AXXXXX                       
BXXXXX                          
BXXXXX                          
ZXXXXX                       
BXXXXX                       
BXXXXX                          
ZXXXXX                       
AXXXXX                       
BXXXXX                          
BXXXXX

Les lignes que j'ai indiquées en "--Pavé 1,2,3,4" sont mises pour bien mettre en évidence la structure de ce fichier.

[Alek-C]

Envoyé par emmachane

Merci pour vos réponses, je vais les tester. Je souhaite apporter une précision sur le fichier en entrée. Il est identique à :

Code :

Les lignes que j'ai indiquées en "--Pavé 1,2,3,4" sont mises pour bien mettre en évidence la structure de ce fichier.

...

Autant pour moi, je me suis compliqué la vie

Edit (j'ai ajouté un ou deux pièges quand même) :

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
$ cat pave2.txt
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
CXXXXX
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
BXXXXX
BXXXXX
ZXXXXX
AXXXXX
BXXXXX
BXXXXX
AXXXXX
BXXXXX
ZXXXXX
$ perl -ne '$buf.=$_ if ($buf); $buf=$_ if (/^A/);  if (/^Z/) {print $buf; $buf=""}' pave2.txt
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
AXXXXX
BXXXXX
BXXXXX
ZXXXXX
AXXXXX
BXXXXX
ZXXXXX

[zipe31]

Les explications pour "sed" :

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
#n
Pas d'affichage

/^A/
Si la ligne commence par A

{
Début regroupement de commandes

:z
Étiquette de branchement

N
On ajoute la ligne suivant dans l'espace de travail (mémoire principale)

$ by
Si dernière ligne du fichier, se brancher à l'étiquette "y"

/.*\nZ/! bz
Si l'espace de travail ne contient pas un caractère fin de ligne suivi d'un "Z", se brancher à l'étiquette "z". Ici on joue sur la gourmandise des regex qui englobe tout ce que contient l'espace de travail jusqu'au dernier caractère de fin de ligne. 

w liste
On écrit le contenu de l'espace de travail dans le fichier "liste".

}
Fin regroupement de commandes


/^A/!
Si la ligne ne commence pas par A

{
Début regroupement de commandes

:k
Étiquette de branchement

N
On ajoute la ligne suivant dans l'espace de travail (mémoire principale)

/.*\nZ/! bk
Si l'espace de travail ne contient pas un caractère fin de ligne suivi d'un "Z", sebrancher à l'étiquette "k".

:y
Étiquette de branchement

w poubelle
On écrit le contenu de l'espace de travail dans le fichier "poubelle"

}
Fin regroupement de commandes

[emmachane]

@Alek-C
Ton code fonctionne très bien pour la génération du fichier liste . Rien ne se produit pour le fichier poubelle . Quand j'exécute le code sur le fichier :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
A2XXXX
B2XXXX
B2XXXX
Z2XXXX
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX

Ton code produit :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
 
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
A2XXXX
B2XXXX
B2XXXX
Z2XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX

En revanche, il ne met pas dans le fichier poubelle ceci :

Code :

1
2
3
4
5
6
7
 
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX

Comment ajouter le bout de code ?
Pardon, mais je n'y connais rien en langage Perl.

Merci

[emmachane]

@zipe31

J'ai testé ton code qui fonctionne très bien dans le cas cité dans le premier message . Ton programme génère bien les deux fichiers "liste" et "poubelle". J'ai voulu tester un autre cas légèrement différent :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
A2XXXX
B2XXXX
B2XXXX
Z2XXXX
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX

Le souci provient du pavé

Code :

1
2
3
4
5
 
A5XXXX
B5XXXX
B5XXXX
Z5XXXX

En fait, ce dernier est redirigé vers le fichier "poubelle" alors qu'il devrait être dans le fichier "liste".

Navré de vous demander à tous les deux une solution toute faite mais c'est tellement proche du but.

Merci encore

[zipe31]

Re-

Essaie avec ça (les changements dans "fich.sed" sont en gras et rouge) :

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
$ cat plop 
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
A2XXXX
B2XXXX
B2XXXX
Z2XXXX
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX

$ cat fich.sed 
#n

/^A/{
:z
h
N
$ by
/.*\nA/ {
x
by
}
/.*\nZ/! bz
w liste
}

/^A/!{
:k
N
/.*\nZ/! bk
:y
w poubelle
}

g
/.*\nA/ {
s/.*\n\(A.*\)/\1/
bz
}
d

$ sed -f fich.sed plop 

$ cat liste 
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
A2XXXX
B2XXXX
B2XXXX
Z2XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX

$ cat poubelle 
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX

$

[Alek-C]

Effectivement, dans mes exemples, j'ai oublié le fichier poubelle.

Mais il faudrait avoir toutes les règles de gestion d'un seul coup si on veut avoir une solution définitive

1) est ce que 2 lignes A peuvent se suivre ?
2) est ce que 2 lignes Z peuvent se suivre ?
3) est ce qu'un pavé commence par le premier A ou le second si plusieurs se suivent (idem pour la fin du pavé)
4) est ce qu'un pavé peut contenir une ligne commençant par A ou Z (je crois que non) ?

Si on dit qu'un pavé commence par une ligne A et se termine par une ligne Z en n'ayant aucune ligne A ou Z entre les 2, cet algo devrait marcher :

1) lecture ligne
1.1) si ligne commence par A, alors on met le buffer dans poubelle (si non vide) et on écrase le contenu du buffer avec la ligne
1.2) sinon si ligne commence par Z, alors on ajoute la ligne au buffer
1.2.2) si buffer commence par A (ce qui veut dire qu'on a au moins une ligne qui commence par A et une qui commence par Z), on le met dans liste
1.2.2) sinon, on le met dans poubelle
1.2.3) on vide le buffer dans tous les cas puisqu'il a été affiché
1.3) sinon (ligne ne commence ni par A ni par Z), on ajoute la ligne au buffer

c'est plus simple que mon premier algo car il n'y a pas les "pavés" à gérer

en perl, ça donne ça (j'ai utilisé la sortie d'erreur pour le fichier poubelle et la sortie standard pour liste, d'où la redirection de chaque sortie dans les fichiers correspondants) :

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
$ cat pave3.txt
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
A2XXXX
B2XXXX
B2XXXX
Z2XXXX
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX
$ perl -ne 'if (/^A/) {print STDERR $buf if ($buf); $buf=$_} elsif (/^Z/) {$buf.=$_; if ($buf =~ /^A/m) {print STDOUT $buf} else {print STDERR $buf};$buf=""} else {$buf.=$_};' pave3.txt 1> liste 2>poubelle
$ cat liste
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
A2XXXX
B2XXXX
B2XXXX
Z2XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX
$ cat poubelle
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX

[frp31]

Envoyé par zipe31

Re-

Essaie avec ça (les changements dans "fich.sed" sont en gras et rouge) :

Code :

après le bloc sed utilisé pour le fichier liste il faut ajouter
pour créer le séparateur
/^A/ i ---------

ou un post traitement

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[fpu@ln ~/tmp] sed '/^A/ i ---' liste
---
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
---
A2XXXX
B2XXXX
B2XXXX
Z2XXXX
---
A5XXXX
B5XXXX
B5XXXX
Z5XXXX
 
[fpu@ln ~/tmp] rm liste

[emmachane]

@Alek-C

1) est ce que 2 lignes A peuvent se suivre => Oui

2) est ce que 2 lignes Z peuvent se suivre => Oui

3) est ce qu'un pavé commence par le premier A ou le second si plusieurs se suivent (idem pour la fin du pavé) => Non

4) est ce qu'un pavé peut contenir une ligne commençant par A ou Z (je crois que non) ? Non

[zipe31]

Salut,

Envoyé par frp31

après le bloc sed utilisé pour le fichier liste il faut ajouter
pour créer le séparateur
/^A/ i ---------

ou un post traitement

Je ne pense pas que ce soit demandé

[Alek-C]

Envoyé par emmachane

@Alek-C

1) est ce que 2 lignes A peuvent se suivre => Oui

2) est ce que 2 lignes Z peuvent se suivre => Oui

3) est ce qu'un pavé commence par le premier A ou le second si plusieurs se suivent (idem pour la fin du pavé) => Non

4) est ce qu'un pavé peut contenir une ligne commençant par A ou Z (je crois que non) ? Non

La question 3 n'attend pas un oui ou un non comme réponse mais je pense avoir saisi :p normalement, le script perl ci-dessous devrait passer avec ces cas particuliers :

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
$ cat pave3.txt
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
Z1XXXX
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX
A5XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX
$ perl -ne 'if (/^A/) {print STDERR $buf if ($buf); $buf=$_} elsif (/^Z/) {$buf.=$_; if ($buf =~ /^A/m) {print STDOUT $buf} else {print STDERR $buf};$buf=""} else {$buf.=$_};' pave3.txt 1> liste 2>poubelle
$ cat liste
A1XXXX
B1XXXX
B1XXXX
Z1XXXX
A5XXXX
B5XXXX
B5XXXX
Z5XXXX
$ cat poubelle
Z1XXXX
B3XXXX
B3XXXX
Z3XXXX
A4XXXX
B4XXXX
B4XXXX
A5XXXX

[zipe31]

Explications concernant le rajout au script "sed" :

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
#n

/^A/{
:z
h
On copie le contenu de la mémoire principale dans la mémoire annexe.

N
$ by
/.*\nA/ {
Si l'espace de travail contient un caractère fin de ligne suivi d'un "A"
Toujours pareil, on joue sur la gourmandise des regex qui englobe tout ce 
que contient l'espace de travail jusqu'au dernier caractère de fin de ligne. 


x
On échange le contenu des 2 mémoires

by
Et on se branche à l'étiquette "y"

}

/.*\nZ/! bz
w liste
}

/^A/!{
:k
N
/.*\nZ/! bk
:y
w poubelle
}

g
On écrase le contenu de la mémoire principale avec le contenu de la mémoire annexe.

/.*\nA/ {
Si l'espace de travail contient un caractère fin de ligne (le dernier sur la ligne) suivi d'un "A"

s/.*\n\(A.*\)/\1/
On ne garde que la partie après le caractère fin de ligne.

bz
Et on se branche à l'étiquette "z".

}
d
Dans le cas contraire on efface la mémoire principale et on entame un nouveau cycle.

[emmachane]

On avance bien Alek-C

Le programme perl ne résout malheureusement pas le cas :

Tout pavé encadré par :
- une ligne de début qui démarre avec un A
- une ligne de fin qui ne démarre pas par un Z

Ce cas correspond à ce que j'ai mentionné dans mon premier message, à savoir : Tout pavé commençant par A et ne se terminant pas par Z doit aller dans une fichier "poubelle"

@zipe31
Quand je lande le programme fich.sed, le terminal me renvoie le message :
"sed : /.*\nZ/! bz dans une commande reconnue"

nb : je suis sous Solaris et le sed n'est pas forcément à jour.

[zipe31]

Envoyé par emmachane

@zipe31
Quand je lande le programme fich.sed, le terminal me renvoie le message :
"sed : /.*\nZ/! bz dans une commande reconnue"

nb : je suis sous Solaris et le sed n'est pas forcément à jour.

Arf

Euh... et hier ça marchait ? C'est bizarre ça

C'est le message d'erreur original ?