Planche : 1


  

Plan
  1. Table d’association/(Java : interface)
  2. Table de hachage/(Java : bibliothèque)
  3. Bonus Java

Planche : 2


Les tables d’associations

Planche : 3


La table d’association

Soit des « informations », munies d’une « clé ».


Planche : 4


La table d’association

Ensemble dynamique d’informations.

Type abstrait de données, défini par les opérations.

Et plus précisément (unicité des clés)


Planche : 5


Application

On veut produire une statistique des mots d’un texte.


Planche : 6


Conception de Freq

En trois étapes.

  1. Lire le texte mot-à-mot.
  2. Compter les occurrences des mots.
  3. Produire un bel affichage (par fréquences décroissantes).

Plus précisément.

  1. Procéder selon le principe du Reader.
  2. Par une table d’association des mots aux comptes. (clé = un mot → information = un compte).
  3. Par un tri à la fin.

Planche : 7


Lecture des mots, tri

On suppose donnés :


Planche : 8


Définition précise de notre table

Une table est un objet Assoc. C’est une table d’association des mots (String) aux int.

Spécification en Java, par une interface (commentée).

interface Assoc {
  /* Créer/remplacer l'association key → val */
  void put(String keyint val) ;
  /* Trouver l'entier associé à key, ou zéro. */
  int get(String key) ;
}

Planche : 9


Code de main
class Freq {
  …
  static void countFile(String nameAssoc t) {
    WordReader wr = new WordReader(name) ;
    count(wrt) ;
    wr.close() ;      // Fermer l'entrée (plus propre)
    Sort.println(t) ; // Affichage trié
  }

  public static void main(String [] arg) {
    countFile(arg[0], …)
  }

}

Planche : 10


Code de count
  static void count(WordReader inAssoc t) {
    for (String word = in.read() ;
         word != null ;
         word = in.read()) {
      if (word.length() >= 4) {
        word = word.toLowerCase() ;
        t.put(wordt.get(word)+1) ;
      }
    }
  }

Remarquer : Assoc n’est pas une classe, mais on peut l’utiliser comme un type, celui du deuxième argument de count.


Planche : 11


Les listes d’associations

La façon la plus simple d’associer un compte à un mot ?

Une liste de paires Stringint.

class AList {
  private String word ;
  private int count ;
  private AList next ;

  AList (String wordint countAList next) {
    this.word = word ; this.count = count ; this.next = next ;
  }
}

Attention


Planche : 12


La table avec une liste

