Arbres non binaires, tries

Arbres non binaires

On va considérer ici les arbres d'arité quelconque avec des listes d'enfants pour les nœuds.

type 'a arbre = { 
    etiquette : 'a; 
    enfants : 'a arbre list 
}

Afin d'effectuer des tests, on pourra considérer l'arbre suivant :

let t = { etiquette = 1;
    enfants = [ 
        { etiquette = 2; enfants = [
            { etiquette = 5; enfants = [] }
            ] };
        { etiquette = 3; enfants = [
            { etiquette = 6; enfants = [
                { etiquette = 10 ; enfants = []}
            ]};
            { etiquette = 7; enfants = []}
        ] };
        { etiquette = 4; enfants = [
                { etiquette = 8; enfants = []};
                { etiquette = 9; enfants = []}
        ] }
    ] }

qui correspond à la représentation :

Comme présenté dans le cours, on peut réaliser des fonctions mutuellement récursives pour travailler avec ces arbres et sur la forêt induite par les enfants d'un nœud :

let rec taille_arbre a =
    1 + taille_foret a.enfants
and taille_foret l = match l with
    | [] -> 0
    | t::q -> taille_arbre t + taille_foret q

Question 1. Écrire une fonction hauteur_arbre : 'a arbre -> int qui calcule la hauteur d'un arbre sur le modèle de la fonction précédente. On fera attention au fait qu'il n'est pas possible de représenter l'arbre vide mais la forêt vide jouera le même rôle vis-à-vis de \(-1\).

Corrigé

let rec hauteur_arbre a =
    1 + hauteur_foret a.enfants
    and hauteur_foret l = match l with
    | [] -> -1
    | t::q -> max (hauteur_arbre t) (hauteur_foret q)

Sur l'arbre d'exemple, on obtient 3.

Question 2. À l'aide d'un parcours récursif, écrire une fonction affiche_etiquettes : int arbre -> unit qui affiche toutes les étiquettes d'un int arbre.

Corrigé

let rec affiche_etiquettes a =
    Printf.printf "%d\n" a.etiquette;
    affiche_foret a.enfants
    and affiche_foret l = match l with
        | [] -> ()
        | t::q -> affiche_etiquettes t; affiche_foret q

Représentation par des arbres binaires

On va maintenant revenir sur la représentation d'un 'a arbre en tant qu'arbre binaire. Pour cela, on va avoir besoin d'étiquettes factices pour les nouveaux nœuds qui ne servent qu'à supporter la structure des nœuds d'arité \(>2\). On va ainsi les représenter par des 'a option arbre_bin où l'étiquette None sera celle des nœuds factices.

type 'a arbre_bin = Noeud of 'a arbre_bin * 'a * 'a arbre_bin | Nil

Question 3. On va commencer par écrire une fonction peigne : 'a option arbre_bin list -> 'a option arbre_bin qui va transformer une forêt d'arbres binaires en sa représentation en peigne à l'aide de nœuds d'étiquettes None.

Note Dans le cas où la liste est vide, on renverra l'arbre vide et si c'est un singleton, on renverra directement l'arbre qu'il contient.

Corrigé

let rec peigne l =
    match l with
    | [] -> Nil
    | [x] -> x
    | a::q -> Noeud(a, None, peigne q)

Question 4. Écrire une fonction convert : 'a arbre -> 'a option arbre_bin qui va réaliser la conversion vue en classe : le premier enfant devient le fils gauche et les enfants suivants, rassemblés en peigne, le fils droit.

Corrigé

let rec convert a =
    match a.enfants with
    | [] -> Noeud (Nil, Some a.etiquette, Nil)
    | a1::q -> Noeud(convert a1, Some a.etiquette, 
            peigne (List.map convert q))

Afin de tester votre fonction, on vous donne une fonction d'affichage textuel d'un tel arbre :

let rec print_arbre_bin pref t =
    match t with
    | Nil -> Printf.printf "%snil\n%!" pref
    | Noeud(g,x,d) -> Printf.printf "%s%s\n%!" pref 
                (match x with None -> "*" | Some n -> string_of_int n);
        print_arbre_bin (String.make (String.length pref) ' ' 
                        ^ "|" ^ String.make 5 '-') g;
        print_arbre_bin (String.make (String.length pref) ' ' 
                        ^ "|" ^ String.make 5 '-') d

