Tables de hachage (ou tableaux associatifs)

• Ce sont des tableaux indexés, non par des indices entiers, mais par des chaînes de caractères, appelées clés. Autrement dit, il s'agit d'un ensemble de couples (clé, valeur) dont le premier élément (clé) détermine le second (valeur scalaire). Ceci assure l'unicité des valeurs de clés.
• Les identificateurs des listes associatives sont précédés du symbole %, les éléments étant des scalaires
• Soit le hachage %hach et l'une de ses clés $cle, alors sa valeur correspondante s'obtient par $hach{$cle} (attention avec des accolades).
  Si la clé n'existe pas, on obtient la valeur undef
  Pour tester l'existence d'une clé ou d'une valeur utiliser respectivement les fonctions booléennes exits et defined :

  if (exists $hach{$cle} ) {
   ...
  if (defined $hach{$cle} ) {
  ...
  

•   Exemple 1 : création d'un hachage, d'une copie, accès aux valeurs

  #!/usr/bin/perl -w
    # déclaration d'une variable de table vide
  %tab = ();
    # définition par affectation d'une suite de couples
  %tab = ("pi" , 3.14 , "c", "300000 km.s-1", "e" , 2.72, "q", "1.6e-19 C" );
    #copie de hachages
  %mesconstantes = %tab;
    # la clé doit être entourée de ' ou ", si elle n'est pas purement alphanumérique
  print "La charge électrique d'un électron est environ $mesconstantes{q}\n";
  $expo= "e";
  print "La constante $expo vaut : $mesconstantes{$expo}\n";
  

•   Exemple 2 : capitales.pl
  Définition avec une autre notation, puis ajout et suppression d'une entrée dans la table

  #!/usr/bin/perl -w
    # autre façon plus explicite de noter les couples
  %capitales = (
          'France' => 'Paris',
          'Italie' => 'Rome',
          'Belgique' => 'Bruxelles'
          );
  print "la capitale de l'Italie est $capitales{Italie}\n";
    # ajout d'une nouvelle association (clé='Allemagne', valeur='Bonn')
  $capitales{'Allemagne'}='Bonn';
    # mise à jour de table car cette capitale a changé ...
  if (exists $capitales{Allemagne} ) {
  delete $capitales{'Allemagne'};
  $capitales{'Allemagne'}='Berlin';
  }
    # création du meme hachage par mise en correspondance de 2 listes
  @pays= qw(France Italie Belgique Allemagne);
  @cap = qw(Paris Rome Bruxelles Berlin);
  @capitales{@pays} = @cap;
  

• Fonctions s'appliquant globalement à un hachage
  
  • keys() et values() appliqués à un hachage donnent respectivement la liste des clés et la liste des valeurs.
    
  • reverse() permet d'inverser la hachage par échange des roles des clés et des valeurs (celles-ci doivent donc être uniques sinon perte d'information)
  • Chaque appel à each() fournit le couple (clé,valeur) suivant, et une liste vide quand la fin est atteinte. each() doit donc s'employer normalement dans une boucle while.
  • Exemples sur le hachage %capitales

    @pays = keys(%capitales);
    print "@pays\n";
    @capitales = values(%capitales);
    print "@capitales\n";
    %pays = reverse(%capitales);
    print "Le pays dont la capitale est Berlin est $pays{Berlin}\n";
    

• Parcourir un hachage
  Attention ! vous constatez que les couples (clé, valeur) ne sont pas rangés dans l'ordre de création, mais selon une structure interne (arbre binaire). On est donc amené à effectuer un tri suivant les clés ou les valeurs avant le parcours. Pour réinitialiser le parcours d'un hachage, on peut faire appel aux fonctions keys(%hach) ou values(%hach)

  while (($cle, $val)= each (%capitales)) {
    print " $cle => $val\n";
  }
  # idem mais en triant d'abord suivant les clés 
  foreach $cle ( sort keys(%capitales) ) {
    print "La capitale de $cle est $capitales{$cle}\n"
  }
  

• Relations entre hachage et liste
  Pour créer un hachage à partir d'une liste et l'inverse :
  %tab = @liste; crée un hachage directement à l'aide des couples formés dans l'ordre à partir de la liste
  @liste = %tab; crée une liste contenant la liste de toutes les clés suivie de la liste de toutes les valeurs du hachage.

• Tableaux associatifs prédéfinis : %ENV et %SIG
  $hote = $ENV{'HOME'};

  TP

############ comptes.pl : manipulations de hachage #############

#!/usr/bin/perl
%tab = %uid = ("jean" , 500, "toto" , 501, "stage", 502, "prof", 503);
@cles = keys(%tab);
@valeurs = values(%tab);
print "La liste des clés : @cles\n";
print "La liste des valeurs : @valeurs\n";
($cle, $val)= each(%tab);
print "Le premier couple : ($cle, $val) \n";
($cle, $val)= each(%tab);
print "Le deuxième  : ($cle, $val) \n";

print "affichage du hachage \%uid de 2 façons :\n";
print "\navec une boucle while :\n";
   ...
print "\navec une boucle foreach :\n";
   ...
print "affichage du hachage trié suivant les clés croissantes :\n";
   ...
print "affichage du hachage trié suivant les valeurs décroissantes :\n";
   ...
print "inverser \%uid en \%comptes puis l'afficher \n";
   ...
# UNIX : construire un hachage %comptes à partir de /etc/passwd
# les clés et et les valeurs sont resp. les noms (1er champ) et les n° uid (3ème champ)
%comptes=();
open P, "/etc/passwd";
while ($ligne=<P>) {
chomp($ligne);
( .. )= split(":",$ligne);
$comptes{..} = ...;
}
# affichage de %comptes
.....

############# dico.pl : utiliser un dictionnaire ###############

1. Créer un hachage dont les clés sont des mots ou des expressions courantes en français, et dont les valeurs correspondantes en sont les traductions en anglais (ou autre langue au choix !)
2. Construire une boucle TANT QUE exécutée jusqu'à ce que le mot entré au clavier soit "zzz"
3. Faire rechercher et afficher sa traduction en anglais ou le message "mot inconnu du dictionnaire"
4. Prolongement
   
   1. Le dictionnaire est stocké dans le fichier dico.txt, une ligne contenant une correspondance français anglais, avec un espace comme séparateur (ou autre)
   2. Ecrire 2 routines et les tester : lit_hachage() qui ouvre le fichier passé en paramètre et le charge dans un hachage %dico, puis ecrit_hachage() qui effectue la transformation inverse en écrivant le hachage %dico dans un fichier passé en paramètre (on pourra envisager des routines plus générales)
   3. Ecrire le script traduction.pl utilisant les 2 fonctions précédentes, puis qui ouvre un fichier contenant un texte en Français, le parcourt, et le traduit "mot à mot", le texte initial suivi de sa "traduction" étant enfin enregistrés en ajout dans le fichier traduction.txt
   4. On pourra évaluer le travail pour permettre une mise à jour du fichier dictionnaire

%dico = (
  maison => house,
  femme => wife,
  logiciel => software,
  voiture=>car
  );
......

########## nbmots.pl : compter les occurrences des mots d'un texte ##########

1. Ouvrir en lecture un texte quelconque, puis parcourir ses lignes
2. Pour simplifier on considère l'espace comme séparateur de mots sur chaque ligne
3. Si le mot courant $mot existe déjà, comme clé du hachage %compteur, incrémenter la valeur correspondante, sinon mettre le mot comme clé d'une nouvelle entrée de %compteur.
   Conseil : l'incrémentation peut se faire dans les 2 cas par : $compteur{$mot}++;. En effet cette instruction crée une nouvelle entrée avec cette clé si elle n'existe pas auparavant (en contexte chaine, la valeur est la chaine vide et en contexte numérique, c'est 0)
4. Lorsque le parcours est terminé, récapituler en affichant les mots trouvés par ordre décroissant de leur occurrence
   Pour cela, il faudra d'abord trier la liste des clés dans l'ordre décroissant des valeurs par :

   @mots_tries = sort { $compteur{$b} <=> $compteur{$a} } keys(%compteur) ;
   

   puis parcourir cette liste triée.

######### * codage_proteines.pl : traduction d'une séquence d'ADN en protéines #########

• A chaque codon, triplet des bases T,C,A,G on fait correspondre un acide aminé (constituant des protéines) ou un signal. Il y a redondance du code génétique, puisque les 4x4x4 = 64 codons possibles correspondent à 20 acides aminés.
• Pour représenter informatiquement le code génétique, il est pratique d'utiliser un hachage pour noter l'ensemble des traductions codon => acide. Ce hachage est fourni
• En fait, à partir de la chaine d'ADN, il y a une phase préalable de transcription qui donne une chaine d'ARN (par remplacement de la base T, la thymine, par U l'uracile. Cette phase est sautée ici pour simplifier.
• On demande d'écrire un programme de test de cette traduction, en complétant le fond de fichier codage_proteines.txt