Étant donnés un mot (Stringw et une liste d’association (AListp.

Conception « top-down » : On suppose écrite une méthode lookCell(pw) qui renvoie

On peut maintenant écrire recherche et mise à jour (get/put),


Planche : 13


Recherche

Écrivons une méthode get statique (Pourquoi ? null est une liste).



class AList {
    …
  static int get(AList pString w) {
    AList q = lookCell(pw) ;
    if (q == nullreturn 0
    else return q.count ;
  }
}

Planche : 14


Création/Mise à jour d’une association de la liste

Écrivons une autre méthode statique dans la classe AList.



  static AList put(AList pString wint c) {
    AList q = lookCell(pw) ;
    if (q == null) {
      return new AList (wcp) ;
    } else {
    q.count = c ;
    return p ;
  }}

Planche : 15


Code de lookCell
static AList lookCell(AList pString w) {
  for ( ; p != null ; p = p.next) {
     if (w.equals(p.word)) {
       return p ;
     }
  }
  return null ; // Pas trouvé
}

Remarquer le return dans la boucle, et le return après la boucle.


Planche : 16


Résumé de la classe AList
class AList {
  ⋮ // Un constructeur, la méthode lookCell
  static int get(AList pString w) { … }
  static AList put(AList pString wint count) { … }
}

Un objet de la classe AList peut-il prendre Assoc comme type ?

interface Assoc {
  int get(String key) ;
  void put(String keyint val) ;
}

Non, essentiellement parce que get et put sont des méthodes statiques de la classe AList.


Planche : 17


Il faut encapsuler
class L implements Assoc {
  private AList p ;

  L() { p = null ; }

  public int get(String w) { return AList.get(pw) ; }

  public void put(String wint c) { p = AList.put(pwc) ; }
}

Planche : 18


Bénéfice

On peut maintenant écrire :

class Freq {
  …
  public static void main(String [] arg) {
    countFile(arg[0], new L()) ;
  }
}

Deux programmeurs peuvent travailler indépendamment (l’un écrit Freq, l’autre écrit L).

  1. Leurs classes sont est compilables.
  2. L’interface les oblige à préciser leurs idées.



Mais La classe L n’est pas très efficace.


Planche : 19


Autre bénéfice (de l’interface)

Nous pouvons fabriquer une autre implémentation (H) de l’interface Assoc (plus efficace que L), et l’utiliser à la place, sans changer Freq.



Un programme de test des diverses implémentations des tables d’association :

// java Freq -L file -> liste d'association
// java Freq -H file -> autre implémentation

class Freq {
  …
  public static void main(String arg) {
    if (arg[0].equals("-L")) countFile(arg[1], new L()) ;
    else if (arg[0].equals("-H")) countFile(arg[1], new H()) ;
    …
  }
}

Planche : 20


Détour : une vue des tableaux

Nous connaissons les tableaux :

Nous pouvons donc voir un tableau comme une table d’association dont les clés sont des int dans [0…t.length[.



Limitations :


Planche : 21


Idée du hachage

Soit une clé quelconque k (pour les mots k est un String).


Planche : 22


Hachage en théorie

Lorsque h(k1) = h(k2) pour k1k2, on dit qu’il y a une collision.

Si il n’y a pas de collisions, le hachage est parfait.


Planche : 23


Idée du hachage II, résolution des collisions

On suppose donc des collisions :

∃ k  k′, k ≠ k′  et  h(k) = h(k′)

Le chaînage : la case i du tableau t contient la liste des informations (kv) avec h(k) = i.


Planche : 24


Implémentation
class H implements Assoc {
  private final static int SZ = 1024 ;
  private AList [] t ;
  H() { t = new AList [SZ] ; }

  // Fonction de hachage h.
  private int hash(String w) {
    return Math.abs(w.hashCode()) % t.length ;
  }

Planche : 25


Chercher dans bonne liste
  public int get(String w) { // Chercher dans t[h(w)]
    int i = hash(w) ;
    AList q = AList.lookCell(t[i], w) ;
    if (q == null)
      return 0 ;
    else
      return q.count ;
  }
Ajouter/Remplacer dans la bonne liste
  public void put(String wint c) {
    int i = hash(w) ;
    AList q = AList.lookCell(t[i], w) ;
    if (r == null)
      t[i] = new AList(wct[i]) ;
    else
      q.count = c ;
  }

Planche : 26


Coût du hachage

On se donne quelques hypothèses.

Alors, le coût moyen d’une recherche/ajout dans une table contenant n associations est en O(1+n/m) (admis).

Donc si m est de l’ordre de n : O(1).

On note α = n/m le facteur de charge, c’est aussi la longueur moyenne des listes de collision (intuitivement clair ?).


Planche : 27


Remarques sur le coût en O(1)

Planche : 28


Redimensionnement

Ce qui était vrai des piles/files l’est aussi des tables de hachages.

Il est pratique et normal que ce soit le code de la table de hachage qui se charge de maintenir α borné.

  private final static double alpha = 4.0 ; // borne sur la charge
  private int nbKeys = 0 ; // n (m est t.length)

  public void put(String wint c) {
    int i = hash(w) ;
    AList q = AList.lookCell(t[i], w) ;
    if (r == null) {
      t[i] = new AList(wct[i]) ;
      nbKeys++ ; // Car vient d'ajouter une association
      if (t.length * alpha <= nbKeys// La charge est trop forte
        resize() ;
    } else
      q.count = c ;
  }

Planche : 29


La méthode resize

Pour assurer un coût amorti en O(1)

Et voilà.

  private void resize() {
    AList [] old = t ;

    t = new AList [2*old.length] ; // Remplacer d'abord
    for (int i = 0 ; i < old.length ; i++) { // Copier old -> t
      for (AList p = old[i] ; p != null ; p = p.next) {
        int h = hash(p,word) ;
        t[h] = new AList (p.wordp.countt[h]) ;
      }
    }
  }

Planche : 30


Bibliothèque

Les tables de hachage sont d’un emploi très courant.

La classe de la bibliothèque est générique à deux paramètres : HashMap <K,V> (package java.util).

Le codage est des plus facile.

import java.util.* ;

class Lib implements Assoc {
  private HashMap <String,Integert ;
  Lib() { t = new HashMap <String,Integer> () ; }
  …
}

Planche : 31


Chercher, remplacer/ajouter dans un HashMap
  public int get(String w) {
   Integer c = t.get(w) ;
   if (c == null// Si pas d'assoc (w → c) t.get(w) -> null
     return 0 ;
   else
     return c ; // Compris comme 'return c.intValue()'
  }
  public void put(String wint c) {
   t.put(wc) ; // ...c....  -> ... Integer.valueOf(c) ...
  }

Et c’est tout !


Planche : 32


Performance

Faire la statistique des mots de sources Java. Temps d’exécution de count (sec.), fonction du nombre de mots lus.

On note :


Planche : 33


Et au cas où vous vous poseriez la question

Statistique des sources Java

return: 13221
static: 9666
null: 8191
string: 6672
system: 6526
void: 6007
public: 5464
else: 5376
println: 4650
private: 4216

  etc.

abandoned: 1
abba: 1
abbcdefgh: 1
ability: 1
abnormally: 1
abnorme: 1
aborted: 1

  etc.

zhoulai: 1
ziegler: 1
zones: 1
zyvabis: 1

Planche : 34


Bilan des collisions

L’efficacité provient principalement du « bon » hachage des clés.

Effectifs des listes de collisions, selon leur taille. Pour n=12904, m=4096, α=3.15.

Il a par ex. environ 900 (sur 4096) listes de collisions de taille 2.


Planche : 35


Autre exemple : linguistique récréative

Un texte sur le hachage :

Pour des clés plus générales cette façon de mélanger est critiquée, mais nous allons écrire une méthode count, qui compte le nombre d’occurrences des mots d’un texte, dans le cas du hachage modulo un nombre premier, il reste possible de calculer modulo m. Mais en fait ce n’est pas divisible par m, pour des entiers successifs, un cas aussi simple est exceptionnel en pratique.

Ce texte est « inspiré » du chapitre du poly sur les tables de hachage.

Il a été produit automatiquement, avec… une table de hachage.


Planche : 36


Un texte qui ressemble à un autre

On suppose que l’enchaînement des mots d’un texte suit un modèle de Markov.

Soit en simplifiant : deux mots w1 puis w2 déterminent le mot suivant w3 (parmi un ensemble de mots possibles).

Idée :


Planche : 37


Un algorithme
  1. w1 et w2 sont les deux premiers mots de T.
  2. Afficher w1 puis w2.
  3. Boucle :
    1. Choisir un w3 qui suit w1w2 dans T.
    2. Si w3 est « (fin) », terminer.
    3. Afficher w3.
    4. Remplacer w1 par w2, puis w2 par w3.

Planche : 38


Les suites de deux mots

Objets de la classe Prefix.

class Prefix {
  private String w1w2 ;
  Prefix (String w1String w2) {
    this.w1 = w1 ; this.w2 = w2 ;
  }

  Prefix shift(String w3) {  // (w1,w2) → (w2,w3)
    return new Prefix (w2w3) ;
  }
}

Planche : 39


Programmation
static void chain() {
  Prefix pref = …
  for ( ; ; ) { // Boucle
    String w3 = step(pref)    // Choisir le troisième mot.
    if (w3 == nullreturn ;  // pref = deux derniers mots.
    System.out.print(w3 + " ") ;
    pref = pref.shift(w3) ;
  }
}

Une seule difficulté : comment choisir le troisième mot efficacement.


Planche : 40


Choisir le troisième mot

Il nous fait une association des préfixes de deux mots de T, vers les mots suivants.

À un préfixe donné peut correspondre plus d’un mot suivant.

[…] des clés distinctes […] des clés successives […]

Donc association des objets Prefix vers par ex. les tableaux de String.

En Java.

static HashMap<Prefix,String []> h =
              new HashMap<Prefix,String []> () ;

Par la suite on suppose que la table est correctement remplie (lecture de T mot-à-mot et h.put).


Planche : 41


Programmation de step

Très facile, avec la table de hachage.

  static HashMap<Prefix,String []> h =
    new HashMap<Prefix,String []> () ;
  static Random rand = new Random () ; // Source pseudo-aléatoire

  static String step(Prefix pref) {
    String[] t = h.get(pref) ;
    return t[rand.nextInt(t.length)] ;
  }

Pour Random voir la doc.


Planche : 42


Code get de la bibliothèque

Schématiquement :

  private V[] t = … ; // tables de listes de collision.

  public V get(K key) {
    int h = Math.abs(key.hashCode()) % t.length ;
    for (AList q = t[h] ; q != null ; q = q.next) {
      if (key.equals(q.key)) return q.val ;
    }
    return null ;
  }

Méthodes hashCode et equals de nos clés (classe Prefix) ?


Planche : 43


Obscur Object

Exemple de méthode ainsi (pré)-définie pour tous les objets ?


Planche : 44


Il faut redéfinir les méthodes

Les méthodes héritées ne nous conviennent pas.

C’est la la même histoire que toString (amphi 01)


Planche : 45


Méthode equals livrée d’origine

Sa signature (type) :

public boolean equals(Object obj)

Sa sémantique (ce qu’elle fait) :

The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true).

En résumé :

new Prefix("a","b").equals(new Prefix("a","b"))false

Nous voulons l’égalité structurelle.


Planche : 46


Redéfinition de equals

Premier essai (classe Prefix).

  boolean equals(Prefix p) {
    return
      this.w1.equals(p.w1) && this.w2.equals(p.w2) ;
  }

S’agit-il d’une redéfinition de equals des Object ?

Non ! Pourquoi ?


Planche : 47


Redéfinition de equals (Object o)

Deuxième essai (classe Prefix).

public boolean equals(Object o) {
  return
    this.w1.equals(o.w1) && this.w2.equals(o.w2) ;
  // NB: w1.equals(..) et w2.equals(..), equals des String
}

Est-ce que ça fonctionne ? Non ! Que se passe-t-il ?

Refus de compiler la classe Prefix.

% javac Prefix.java
Prefix.java:15: cannot resolve symbol
symbol  : variable w1
location: class java.lang.Object
    this.w1.equals(o.w1) && ... ;                       ^

Planche : 48


Redéfinition de equals (Object o)

Dans l’essai précédent, le compilateur n’a aucun moyen de savoir que l’Object que l’on lui donne est toujours un Prefix.

Il faut le lui dire !

public boolean equals(Object o) {
 // downcast (conversion de type vers le bas)
  Prefix p = (Prefix)o ;
  return
    this.w1.equals(p.w1) && this.w2.equals(p.w2) ;
}

Que se passe-t-il avec p.equals("coucou") ?

Un échec (à l’exécution) ! Mais plus précisément ?

L’exception java.lang.ClassCastException est levée.


Planche : 49


Redéfinition de hashCode ()

Il s’agit produire un int à partir de w1 et w2 (deux String).

public int hashCode() {
// Un calcul à partir de this.w1 et this.w2
}

Pour garantir le bon fonctionnement de la table de hachage, il faut :

p1.equals(p2) entraîne p1.hashCode() == p2.hashCode()

Le mélangeur multiplicatif (par un nombre premier).

public int hashCode() {
  return
    37 * this.w1.hashCode() + this.w2.hashCode() ;
}

Inspiré du hachage des chaînes de Java.


Planche : 50


Une bonne fonction de hachage

Planche : 51


Conclusion, table de hachage

Les tables de hachage sont des tableaux généralisés.


Planche : 52


Bonus interface

put et get c’est quand même un peu juste.

Comment effectuer la dernière étape du programme Freq avec les tables de hachage de la bibliothèque ?

  1. Produire un bel affichage.



Une solution un peu plus détaillée.


Planche : 53


Récupérer l’ensemble des clés d’une table

C’est ce que fait la méthode keySet des HashMap<K,V>).

public Set<KkeySet()

Itérer sur cet ensemble, pour construire la liste, magique :

// t est la table de bibliothèque HashMap<String,Integer>
  Set<Stringkeys = t.keySet() ;
  AList r = null ;
  for (String k : keys) {
    r = new AList (kt.get(k), r) ;
  }
// r contient la liste des (w → c)

Planche : 54


Au delà de la magie

Une interface souvent utilisée : Iterator<E> (package java.util, doc), un itérateur sur une « collection » de E.

Deux méthodes intéressantes :

Usage :

  Iterator<Eit = …
  while (it.hasNext()) {
    E e = it.next() ;
    // Traiter e
  }

Planche : 55


Au delà de la magie II

De nombreuses classes de la bibliothèque (par exemple Set<E>) implémentent l’interface Iterable<E> (package java.lang, doc)

Une seule méthode :

Usage :

  Iterable<Ees = …
  Iterator<Eit = es.iterator() ;
  while (it.hasNext()) { E e = it.next() ; … }

Notation abrégée :

  Iterable<Ees = …
  for (E e : es) {
    …
  }

Planche : 56


Au delà de la magie III

Et donc :

  Set<Stringkeys = … ;
  for (String k : keys)
    r = new AList (k, t.get(k), r) ;

Est traduit par le compilateur en :

   Set<Stringkeys = … ;
// keys implémente Iterable<String>
  {
     Iterator<Stringit = keys.iterator() ;
// it est un itérateur sur les elts de keys
     while (it.hasNext()) {
        String k = it.next() ;
        r = new AList (k, t.get(k), r) ;
     }
  }

Planche : 57


Bonus magique

Tout ce passe comme si un tableau de type T [] implémentait l’interface Iterable. Plus directement,

  T [] t = … ;
  for (T v : t) {
    …
  }

Est l’expression succinte de :

  T [] t = … ;
  for (int k = 0 ; k < t.length ; k++) {
    …
  }

Planche : 58



Ce document a été traduit de LATEX par HEVEA