RICM4
Recherche d'Information Multimédia
TP 1 & 2 - Loi de Zipf

1. But du TP

Manipuler une collection de documents avec le langage PERL et illustrer empiriquement la loi de Zipf. Le langage PERL est un langage interprété basé sur les langages C, sed, awk et shell (sh). Il prend en charge les expressions régulières dans sa syntaxe permettant de remplacer des scripts shell qui peuvent devenir vite illisibles.
PERL est typé statiquement de façon simple avec un premier caractère non alphanumérique (appelé sigil) comme premier caractère d'un identificateur de variable. Ainsi comme pour les shells Unix

Le sigil $ dénote une variable scalaire;
```
my $x;
my $b = -10;
my $z = "bonjour";
```
le sigil @ dénote une variable tableau;
```
my @tab = (3.5,-5);   # déclaration et initialisation
$t[0] = -4;           # affectation d'un élément
print "$t[0]\n";      # affichage d'un élément
```
Les fonctions de manipulation de tableaux sont :
- Ajout et suppression à gauche
  - La fonction unshift prend en arguments un tableau et une liste de valeurs scalaires ; ces valeurs sont ajoutées au début du tableau :
    unshift(@tab,5,6); @tab vaut alors la liste (5,6,3.5,-5).
  - La fonction shift prend un tableau en argument ; elle supprime son premier élément (les autres sont alors décalés) et renvoie cet élément : $e=shift(5,6,3.5,-5)
    $e vaut alors 5 et @tab la liste (6,3.5,-5).
- Ajout et suppression à droite
  - La fonction push prend en argument un tableau et une liste de valeurs scalaires ; ces valeurs sont ajoutées à la fin du tableau : push(@tab,1,2)
    @tab vaut alors la liste (6,3.5,-5,1,2).
  - La fonction pop prend un tableau en argument ; elle supprime son dernier élément et renvoie cet élément : $e=pop(@tab)
    $e vaut alors 2 et @tab la liste (6,3.5,-5,1).

le sigil % dénote une variable de hashage;


my %ha = ( key1     => val1,
           key2     => val2 );

* Fonctions très utiles :

La fonction split prend en paramètres un séparateur et une chaîne de caractères ; elle renvoie la liste des éléments de la chaîne de caractères délimités par le séparateur.
```
 @tab=split(/:/,"1:4:-1:5"); => @tab=(1,4,-1,5)
```
La fonction join prend en paramètre un scalaire et une liste ; elle renvoie une chaîne de caractères comportant les éléments de la liste, concaténés et séparés par ce premier paramètre scalaire.
```
 $e=join("|",@tab); => $e="1|4|-1|5"
```

* Les structures de contrôles sont les mêmes qu'en langage C avec la même syntaxe.
* Le mot-clef sub permet de définir des fonctions en Perl. Les arguments d'une fonction sont des valeurs scalaires et elles sont accessibles via le tableau @_


sub FonctionTest {
   my ($a,$b,$c) = @_;
   ... instructions ...
   return $x;
}

=> Appel: FonctionTest(1,4,-1);

* Pour ouvrir un fichier open(HANDLE,"Chemin/Nom de fichier");
* Pour lier une variable à une expression régulière, il faut utiliser l'opérateur =~ => Guide de programmation PERL; expressions régulières

2. Déroulement

