Secteur TAL Informatique,
Université Sorbonne nouvelle, Paris 3
19 rue des Bernardins, 75005 Paris
Secteur TAL Informatique, Université Sorbonne nouvelle, Paris 3

BaO4 :
Des Textes Aux Graphes


 

Liens

Retour page du cours.

Présentation  du travail


A l'issue du travail fait dans la séance Boîte à Outils Série 3 vous avez appris à extraire des suites de tokens correspondant à des patrons morpho-syntaxiques prédéfinis. Dans cette séance, le travail à faire doit conduire à construire des graphes donnant à voir ces patrons.

Exemple de données utilisées ici en entrée ( cf infra "travail à faire étape 2") : Aurélia a construit ce fichier de termes à partir de ce fichier de patrons (via Treetagger)

L'objectif de cette séance est de prendre appui sur ce type de liste de termes pour construire des graphes. Pour illustrer ce travail, nous commençons par présenter les outils et les formats de données utilisées pour construire ces graphes. On présente ensuite le travail à faire sur les listes de termes issues de la Boîte à Outils Série 3.

Les graphes : format des données à utiliser


Exemple 1 dit "Hawaï"


Exemple construit à partir de "Les routes dans les îles Hawaï" {Alfred Aho and Jeffrey Ullman, Concepts fondamentaux de l'informatique, Dunod, 1993}

Les graphes à construire doivent être construits au format graphml.

GRAPHML : http://graphml.graphdrawing.org/
GraphML is a comprehensive and easy-to-use file format for graphs. It consists of a language core to describe the structural properties of a graph and a flexible extension mechanism to add application-specific data. Its main features include support of

  • directed, undirected, and mixed graphs,
  • hypergraphs,
  • hierarchical graphs,
  • graphical representations,
  • references to external data,
  • application-specific attribute data, and
  • light-weight parsers.
Unlike many other file formats for graphs, GraphML does not use a custom syntax. Instead, it is based on XML and hence ideally suited as a common denominator for all kinds of services generating, archiving, or processing graphs.

(lien vers fichier de test au format graphml)

<?xml version="1.0" encoding="iso-8859-1"?>
<graphml>
 <key id="d0" for="node" attr.name="nom" attr.type="string"/>
 <key id="d1" for="edge" attr.name="poids" attr.type="double"/>
 <graph edgedefault="undirected">
     <node id="1"><data key="d0">Maili</data></node>
     <node id="2"><data key="d0">Wahiawa</data></node>
...
    <edge source="1" target="2"><data key="d1">15.0</data></edge>
    <edge source="1" target="3"><data key="d1">20.0</data></edge>
    <edge source="2" target="3"><data key="d1">12.0</data></edge>
 </graph>
</graphml>

Pour un noeud est fourni un identifiant (forcément un entier pour Pajek, et l'étiquette comme contenu de l'élément data. Pour une arête, sont fournis les identifiants de ses noeuds de départ et d'arrivée et son étiquette (ici le poids) comme contenu de l'élément data. La feuille de style GraphML2Pajek.xsl transforme le graphe ainsi représenté vers le format Pajek (cf infra) :

(lien vers fichier au format Pajek)

*Vertices 13
1 "Maili"
2 "Wahiawa"
...
1 2 15.0
1 3 20.0
2 3 12.0
...

Pajek permet ensuite de construire le graphe :

Graphe Hawai

Figure 1 : Graphe via Pajek

Exemple 2 dit "Prématurés" : les attirances avec l'information mutuelle dans le corpus Prématurés


Les outils utilisés


PAJEK (disponible au LABO/ILPGA)


Hypertoire : http://vlado.fmf.uni-lj.si/pub/networks/pajek/
Mode d'emploi : http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf

Pajek est un logiciel développé par V. Batagelj et A. Mrvar, qui permet de traiter des données de réseaux de grande taille. Sur le site, vous aurez la possibilité de télécharger gratuitement le logiciel, son mode d'emploi et de vous abonner à la mailing list qui lui est consacrée

Pajek

Figure 2 : Interface de Pajek - Construction d'un graphe (clic sur l'image pour agrandir)

PROCESSEURS XSLT


Objectif : Transformer un document XML via une feuille de styles XSLT . Application : transformer un document graphml pour Pajek

1. Saxon


Hypertoile : http://saxon.sourceforge.net/

(à récupérer ici : programme SAXON pour windows)

Mode d'emploi :

ME saxon

Figure 3 : Lancement de saxon (clic sur l'image pour agrandir)
2. AltovaXSLT


Processeur développé par Altova 

(à récupérer ici AltoXSLT.zip ou là)

Mode d'emploi :

ME altova

Figure 4 : Lancement de AltovaXSLT (clic sur l'image pour agrandir)
3. AltovaXML 2006


Hypertoile : http://www.altova.com/altovaxml.html

Mode d'emploi :

Dans la ligne de commandes, tapez :

AltovaXML -xslt1 xsltfile -in xmlfile [-out outputfile] [options]

AltovaXML –xslt2 xsltfile -in xmlfile [-out outputfile] [options]

4. XMLCooktop (disponible au LABO/ILPGA)


Hypertoile : http://www.xmlcooktop.com/

Mode d'emploi :

Tout se passe dans l’interface proposée par l’outil :


c1

Figure 5 : XMLCooktop - Chargement du fichier XML (clic sur l'image pour agrandir)
c2

Figure 6 : XMLCooktop - Chargement du fichier XSL (clic sur l'image pour agrandir)
c3

Figure 7 : XMLCooktop - Application du processeur XSLT et visualisation du résultat (clic sur l'image pour agrandir)
5. XMLShell (disponible au LABO/ILPGA)


Hypertoile : http://www.softgauge.com/downloads.htm

Mode d'emploi :

Tout se passe dans l’interface proposée par l’outil :

x1

Figure 8 : XMLShell - Chargement du fichier XML (clic sur l'image pour agrandir)
x2

Figure 9 : XMLShell - Lancement du processeur XSLT (attention sortie TXT ici)
x3

Figure 10 : XMLShell - Visualisation du résultat (clic sur l'image pour agrandir)

Travail à faire

Etape n°1 : prise en main des outils

  1. Récupérer les ressources de Test fournies (Hawaï)
  2. A partir du graphe Hawai.xml et de la feuille de styles GraphML2Pajek.xsl, construire le fichier au format Pajek via un processeur XSLT de votre choix
  3. Charger ensuite ce fichier dans Pajek et demander à celui-ci de vous construire le graphe.

Etape n°2 : les patrons dans les fils

  1. Vous devez commencer par "mettre la main" sur les listes de token produites dans la BàO série 3 (avec Cordial et TreeTagger). Par exemple celle présentée supra, construite par Aurélia à partir de ce fichier de patrons (via Treetagger) : fichier de termes
  2. Vous devrez ensuite transformer cette liste de patrons au format graphml. Pour cela vous devrez utiliser le programme perl patron2graphml.pl, celui-ci prend en entrée une liste de patrons (argument 0 du programme) et il construit en sortie un fichier au format graphml
    Exemple d'utilisation : perl patron2graphml.pl liste-de-token.txt
    • Ce que fait ce programme :
      algo

      Figure 11 : patron2graphml (clic sur l'image pour agrandir)

    • Texte du programme patron2graphml.pl :

      • #!/usr/bin/perl
      <<DOC;
      FEVRIER 2006
      usage : perl patron2graphml.pl liste-de-token.txt
      Le programme prend en entrée le nom du fichier contenant les patrons
      à traiter (des blancs entre les termes du patron)
      Le programme construit en sortie un fichier au format graphml
      DOC
      #-------------------------
      # definitions de variables
      #-------------------------
      my $file="$ARGV[0]";
      my %listeMot={};
      my %listePatron={};
      #-------------------------
      # Partie 1
      # A. ouverture du fichier des patrons : ce fichier contient sur chaque ligne une sequence : mot1 mot2
      # B. dans la boucle while qui suit on va reperer pour chaque mot (a gauche du patron)
      # l'ensemble des mots associés (a droite du precedent)
      # on cree ensuite un tableau indexe qui associe au mot de gauche la liste des mots associes
      # motgauche -> (motdroite-1,motdroite-2,...)
      # on n'ajoute qu'une seule occurrence des mots presents a droite mais on compte
      # la frequence d'un patron donne dans un tableau de patron
      #-------------------------
      open(F,$file);
      while (my $ligne=) {
        $ligne=~/([\w]+)[^\w]+([\w]+)/;
        my $mot1=$1;
        my $mot2=$2;
        print "M1 : $mot1\n";
        print "M2 : $mot2\n";
        my $patron="$mot1\t$mot2";
        if (!(exists($listeMot{$mot1}))) {
          my @tmp=();
          push(@tmp,$mot2);
          $listeMot{$mot1}=\@tmp; # principale difficulté de ce script : construction d'un référence vers un tableau
          print "FM : $listeMot{$mot1}\n";
          $listePatron{$patron}++;
        }
        else {
          my $tmp=$listeMot{$mot1};
          my @tmp2=@$tmp;
          if (!(grep(/$mot2/, @tmp2))) {
            push(@tmp2,$mot2);
          }
        $listeMot{$mot1}=\@tmp2; # idem
        print "NM : $listeMot{$mot1}\n";
        $listePatron{$patron}++;
        }
      }
      close(F);
      #print %listeMot,"\n";
      #-------------------------
      # Partie 2
      # A. Creation du fichier de sortie et squelette minimal
      # B. parcours du tableau des associations motgauche -> (motdroite-1,motdroite-2,...)
      # pour chaque motgauche on cree un noeud du graphe idem pour chaque mot de la liste associee
      # afin de ne pas creer de doublon on utilise un tableau contenant pour chaque mot son indice
      # on verifie dans ce tableau la presence ou non du mot a associer a un noeud
      #-------------------------
      open (F,">patron-graphml.xml");
      print F "<?xml version=\"1.0\" encoding=\"iso-8859-1\"?>\n";
      print F "<graphml>\n";
      print F " <key id=\"d0\" for=\"node\" attr.name=\"forme\" attr.type=\"string\"/>\n";
      print F " <key id=\"d1\" for=\"edge\" attr.name=\"frequence\" attr.type=\"double\"/>\n";
      print F " <graph edgedefault=\"undirected\">\n";
      my $id=1;
      my $listeId={};
      while (($mot, $liste) = each(%listeMot)) {
        my @tmp=@$liste; # ici, on "reconstruit" le tableau à partir de la référence
        print "$mot\t@tmp\n";
        if ($mot !~/HASH/) {
         my $tmpID;
         if (!(exists($listeId{$mot}))) {
          print F " <node id=\"$id\"><data key=\"d0\">$mot</data></node>\n";
          $listeId{$mot}=$id;
          $tmpID=$id;
          $id++;
         }
         else {
          $tmpID=$listeId{$mot};
         }
         foreach my $cible (@tmp) {
          my $nbpatron=0;
          $patron="$mot\t$cible";
          $nbpatron=$listePatron{$patron};
          if (!(exists($listeId{$cible}))) {
           print F " <node id=\"$id\"><data key=\"d0\">$cible</data></node>\n";
           $listeId{$cible}=$id;
           print F " <edge source=\"$tmpID\" target=\"$id\"><data key=\"d1\">$nbpatron</data></edge>\n";
           $id++;
          }
          else {
           print F " <edge source=\"$tmpID\" target=\"$listeId{$cible}\"><data key=\"d1\">$nbpatron</data></edge>\n";
          }
         }
        }
      }
      print F " </graph>\n";
      print F "</graphml>\n";
      close(F);

    • En savoir plus sur les références en Perl :

      • La notion de référence en résumé : (source : http://perl.enstimac.fr/DocFr/perlreftut.html)
      Une des caractéristiques nouvelles les plus importantes de Perl 5 a été la capacité de gérer des structures de données compliquées comme les tableaux multidimensionnels et les tables de hachage imbriquées. Pour les rendre possibles, Perl 5 a introduit un mécanisme appelé "références" ; l'utilisation de celles-ci est le moyen de travailler avec des données complexes structurées en Perl... Une référence est un scalaire qui fait référence à un tableau entier ou à une table de hachage entière (ou à à peu près n'importe quoi d'autre).
      Règle de construction 1
      Si vous mettez un \ devant une variable, vous obtenez une référence à cette variable.
      $tref = \@tableau; # $tref contient maintenant une référence
      # à @tableau
      $href = \%hachage; # $href contient maintenant une référence
      # à %hachage
      Une fois que la référence est stockée dans une variable comme $tref ou $href, vous pouvez la copier ou la stocker ailleurs comme n'importe quelle autre valeur scalaire :
      $xy = $tref; # $xy contient maintenant une référence
      # à @tableau
      $p[3] = $href; # $p[3] contient maintenant une référence
      # à %hachage
      $z = $p[3]; # $z contient maintenant une référence
      # à %hachage
      Règle de construction 2
      ELEMENTS ] crée un nouveau tableau anonyme, et renvoie une référence à ce tableau. { ELEMENTS } crée une nouvelle table de hachage anonyme et renvoie une référence à cette table.
      $tref = [ 1, "toto", undef, 13 ];
      # $tref contient maintenant une référence à un tableau
      $href = { AVR => 4, AOU => 8 };
      # $href contient maintenant une référence à une table de hachage
      (la suite)

  3. Une fois, le fichier au format graphml obtenu (en suivant notre exemple précédent, le fichier obtenu ressemble à ça : patron-graphml.xml), (1) vous appliquerez la feuille de styles GraphML2Pajek.xsl sur ce fichier, (2) et enfin vous chargerez le résultat dans Pajek (en suivant toujours notre exemple précédent, on obtient ceci en amont de Pajek : sortie-patron-2.txt) pour obtenir un graphe de ce type :
Pajek

(clic sur l'image pour agrandir) | (Le même graphique au format PDF)

Figure 12 : Des Textes (des fils) Aux Graphes (via Pajek)

Mode d'emploi pour obtenir le graphe précédent (vous pourrez tester d'autres options) :
1. Charger le fichier sortie-patron-2.txt dans Pajek, option Network (cf figure supra)
2. Dessiner le graphe via l'option Draw
3. Enfin, dans le graphe obtenu, choisir : Layout>Energy>Fruch...>3D. Vous pourrez ensuite ajuster les noeuds à la main...


 

Affichage de la "valeur" des arcs : i.e. la fréquence des patrons :
On peut ensuite (après avoir parcouru la documentation de Pajek) choisir d'afficher la fréquence des patrons ainsi représentés :
Pour cela, on va dans Option>Lines>Mark Lines>With Values et on obtient le graphe suivant :

Pajek

(clic sur l'image pour agrandir) | (Le même graphique au format PDF)

Figure 13 : Des Textes (des fils) Aux Graphes (fréquence des patrons) (via Pajek)

Pour finir, on donne à voir ici, le graphe construit à partir des fils RSS du journal Le Monde (19.11.2005 - 26.02.2006), extraction des patrons NOM ADJ (via treetagger) :

13000 patrons

Figure 14 : Des Textes (des fils) Aux Graphes : Fils Le Monde, NOM ADJ (plus de 13000 occurrences de patrons) (clic sur l'image pour agrandir)

Les données utilisées pour construire ce graphique sont disponibles ici : fils-monde-191105-260206 (la sortie treetagger, le fichier graphml, le format pajek).