aide en Ocaml Arbre de HuffmanFermé

Question

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

KX · Answer

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;;

KX · Answer

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 !

KX · Answer

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épartlet 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...

Aide en Ocaml Arbre de Huffman

3 réponses

Newsletters