On considère la collection de documents CACM qui contient les titres, auteurs et résumés (lorsque ces derniers sont disponibles) d'un ensemble d'articles scientifiques, ainsi qu'un ensemble de requêtes et de jugements de pertinence. L'ensemble des documents est disponible à l'adresse suivante:
http://ir.dcs.gla.ac.uk/resources/test_collections/cacm/
Le répertoire contient 6 fichiers, cacm.all, cite.info, common_words, qrels.text, query.text et README. Ce dernier contient des informations sur les fichiers précédents. La collection contient 3204 documents, dont le texte est disponible dans le fichier cacm.all. Dans ce fichier, chaque document est séparé par une balise .I (suivie de l'identificant du document) qui contient le titre du documents (balise .T), les auteurs (balise .A), la date de publication (balise .B), l'abstract (balise .W), des mots-clefs (balise .K) ainsi que d'autres informations que nous ignorerons (en particulier des informations par rapport aux articles cités dans la balise .X). Certaines informations (par exemple abstract ou mots-clefs) peuvent ne pas être disponibles pour certains documents. le fichier query.text contient le texte des requêtes. Chaque requête est précédée d'une balise .I (suivi de l'identifiant de la requête), le texte de la requête est contenu dans la balise .W, la balise .N donne l'auteur de la requête (à ignorer). Certaines requêtes sont données avec une balise .A qui représente des auteurs spécifiques pour les articles à renvoyer. Le fichier qrels.text contient les identifiants des documents pertinents pour les requêtes. Chaque ligne donne un couple d'idientifiants (requête, document pertinent pour la requête). Ce fichier sera utile pour l'évaluation qu'on verra plus tard. Enfin, le fichier common_words contient les mots fréquents de la collection, et nous servira de stop-list. Le fichier cite.info contient des informations relative au codage des citations (balise .X) dans le fichier cacm.all. Ce fichier est ignoré dans la suite.

Pour chaque balise .I, la fonction suivante extrait les contenu des balises .T, .A, .W et .B en les mettant dans un fichier portant le nom CACM-XX où XX est le numéro associé à la balise .I


sub ExtractionDesFichiers($$)
{
   my ($FileName,$Path)=@_; # Tableau des paramètres 
   open(F,$FileName) || die "Erreur d'ouverture du fichier $FileName\n";
   my $str="";
   my $Num=0;

   open(COL,">$Path/Collection") || die "Erreur de creation de Collection\n";
   while(!eof(F)){
     if($str =~m /\.I\s/){ # On regarde si s$tr contient la chaîne .I
        close(NF);
        $str =~s/\.I\s//g; # Dans $str, on supprime la chaîne .I avant le numéro de document
        $Num=$str;
        print COL "CACM-$Num\n";
        print "Processing ... CACM-$Num\n";
        open(NF,">$Path/CACM-$Num");
     }
     if(($str=~ m/\.T/) || ($str=~ m/\.A/) || ($str=~ m/\.W/) || ($str=~ m/\.B/)) { # Si $str contient une des balises que l'on veut 
        $Go=1;
        while($Go==1){  # Tant que l'on ne rencontre pas une nouvelle balise
           chop($str=<F>);
           if(($str eq "\.W") || ($str eq "\.B") || ($str eq "\.N") || ($str eq "\.A") || ($str eq "\.X") || ($str eq "\.K") || ($str eq "\.T") || ($str eq "\.I")){
             $Go=0;
             break;
           }
           else{
             print NF "$str "; # On écrit le contenu dans le fichier CACM-XX
           }
        }
     }
     else{
       chop($str=<F>);
     }
  }
  close(F);
}

Écrire une fonction qui ouvre les fichiers CACM-XX un à un et qui pour chaque fichier, filtre tous les caractères non-alphanumérique et écrit le résultat (en minuscule) dans un autre fichier portant le même nom et avec l'extension .flt en plus.
Indication: On pourra utiliser la fonction PERL lc et le filtre suivant
$I =~ s/(\,|\=|\/|\.|\?|\'|\(|\)|\_|\$|\%|\+|\[|\]|\{|\}|\&|\;|\:|\~|\!|\@|\#|\^|\*|\||\<|\>|\-|\\s|\\)//g;
Calculer la fréquence d'apparition de tous les termes de la collection et les ordonner par le nombre d'apparition décroissant. Plotter le rang de ces termes n fonction de leur nombre total d'apparition. La loi de Zipf est-elle vérifiée visuellement? Quelle est dans ce cas la valeur de la constante liant le rang au nombre d'apparition, d'après cette loi?
Calculer le nombre moyen d'apparition du terme le plus fréquent dans les documents et comparer le à la valeur estimée par la loi de Zipf.