Huffman : arbre et chaine de binaire

Commenter

Contenu du snippet 

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

Compatibilité : ObjectiveCaml

Disponible dans d'autres langages :

A voir également

S'inscrire maintenant

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.

Du même auteur (coucou747)