Plan

Ce cours a été donné par Georges Gonthier.

Types enregistrement
Types paramétrés
Listes associatives
Recherche en table
Hachage
Listes de collision
Adressage ouvert
Hachage multiple

Types enregistrement

C'est le pendant en CAML des record de Pascal ou des struct de C.

Déclaration:


type point = {x:int; y:int};;

Attention ceci définit un nouveau type.

Utilisation:


let translate p dx dy = 

  {x=p.x+dx; y=p.y+dy};;

Attention les noms de champs (x, y ici) ne peuvent être partagés.

On peut aussi utiliser le filtrage:


let translate {x=px; y=py} dx dy =
  {x=px+dx; y=py+dy};;

Plusieurs des types prédéfinis de CAML ( tableaux, listes mais aussi tuples et fonctions) sont paramétrés: pour les utiliser il faut préciser avec quels types leurs valeurs sont construites. Ainsi on n'a pas de type ``liste'', mais des listes d'entiers (int list), de flottants, etc. Les types enregistrement, définis par l'utilisateur, ne sont pas paramétrés en général, mais peuvent l'être:

type complex = {re:float; im:float};;
type 'a monome = {exp: int; coeff: 'a};;
type 'a polynome = {monomes: 'a monome list};;

Ainsi on a:

let p1 = {monomes= [{exp=2; coeff=5};
                    {exp=1; coeff=2}]};;
p1 : int polynome = ...
let p2 = {monomes=
            [{exp=3; coeff={im=0.0;re=3.0}};
             {exp=0; coeff={im=1.0;re=0.0}}]};;
p2 : complex polynome = ...

Attention cependant il n'y a pas de type paramétré général ``enregistrement''.

Listes associatives

Ce sont des listes dont les éléments servent à ranger une valeur sous une clé permettant de les retrouver.

type elem = {cle:int; val: int list};;
let rec afind k = function
  e :: al -> if e.cle = k then e.val else afind k al
| [ ]     -> [ ];;

On peut utiliser des a-listes modifiables pour gérer un répertoire:

type entree = {nom: string;
               mutable adresse: string list}
and  repertoire = {mutable entrees: entree list};;
let modif n a r =
   let rec loop = function
     e :: al ->
       if e.nom = n then e.adresse <- a else loop al
   | [ ] ->
       r.entrees <- {nom=n; adresse=a}::r.entrees
   in loop r.entrees;;

Recherche en table

Si le nombre d'entrées est prévisible, on peut ranger les éléments dans un tableau au lieu d'une liste:

type table = {mutable nb:int; tab: elem vect};;
let ajout k v t =
  let j = ref 0 in
  while !j < t.nb && t.tab.(!j).cle <> k do
    j := !j+1
  done;
  if !j = t.nb then t.nb <- !j+1 else ();
  t.tab.(!j) <- {cle=k; val=v};;

Si les éléments sont rangés par clé croissante, on peut faire une recherche dichotomique, en O(log n) au lieu de O(n).

let dicho k t =
  let rec cherche g d =
    if d <= g then [ ]
    else let m = (g+d) / 2 in
         let km = t.tab.(m).cle in
         if km = k then t.tab.(m).val
         else if km > k then cherche g m
         else cherche (m+1) d
  in cherche 0 t.nb;;

Si on connaît la répartition, on peut même faire une recherche par interpolation, en O(log log n).

Hachage

Généralisation de la table directement indexée par la clé, impraticable quand il y a trop de clés possibles.

Idée: on range l'élément de clé c en position h(c) dans [0,M-1], où h est une fonction ``aléatoire''.

Prérequis: avoir une ``bonne'' fonction h.
Solution, si c est une chaîne de caractères: h(c) = (c.[1] * B^{n-1} + c.[2] * B^{n-2} + ... + c.[n]) mod M

let hache m b s =
  let h = ref 0 in
  for i = 0 to string_length(s) - 1 do
    h := (!h*b + int_of_char s.[i]) mod m
  done;
  !h;;

Il est bon de choisir M premier, et B = 128 ou B = 256 pour faire une multiplication rapide.

Hachage et collisions

Si h(i)=h(j) ``par hasard'', que faire?
Plusieurs solutions:

Hachage avec listes de collision

Hachage avec adressage ouvert

Hachage à 2 niveaux avec adressage ouvert

Hachage avec chaînage

Hachage multiple

Hachage pour cache

Listes de collision

On hache dans un tableau de a-listes

type eltabhash = {m:int; eltab: entree list vect};;
let mkltab m = {m=m; eltab=make_vect m [ ]};;
let lookup n {m=m; eltab=t} =
   let i = hache m 128 n in
   let rec loop = function
      e :: l ->
        if e.nom = n then e.adresse else loop l
   |  [ ] ->
        [ ]
   in loop t.(i);;
let insert n a {m=m; eltab=t} =
   let i = hache m 128 n in
   let rec loop = function
      e :: l ->
        if e.nom = n then e.adresse <- a else loop l
   |  [ ] ->
        t.(i) <- {nom=n; adresse=a}::t.(i)
   in loop t.(i);;

Complexité en O(n/m).

Adressage ouvert

On range directement les entrées dans le tableau, et en cas de collision on fait une bête recherche linéaire. Il faut pouvoir borner le nombre maximum d'entrées. On utilise une valeur spéciale pour repérer les cases libres.

type otabhash = {m:int; etab: elem vect};;
let elemVide = {cle=(-1); val=[ ]};;
let estVide t i = t.(i) == elemVide;;
let mkotab m = {m=m; tab=make_vect m elemVide};;
let insert k v {m=m; etab=t} =
   let i = ref (k mod m) in
   while not estVide t (!i) && t.(!i).cle <> k do
     i := (!i+1) mod m
   done;
   t.(!i) <- {cle=k; val=v};;

La complexité ne dépend que du taux d'occupation alpha=n/m, et vaut:
1/2 (1+1/1-alpha^2) (pour une insertion ou une recherche avec échec),
1/2 (1+1/11-alpha) (pour une recherche avec succès).

Pour alpha=66%, on fait 5 et 2.
Pour alpha=90%, on fait 50 et 5.

Pour accélerer on peut faire un double hachage, en augmentant i par pas de u=h2(k), où h2 est une seconde fonction de hachage, au lieu de pas de 1.

On fait alors (1/1 - alpha) et (1/alpha) ln (1/11-alpha), soit
pour alpha = 80%, 5 et 1,3;
pour alpha = 99%, 100 et 5.

Hachage multiple

On peut hacher une grande table (dictionnaire par exemple) de d mots par k fonctions h_i indépendantes, 1 <= i <= k. Et on prend un grand tableau T de n bits où T[j]=1 si h_i(v)=j pour v dans le dictionnaire et 1 <= i <= k.

La probabilité pour qu'aucun mot d'un dictionnaire de taille d ne positionne un T[j] donné est

p = e^(-alpha) (où alpha = d k / n.)

La probabilité pour qu'un v arbitraire soit dans le dictionnaire est (1 - p)^k. Ce qui se minimise pour d=25000, n=400000, k=11 en 0.000458711.

C'est la méthode utilisée par la commande spell de Unix.