IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Shell et commandes GNU Discussion :

Algorithme de séparation de pavé


Sujet :

Shell et commandes GNU

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Août 2009
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2009
    Messages : 80
    Par défaut Algorithme de séparation de pavé
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : 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
    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

  2. #2
    Expert confirmé Avatar de frp31
    Homme Profil pro
    Ingénieur systèmes et réseaux
    Inscrit en
    Juillet 2006
    Messages
    5 196
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur systèmes et réseaux
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Juillet 2006
    Messages : 5 196
    Par défaut
    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.

  3. #3
    Membre très actif

    Homme Profil pro
    Responsable projets techniques
    Inscrit en
    Février 2003
    Messages
    980
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Responsable projets techniques
    Secteur : Biens de consommation

    Informations forums :
    Inscription : Février 2003
    Messages : 980
    Par défaut
    @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 : 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
    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

  4. #4
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2011
    Messages
    1 946
    Détails du profil
    Informations personnelles :
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Janvier 2011
    Messages : 1 946
    Par défaut
    Salut,

    Citation Envoyé par Alek-C Voir le message
    @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 : 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
    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
    
    $

  5. #5
    Membre très actif

    Homme Profil pro
    Responsable projets techniques
    Inscrit en
    Février 2003
    Messages
    980
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Responsable projets techniques
    Secteur : Biens de consommation

    Informations forums :
    Inscription : Février 2003
    Messages : 980
    Par défaut
    Citation Envoyé par zipe31 Voir le message
    Salut,



    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
    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
    
    $
    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 !

  6. #6
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2011
    Messages
    1 946
    Détails du profil
    Informations personnelles :
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Janvier 2011
    Messages : 1 946
    Par défaut
    Re-

    Citation Envoyé par Alek-C Voir le message
    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 )
    Citation Envoyé par Alek-C Voir le message
    L'exercice de compréhension est laissée à la charge du lecteur

  7. #7
    Membre confirmé
    Profil pro
    Inscrit en
    Août 2009
    Messages
    80
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2009
    Messages : 80
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  8. #8
    Membre très actif

    Homme Profil pro
    Responsable projets techniques
    Inscrit en
    Février 2003
    Messages
    980
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Responsable projets techniques
    Secteur : Biens de consommation

    Informations forums :
    Inscription : Février 2003
    Messages : 980
    Par défaut
    Citation Envoyé par emmachane Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.
    ...

    Autant pour moi, je me suis compliqué la vie

    Edit (j'ai ajouté un ou deux pièges quand même) :
    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
    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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 0
    Dernier message: 21/08/2014, 02h48
  2. séparation de source et algorithme DUET
    Par FrereTibius dans le forum Bibliothèques
    Réponses: 1
    Dernier message: 20/11/2012, 16h50
  3. Algorithme de séparation de texte
    Par Bash01 dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 08/01/2011, 00h26
  4. Algorithme de randomisation ... ( Hasard ...? )
    Par Anonymous dans le forum Assembleur
    Réponses: 8
    Dernier message: 06/09/2002, 14h25
  5. Algorithme génétique
    Par Stephane.P_(dis Postef) dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 15/03/2002, 17h14

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo