|
|
|
|
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
Configuration: Linux Firefox 3.0.5
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 !
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;;La confiance n'exclut pas le contrôle |
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 !
La confiance n'exclut pas le contrôle |
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... La confiance n'exclut pas le contrôle |
A quel arbre capturer goinfrex version diamant Algorithme de huffman java Animal crossing arbres a clochettes Arbre de talent destruction Arbre detourer photoshop Arbre genealogique gratuit Arbre généalogique vierge Arbre généalogique vierge gratuit Arbres généalogiques a remplir Créer arbre généalogique Dessin arbre généalogique Huffman Image d'un arbre genealogique Install ocaml on linux Mon arbre généalogique Paf 4 arbres généalogique Toit pour cabane dans les arbres Y a t'il obligation d'avoir des arbres dans un lotissement