let ( @@ ) f g x = f (g x);; type lettre = {l:char; f:int;};; type huff = Feuille of lettre | Branche of huff * huff;; type huffL = huff list;; type binarySeg = bool list;; let rec count = function | Feuille l -> l.f | Branche (h1, h2) -> count h1 + count h2;; let rec getFC = function | Feuille l -> l.l | Branche (h1, h2) -> getFC h1;; let cmp f h1 h2 =((f h1) < (f h2));; let insert cmp huff huffL= let rec insert acc = function | [] -> List.rev (huff::acc) | hd::lt -> if cmp huff hd then List.rev_append acc (huff::hd::lt) else insert (hd::acc) lt in insert [] huffL;; let string2huffL cmp str = let strget=String.get str in let rec f acc = function n -> if n = -1 then acc else f (insert cmp (Feuille({l=strget n;f=1})) acc) (n-1) in f [] ((String.length str)-1);; let grouper fa fb = match (fa, fb) with | (Feuille la, Feuille lb) -> (if la.l = lb.l then Feuille ({l=la.l;f=la.f + lb.f}) else Branche (fa, fb)) | _ -> Branche (fa, fb);; let grouperL cmp grouper2 liste= let rec f acc = function | [] -> acc | hd1::hd2::lt -> if (getFC hd1) = (getFC hd2) then f acc ((grouper2 hd1 hd2)::lt) else f (insert cmp hd1 acc) (hd2::lt) | hd1::[] -> insert cmp hd1 acc in f [] liste;; let rec grouperA cmp = function | hd::[] -> hd | hd1::hd2::lt -> grouperA cmp ( insert cmp (grouper hd1 hd2) lt) | _ -> failwith "?? grouperA ??";; let getArbreForString chaine = grouperA (cmp count) (grouperL (cmp count) grouper (string2huffL (cmp (int_of_char @@ getFC)) chaine)) ;; let getBinarySeq arbre c = let rec f = function | Branche (ba, bb) -> let (boola, seq)= f ba in if boola then (boola, true::seq) else let (boolb, seq)= f bb in (boolb, false::seq) | Feuille (fa) -> (fa.l=c, []) in f arbre;;
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.