L'affichage de print_arbre_bin "" (convert t) doit correspondre à la représentation suivante, où \(\star\) est un nœud factice d'étiquette None :

Arbre binaire obtenu par conversion ; $\star$ (violet) est le nœud factice d'étiquette None.

Tries

On considère les tries vus en classe, on définit ici un type spécifique :

type trie = {
    mot : bool;
    enfants : (char * trie) list
    }

• Le champ mot va permettre d'indiquer si le nœud finit un mot (l'\(\star\) de la représentation) ou non.
• Le champ enfants présente la liste des enfants avec l'étiquette de l'arête qui y mène.

Par exemple, le trie suivant, vu en cours, représente l'ensemble de mots bar, barbe, art, ami, abri, abricot, abonne :

Premières manipulations

Question 5. Écrire une fonction taille : trie -> int qui renvoie le nombre de nœuds d'un trie et une fonction nb_mots : trie -> int qui renvoie le nombre de mots d'un trie. On s'inspirera directement des fonctions de la première partie du TP.

Corrigé

let rec taille a = 
    1 + taille_foret a.enfants
    and taille_foret l = match l with
        | [] -> 0
        | (_, t) :: q -> taille t + taille_foret q
let rec nb_mots a = 
    (if a.mot then 1 else 0) + nb_mots_foret a.enfants
    and nb_mots_foret l = match l with
        | [] -> 0
        | (_, t) :: q -> nb_mots t + nb_mots_foret q

Sur le trie précédent, on obtient 21 nœuds et 7 mots.

Question 6. Écrire une fonction trie_apres_char telle que l'appel à trie_apres_char l c renvoie Some t' s'il y a un couple (c, t') dans la liste l et None sinon. On pourra s'en servir avec trie_apres_char t.enfants c pour trouver le trie potentiel dont l'arête est étiquetée par c.

Corrigé

