Aide en Ocaml Arbre de Huffman

Fermé
shankssword Messages postés 1 Date d'inscription jeudi 12 février 2009 Statut Membre Dernière intervention 12 février 2009 - 12 févr. 2009 à 18:22
KX Messages postés 16664 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 21 janvier 2023 - 24 févr. 2009 à 21:04
salut tout le monde, je suis un debutant en Ocaml. je voudrais creer une fonction qui prend en entrée un arbre de huffman et un message sous forme de liste de bits et qui rend le message codé sous forme de chaine de caractère.


type arbreHuffman = feuille of int*char
|Noeud of arbreHuffman*int*arbreHuffman

let rec decodage a l =
match l with
|[] -> (match a with
|Feuille(i,c)-> String.make 1 c
|_ -> failwith "erreur" )

|t::q -> match a with
|Feuille(i,c) -> String.make 1 c ^ decodage a q
|Noeud(g,n,d)-> if t= false then decodage g q else decodage d q

dans mon code lorsqu'on arrive a une feuille, on y reste blauqué.
est ce que vous pouvez me dire svp comment je peux faire pour revenir à la racine ?
merci d'avance

3 réponses

KX Messages postés 16664 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 21 janvier 2023 2 998
24 févr. 2009 à 20:10
Autant le dire tout de suite, je ne connais pas OCaml, alors ce qui va suivre marche avec CamlLight, il faudra juste faire la traduction en OCaml !

De plus je ne suis pas expert (à mon grand regret) alors je peux me tromper, mais quand je regarde ton code la première chose que je me dit c'est que l'imbrication des match doit posé problème...

Alors voici peut-être un début de solution :
exception erreur;;

type arbreHuffman =
|feuille of (int*char)
|noeud of (arbreHuffman*int*arbreHuffman);;

let rec decodage a l =
match l,a with
|[],feuille (i,c) -> make_string 1 c
|[],noeud x -> raise erreur
|t::q,feuille (i,c) -> (make_string 1 c)^(decodage a q)
|t::q,noeud (g,i,d) -> if t=0 then decodage g q
				              else decodage d q;;
1
KX Messages postés 16664 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 21 janvier 2023 2 998
24 févr. 2009 à 20:36
Par exemple si je fais un petit arbre (je ne sais pas trop à quoi serve les int, mais ici ça n'a pas d'importance)
let arbre=noeud(
                noeud (
                       feuille (1,`a`),
                       2,
                       feuille (1,`b`)
                       ),
                3,
                noeud (
                       feuille (1,`c`),
                       2,
                       feuille (1,`d`)
                       )
                );;
Voici ce que j'obtiens pour différents cas :
decodage arbre [0;0];;
#- : string = "a"

decodage arbre [0;1];;
#- : string = "b"

decodage arbre [1;0];;
#- : string = "c"

decodage arbre [1;1];;
#- : string = "d"

decodage arbre [0];;
#Uncaught exception: erreur

decodage arbre [1];;
#Uncaught exception: erreur

decodage arbre [0;0;0];;
#- : string = "aa"

decodage arbre [0;0;1];;
#- : string = "aa"
Il me semble que l'objet de ta question concerne les deux derniers exemples de tests, c'est à dire que tu ne veux pas voir apparaitre plusieurs fois le caractère au cas où la liste soit trop longue...
Dans ce cas il faut revenir au code et légèrement le modifier
let rec decodage a l =
match l,a with
|_,feuille (i,c) -> make_string 1 c
|[],noeud x -> raise erreur
|t::q,noeud (g,i,d) -> if t=0 then decodage g q
                              else decodage d q;;
Et si j'ai bien compris ton problème, une fois que tu auras transformer ça en OCaml, tu devrais avoir ta réponse !
0
KX Messages postés 16664 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 21 janvier 2023 2 998
24 févr. 2009 à 21:04
Peut être voulais-tu plutôt avoir (dans mon exemple) :
decodage arbre [0;1;0;0;1;0];;
#- : string = "bac"
Dans ce cas il va falloir tricher un peu en plaçant un troisième paramètre qui sera en quelque sorte la mémoire de l'arbre de départ
let rec decodage a l mem =
match l,a with
|_,feuille (i,c) -> (make_string 1 c)^(decodage mem l mem)
|[],noeud x -> ""
|t::q,noeud (g,i,d) -> if t=0	then (decodage g q mem)
				else (decodage d q mem);;

decodage arbre [0;1;0;0;1;0] arbre;;
Ici on ne met plus l'exception erreur, sinon cela ne fonctionnerait pas...
0