let rec trie_apres_char (l:(char * trie) list) (c:char) =
    match l with
    | [] -> None
    | (c',t)::q -> if c = c' then Some t else trie_apres_char q c

Question 7. En déduire une fonction contient : trie -> string -> bool qui teste si un mot est présent dans le trie.

Corrigé

let contient (t:trie) (s:string) : bool =
    let rec aux t i =
        if i = String.length s
        then t.mot
        else match trie_apres_char t.enfants s.[i] with
            | None -> false
            | Some t' -> aux t' (i+1)
    in aux t 0

Question 8. Écrire une fonction enumere : trie -> string list qui renvoie tous les mots contenus dans un trie par un parcours récursif.

Indication : on pourra utiliser :

• List.concat pour passer d'une liste de listes à la concaténée de ses éléments. Ainsi List.concat [ [1;2]; [3]; [4;5] ] va renvoyer [1;2;3;4;5].
• String.make 1 c transforme le caractère c en chaîne de caractères.
• On rappelle que ^ permet de concaténer deux chaînes.

Corrigé

let enumere (t:trie) =
    let rec aux t acc = 
        let l = List.concat (List.map (fun (c,t') -> 
                aux t' (acc ^ String.make 1 c)) t.enfants) in
        if t.mot then acc :: l else l
    in aux t ""

Ajout d'un mot à un trie

Pour effectuer l'ajout d'un mot à un trie, on va commencer par écrire une fonction qui, étant donnés une chaîne de caractères \(s = c_0 \dots c_{n-1}\) et un entier \(i\le n\), va renvoyer le trie t correspondant à la branche :

Branche du trie pour le suffixe $c_i \dots c_{n-1}$ ; $\star$ marque la fin du mot.

c'est-à-dire le trie ne contenant que le mot \(c_i \dots c_{n-1}\) (le mot vide si \(i = n\)).

Question 9. Écrire la fonction suffixe : int -> string -> trie.

Corrigé

let rec suffixe (i:int) (s:string) : trie =
    let n = String.length s in
    if i = n
    then { mot = true; enfants = [] }
    else { mot = false; enfants = [ (s.[i], suffixe (i+1) s) ] }

Question 10. Écrire une fonction avec_trie_pour_char : (char * trie) list -> char -> trie -> (char * trie) list telle que avec_trie_pour_char l c t renvoie la liste obtenue en remplaçant (c,t') par (c,t) dans l si un tel couple est présent, ou en ajoutant le couple (c,t) à la fin sinon.

Corrigé

let rec avec_trie_pour_char l c t =
    match l with
    | [] -> [ (c, t) ]
    | (c', t') :: q -> if c = c' then (c, t) :: q else (c', t') :: avec_trie_pour_char q c t

Question 11. Écrire une fonction ajoute : trie -> string -> trie qui renvoie le trie obtenu en ajoutant un nouveau mot.

Corrigé

let ajoute t s =
    let n = String.length s in
    let rec aux t i =
        if i = n
        then { t with mot = true }
        else let t' = match trie_apres_char t.enfants s.[i] with
                    | None -> suffixe (i+1) s
                    | Some t' -> aux t' (i+1) in
            { t with enfants = avec_trie_pour_char t.enfants s.[i] t' }
    in aux t 0

On va utiliser la fonction précédente pour retrouver le trie donné en début de partie, avec trie_of_list ["bar"; "barbe"; "art"; "ami"; "abri"; "abricot"; "abonne"] :

let rec trie_of_list l = match l with
    | [] -> { mot = false; enfants = [] }
    | s::q -> ajoute (trie_of_list q) s

On va maintenant récupérer une grande liste de mots dans le fichier dictionnaire_fr (un mot par ligne).

let dictionnaire = let rec lit_fichier f =
        try
            let s = input_line f in
                s :: lit_fichier f
            with End_of_file -> []
        in
        lit_fichier (open_in "dictionnaire_fr")

Question 12. En déduire un trie permettant de représenter ce dictionnaire et comparer :

• le nombre de caractères total ;
• le nombre de nœuds du trie.

Que peut-on en déduire ?

Est-ce vraiment précis comme comparaison ?

Corrigé

Le dictionnaire contient 605 835 mots, soit 7 585 815 caractères en comptant les sauts de ligne, et le trie possède 2 681 196 nœuds : le partage des préfixes divise par presque 3 le nombre de « cases ».

La comparaison n'est pas précise : un caractère occupe un octet alors qu'un nœud du trie est un enregistrement contenant un booléen, une liste de couples, des pointeurs… En mémoire, le trie occupe en réalité bien plus de place que le texte.

On va essayer d'améliorer l'estimation précédente en stockant le trie dans un fichier.

Question 13. Pour cette question, on va écrire un fichier binaire contenant le trie, on parle de sérialisation.

Allez voir les documentations des fonctions suivantes : open_out_bin, output_char, output_byte.

On va écrire un trie ainsi :

• un octet qui contient \(mot + arite\) où \(mot = 0\) si ce n'est pas un mot et \(128\) sinon et \(arite\) est l'arité du nœud qu'on supposera toujours \(< 128\)

• pour chaque enfant

  • le caractère de l'arête
  • l'écriture de l'enfant (écriture récursive donc)

• En faisant cela, comparez les tailles des deux représentations du dictionnaire.

• Comparez avec un zip du dictionnaire.
• Est-ce décevant ?

Corrigé

let rec ecrit_trie out t =
    let arite = List.length t.enfants in
    assert(arite < 128);
    output_byte out ((if t.mot then 128 else 0) + arite);
    List.iter (fun (c,a) ->
        output_char out c;
        ecrit_trie out a) t.enfants

let sauve_trie nom t =
    let out = open_out_bin nom in
    ecrit_trie out t;
    close_out out

Chaque nœud occupe un octet, plus un octet pour l'arête qui y mène (sauf la racine), soit \(2 \times 2\,681\,196 - 1\) octets : le fichier fait environ 5,4 Mo contre 7,6 Mo pour le texte. Un zip du dictionnaire fait environ 2 Mo : notre représentation, qui n'exploite que le partage des préfixes, est nettement moins bonne qu'un algorithme de compression généraliste (qui exploite aussi les suffixes communs et les fréquences des lettres, voir le TP sur le codage de Huffman).