lastsseldon : OK, je vais essayer d'améliorer mon code avec tes conseils.
Fondamentalement, ce n'est qu'une expérience pour illustrer le concept de compression par dictionnaire. A priori, la décompression pourrait se faire en stockant le dictionnaire puis en s'en servant, mais, pour les gros fichiers, ça risque de prendre une place assez énorme.
Je pense qu'il est possible de reconstituer le dico au fur et à mesure de la décompression. On parcourt les codes compressés et on sort la chaine, tout en reconstituant le dico au fur et à mesure. Dans ce cas, le seul dico qu'il te faut stocker est celui de départ, mais on peut très bien faire une convention est utiliser toujours le même.
Sinon, t'as pas un conseil pour pouvoir aérer ce genre de code ? Je le trouve trop concentré.
J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.
Tu m'évites de me farcir la partie GraphViz (chuis un bon feignant moi : je lance l'idée et je laisse bosser les autres... quel escroc ! ) !
Pour tes améliorations sur le code Io, je suis bien d'accord, c'est plus clair (et juste...) comme ça. Juste, ta méthode atAndRemove fait exactement comme la méthode native des listes : atRemove (retour de la valeur supprimée). Pour la méthode makeHuffTree, on pourrait la donner au prototype Tree plutôt qu'à treeList, et encapsuler toute la partie de code associé à treeList dedans, histoire d'être plus propre et transparent :
Pas qu'il y ait de quoi être fier d'avoir codé un RLE mais sur demande de Dark-Side, je vous poste le mien, écrit pour donner tort au tuto de Natim qui disait qu'il fallait 150 lignes de C pour coder un RLE. j0r.
#include <limits.h>
#include <stdio.h>
int main(void)
{
int c, n, x;
for (n = 1, x = getchar(); c = getchar(), x != EOF;)
n = c==x && n<UCHAR_MAX ? n+1 : (printf("%c%c", n, x), x = c, 1);
return 0;
}
Il y avait un bogue infâme dans mon implémentation du codage de Huffman (merci bluestorm). Ne l'exécutez pas .
Mais bref, n'épiloguons pas (esquive spottaid), voici le nouveau code, qui marche très bien (a priori ).
#!/usr/bin/perl
use strict;
use warnings;
use GraphViz;
# Make the tree from the input string
sub make_tree {
my (%frq, @trees);
$frq{$_}++ for (split //, shift);
push @trees, { val => $_, wgt => $frq{$_} } for (keys %frq);
while ($#trees > 0) {
@trees = sort { $a->{wgt} <=> $b->{wgt} } @trees;
my ($t1, $t2) = (shift @trees, shift @trees);
push @trees, { 1 => $t1, 0 => $t2, wgt => $t1->{wgt} + $t2->{wgt} };
}
return $trees[0];
}
# Make the hash letter => code from the input tree
sub make_dict {
my ($tree, $dict, $path) = @_;
if (exists $tree->{val}) {
$dict->{ $tree->{val} } = $path;
} else {
make_dict ($tree->{$_}, $dict, ($path.$_)) for ('0','1');
}
}
# Encode the input string, returning the encoded string and the tree
sub encode {
my ($input, $result) = (shift, '');
my $tree = make_tree $input;
my $dict = {};
make_dict $tree, $dict, '';
for (split //, $input) {
$result .= $dict->{$_};
}
return ($result, $tree);
}
# Decode the input string with the tree, returning the decoded string
sub decode {
my ($input, $tree) = @_;
my ($result, $current) = ('', $tree);
for (split //, $input) {
$current = $current->{$_};
if (exists $current->{val}) {
$result .= $current->{val};
$current = $tree;
}
}
return $result;
}
# Create a DOT graph from the input tree
sub tree2dot_aux {
my ($t, $cur, $g, $cnt) = @_;
my $count = $$cnt;
if (exists $t->{val}) {
$g->add_node($$cnt, label => "'$t->{val}'\nweigth: $t->{wgt}\ncode: $cur",
shape => 'box');
} else {
$g->add_node($$cnt, label => "weigth: $t->{wgt}");
for ('0', '1') {
$$cnt++;
$g->add_edge($count => $$cnt, label => $_);
tree2dot_aux ($t->{$_}, ($cur.$_), $g, $cnt);
}
}
}
sub tree2dot {
my $tree = shift;
my $graph = GraphViz->new();
$graph->add_node('root', shape => 'octagon', label => "root\nweigth: $tree->{wgt}");
my $count = 0;
for ('0', '1') {
$graph->add_edge ('root' => $count, label => $_);
tree2dot_aux ($tree->{$_}, $_, $graph, \$count);
$count++;
}
return $graph;
}
## Main
undef $/;
my $input = <>;
my $tree = make_tree $input;
my $graph = tree2dot $tree;
print $graph->as_png;
Et pour rigoler, voici l'arbre qu'on pourrait obtenir avec le code de mon implémentation : (Attention, c'est une image maxi giant).
( Prelude )
: not postpone 0= ; immediate
: foreach over + swap ;
: incr 1 swap +! ;
: reset 0 swap ! ;
( Lists )
: cons here >r , , r> ;
: car @ ;
: cdr cell+ @ ;
: null? nil = ;
: singleton? dup null? if drop true else cdr null? then ;
: dolist postpone >r postpone begin postpone r@ ; immediate
: repeatlist postpone repeat postpone r> ; immediate
: car@ postpone r@ postpone car ; immediate
: cdr! postpone r> postpone cdr postpone >r ; immediate
: pop postpone car@ postpone cdr! ; immediate
: copy-lst dolist null? not while pop cons repeatlist drop ;
: reverse nil swap copy-lst ;
: append reverse copy-lst ;
( Tuples )
: mktuple swap cons ;
( Occurences )
create alphabet 255 cells allot
: alpha cells alphabet + ;
: init 255 0 do i alpha reset loop ;
: fill init foreach do i c@ alpha incr loop ;
: cmp-weight cdr swap cdr < ;
: lower dup null? if drop false else car cdr >r over cdr r> > then ;
: insert nil rot dolist lower while pop cons repeatlist rot cons swap reverse append ;
: on-tuple >r dup alpha @ dup 0= if drop drop r> drop else mktuple r> execute then ;
: to-lst nil 255 0 do i ['] insert on-tuple loop ;
: occurences init fill to-lst ;
( Huffman Tree )
: mktree here >r , , , , r> ;
: mkleaf nil nil rot dup cdr swap car mktree ;
: val @ ;
: weight cell+ @ ;
: lbranch 2 cells + @ ;
: rbranch 3 cells + @ ;
: leaf? val null? not ;
: couple 2dup weight swap weight + 0 mktree ;
: inithuff nil swap dolist null? not while pop mkleaf cons repeatlist drop reverse ;
: mkhufftree inithuff dolist singleton? not while pop pop couple r> swap insert >r repeatlist car ;
( Encodage )
: char-append rot rot here >r >r r@ foreach ?do i c@ c, loop c, r> 1+ r> swap ;
: left-go [char] 0 char-append ;
: right-go [char] 1 char-append ;
: .leaf.path ." '" val emit ." ' = " type cr ;
: .code dup leaf? if .leaf.path else >r 2dup left-go r@ lbranch recurse right-go r> rbranch recurse then ;
: huffcode occurences mkhufftree s" " rot cr .code ;
Exemple d'utilisation :
$ gforth huffman.fs
redefined fill GForth 0.5.0, Copyright (C) 1995-2000 Free Software Foundation, Inc.
GForth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
s" go go gophers" huffcode
' ' = 000
'r' = 0010
's' = 0011
'g' = 01
'o' = 10
'h' = 1100
'p' = 1101
'e' = 111
ok
ZOMG.
PS: 70 lignes, pour un langage extrèmement bas niveau, je trouve ça assez impressionant perso (surtout que je dois coder super mal, c'est mon premier vrai code en Forth )
Hum, les deux codes ont presque le même nombre de chars, la version Perl en a un poil plus. Après y'a surement moyen de simplifier ça, et il ne font pas exactement la même chose d'après ce que j'ai compris.
Bon, j'avais rien à faire ce soir, et j'ai donc codé un RLE histoire d'apporter ma pierre à l'édifice . Ce RLE, j'ai choisi un langage plutôt... spécial pour le programmer : SNUSP.
Si c'est pas beau ça... . SNUSP est un langage proche du brainfuck, mais dans lequel on programme en deux dimensions. J'ai programmé un interpréteur de Bloated SNUSP (une des normes de SNUSP existant aujourd'hui) en Python pour tester mon programme, et il fonctionne impecablement . Bref, j'ai compressé le code de mon programme en utilisant RLE, et magie :
$ time python snusp.py test.snusp < test.snusp > test.snusp.compressed
python snusp.py test.snusp < test.snusp > test.snusp.compressed 50,33s user 0,31s system 96% cpu 52,316 total
$ stat test.snusp | grep Size
Size: 1606 Blocks: 8 IO Block: 4096 fichier régulier
$ stat test.snusp.compressed | grep Size
Size: 1092 Blocks: 8 IO Block: 4096 fichier régulier
Conclusion : SNUSP c'est magique... et ça se compresse bien en RLE .
EDIT: Cadeau... j'ai codé le décompresseur avec, et à ma grande joie c'est de loin plus simple que le compresseur .
wgmpgp, c'est énorme. J'avais déjà vu des snippets de ce langage sur Wikipédia... Mais aucun de cette « ampleur ». À quand une version 3D ?
Sinon, j'ai terminé mes devoirs pour mon encodeur, voici ce que ça donne :
module CompressionDico where
import Data.Map as Map
lzwLike::String->String->Map String Int->[Int]
-- Compresser une chaine vide revient a une chaine vide
lzwLike [] [] _ = []
-- Si le buffer est vide, on charge un caractere et on reprend la compression
lzwLike [] (hd:tl) dico = lzwLike [hd] tl dico
-- Si le contenu du buffer est dans le dico, on charge 1 caractère de plus dans
-- le buffer et on continue. Sinon, on sort le code dico du début du buffer et
-- on ajoute le buffer au dico.
lzwLike mot (hd:tl) dico = case Map.lookup mot dico of
Just x -> lzwLike (hd:mot) tl dico
Nothing -> dico ! (tail mot) : lzwLike [head mot] (hd:tl) nouvoDico
where nouvoDico = insert mot (size dico + 1) dico
-- S'il ne reste plus rien après le buffer, on compresse ce dernier cara par
-- cara. Ne devrait pas arriver, mais on sait jamais.
lzwLike mot [] dico = case Map.lookup mot dico of
Just x -> [x]
Nothing -> dico ! [head mot] : lzwLike (tail mot) [] dico
C'est un peu plus light à lire comme je voulais, et ça devrait être clairement plus rapide (vu que les last, init & co ont cédé leur place aux head, tail & co, on passe de O(N) a O(1)).
Pour la décompression, je sais pas encore par contre. Quelqu'un aurait une idée pour générer automatiquement un dico « de base » à partir du contenu ?
J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.
C'est vrai qu'un SNUSP en 3D serait très marrant . Par contre, je vous laisse le soin de coder ça vous même, ainsi que l'implémentation de huffman en SNUSP .
Non, tu peux écrire N matrices 2D de NxN à la suite. Et après « regrouper » ça en 3D. Et puis on pourrait même essayer de faire un éditeur avec OpenGL, etc.
Si on a même plus le droit de dire des conneries de temps en temps...
J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.
J'ai empêché personne de dire des conneries Je faisais juste la réflexion que ça n'était pas très crédible, quoique sûrement faisable (et encore, ça doit être bien chaud ).
Bon, vu que personne n'a encore évoqué la compression par dictionnaire, je m'y mets. Voici ce que j'ai, en Haskell :
module CompressionDico where
import Data.Map as Map
lzwLike::String->String->Map String Int->[Int]
-- Compresser une chaine vide revient a une chaine vide
lzwLike [] [] _ = []
-- Si le buffer est vide, on charge un caractere et on reprend la compression
lzwLike [] (hd:tl) dico = lzwLike [hd] tl dicco
-- Si le contenu du buffer est dans le dico, on charge 1 caractère de plus dans
-- le buffer et on continue. Sinon, on sort le code dico du début du buffer et
-- on ajoute le buffer au dico.
lzwLike mot (hd:tl) dico =
if findWithDefault (-1) mot dico /= (-1)
then lzwLike (mot ++ [hd]) tl dicco
else dico ! (init mot) : lzwLike [(last mot)] (hd:tl) nouvoDico
where nouvoDico = insert mot (size dico + 1) dico
-- S'il ne reste plus rien après le buffer, on compresse ce dernier cara par
-- cara. Ne devrait pas arriver, mais on sait jamais.
lzwLike mot [] dicco =
if findWithDefault (-1) mot dico /= (-1)
then [dico ! mot]
else dico ! [head mot] : lzwLike (tail mot) [] dico
La fonction lzwLike (qui est une compression dictionnaire basique qui s'inspire de l'idée générale de lzw, d'où le nom) prend en paramètre le buffer, la chaine à compresser et le dictionnaire. Vous pouvez par exemple l'appeler comme ça :
chaine vaut alors [1, 2, 3, 3]. Vous pouvez faire une fonction pour appeler lzwLike plus facilement :
compression [] _ = []
compression s d = lzwLike "" s d
Mais c'est pas franchement utile.
J'ai pas testé en profondeur, y'a donc probablement des erreurs. Mais le principal problème de ce code (comme tous mes codes Haskell) est qu'il est assez crade et probablement trop verbeux. Si vous avez mieux...
Pour les générations futures, voici le code de GuilOooo avant qu'il tente (ou pas) de réécrire l'histoire.
edit : deuxième partie :
module CompressionDico where
import Data.Map as Map
lzwLike::String->String->Map String Int->[Int]
-- Compresser une chaine vide revient a une chaine vide
lzwLike [] [] _ = []
-- Si le buffer est vide, on charge un caractere et on reprend la compression
lzwLike [] (hd:tl) dico = lzwLike [hd] tl dico
-- Si le contenu du buffer est dans le dico, on charge 1 caractère de plus dans
-- le buffer et on continue. Sinon, on sort le code dico du début du buffer et
-- on ajoute le buffer au dico.
lzwLike mot (hd:tl) dico = case Map.lookup mot dico of
Just x -> lzwLike (hd:mot) tl dico
Nothing -> dico ! (tail mot) : lzwLike [head mot] (hd:tl) nouvoDico
where nouvoDico = insert mot (size dico + 1) dico
-- S'il ne reste plus rien après le buffer, on compresse ce dernier cara par
-- cara. Ne devrait pas arriver, mais on sait jamais.
lzwLike mot [] dico = case Map.lookup mot dico of
Just x -> [x]
Nothing -> dico ! [head mot] : lzwLike (tail mot) [] dico
Je suis débutant mais je me lance, en Fortran 90; sur l'algorithme RLE.
Je sais que c'est un langage méconnu (puisque démodé), mais un petit code comme celui-ci devrait être compréhensible par tous...
PROGRAM Main
implicit none;
character(len=1024) :: str
read '(a)', str
call compress(trim(str))
END PROGRAM Main
SUBROUTINE compress(str)
implicit none;
character(len=*) :: str
character :: ch
integer :: i, n, a = 1
n = len(str)
ch = str(1:1)
do i=2, n
if (ch == str(i:i)) then
a = a + 1
else
print '(i0, a, $)', a, ch
a = 1
endif
ch = str(i:i)
enddo
print '(i0, a)', a, ch
END
Je ne suis pas satisfait de ma solution. Écrire le dernier caractère à la fin de la procédure, en dehors de la boucle, n'est guère élégant...
Ce n'est pas élégant parce qu'il n'existe pas de construction permettant d'exprimer "a*a" (avec la syntaxe des expressions régulières), alors qu'on est habitué à la construction "do a while(...)" (qui correspond à "a+" ou "aa*".) Une solution serait de boucler un peu trop, et d'ajouter un test "si c'est la fin, afficher également", mais cela rajoute des calculs inutiles.
Si cela était possible d'une manière concise en Fortran, je te recommanderais de placer l'affichage dans une autre procédure. Mais ça ne l'est pas, donc c'est probablement le mieux tu puisses faire.
Ma propre solution en Forth :
0 value focus
variable length
: reset to focus 0 length ! ;
: incr 1 length +! ;
: out length @ ?dup-if 0 .r focus emit then ;
: up dup focus = ?dup-0=-if out reset then incr ;
: each over + swap ;
: rle 0 reset each do i c@ up loop out ;
\ tests
: show 2dup type cr rle cr ;
s" hello" show
s" aaaabbaadaaabb" show
bye
Salut
J'ai essayé d'écrire un petit Huffman en F# :
type Arbre<'T> = Nil | Branche of 'T * Arbre<'T> * Arbre<'T>
let probabilites phrase =
let probs = new System.Collections.Generic.Dictionary<char,int>()
for c in phrase do
if probs.ContainsKey(c) then
probs.[c] <- probs.[c] + 1
else
probs.[c] <- 1
[for c in probs.Keys -> (Branche(c,Nil,Nil), probs.[c]) ] |> List.sortWith (fun (_,n1) (_,n2) -> n1 - n2)
let rec creerArbre probs =
match probs with
| [] -> Nil
| [(a,_)] -> a
| (a1,v1) :: (a2,v2) :: reste -> let probs' = (Branche('_',a1,a2),v1 + v2) :: reste
creerArbre probs'
let rec listeCodes arbre (acc: string) =
match arbre with
| Nil -> []
| Branche(c, Nil, Nil) -> [(c,acc)]
| Branche(_, g, d) -> let listeg = listeCodes g (acc + "1")
let listed = listeCodes d (acc + "0")
listeg @ listed
let Huffman phrase =
let prob = probabilites phrase
let arbre = creerArbre prob
let codes = listeCodes arbre ""
let listeCars = [for c in phrase do
let (car,code) = codes |> List.find (fun (car,_) -> car = c)
yield code]
(listeCars |> List.fold (fun acc c -> acc + c) "", codes)
let test = Huffman "Test de l'algo de Huffman !"
Printf.printfn "%A" test
Je débute dans ce langage donc toutes les critiques et idées d'amélioration/factorisation du code sont les bienvenues.
Je pense que ton implémentation de la construction de l'arbre est fausse : tu récupères les deux nœuds de poids le plus faible, tu les fusionnes, mais tu mets le nœud résultat au début de la liste de nœuds directement. C'est faux (si je me souviens bien, j'ai un peu oublié l'algo depuis le temps) puisqu'il peut y avoir des nœuds suivants de poids inférieur.
Par exemple, quel est l'arbre construit pour les fréquences suivantes : (a 2) (b 2) (c 3) (d 3) ? (par exemple sur l'entrée "aabbcccddd")
Enfin, ta fonction de codage n'est pas du tout efficace : pour chaque lettre dans l'entrée, tu vas chercher linéairement dans une liste de clés (lettre, code) pour trouver le bon code. Il vaut mieux faire comme pour le calcul des probabilités, utiliser une table associative des lettre vers tes données. De plus ça permettra de coder une fonction "listeCodes" plus efficace, car la fusion de deux tables associatives est plus performante à priori que la concaténation de deux listes.
Je pense que ton implémentation de la construction de l'arbre est fausse : tu récupères les deux nœuds de poids le plus faible, tu les fusionnes, mais tu mets le nœud résultat au début de la liste de nœuds directement. C'est faux (si je me souviens bien, j'ai un peu oublié l'algo depuis le temps) puisqu'il peut y avoir des nœuds suivants de poids inférieur.
Oui t'as raison, je n'ai pas ajouté le nouveau nœud au bon endroit. J'ai fait un petit exemple sur une feuille avant d'écrire l'algo, et c'est lui qui m'as induit en erreur. Puisque la liste doit rester triée, et pour éviter de refaire le tri à chaque modification, j'ai écrit une fonction qui insère juste le nouveau élément au bon endroit (comme celle qu'on utilise pour le tri fusion).
Citation : bluestorm
Enfin, ta fonction de codage n'est pas du tout efficace : pour chaque lettre dans l'entrée, tu vas chercher linéairement dans une liste de clés (lettre, code) pour trouver le bon code. Il vaut mieux faire comme pour le calcul des probabilités, utiliser une table associative des lettre vers tes données. De plus ça permettra de coder une fonction "listeCodes" plus efficace, car la fusion de deux tables associatives est plus performante à priori que la concaténation de deux listes.
Je suis conscient des différences de performances des concaténations des listes et des dictionnaires (temps linéaire pour les listes, logarithmiques pour les dictionnaires représentés par un arbre), mais j'ai voulu éviter d'abuser de structures de données mutables. J'ai pensé à utiliser des Map (dictionnaires immuables), mais je ne savais pas trop comment fusionner les deux Map droite et gauche (j'ai finalement trouvé la solution : un fold).
Voici la nouvelle version :
open System.Collections.Generic
type Arbre<'T> = Nil | Branche of 'T * Arbre<'T> * Arbre<'T>
let probabilites phrase =
let probs = new Dictionary<char,int>()
for c in phrase do
if probs.ContainsKey(c) then
probs.[c] <- probs.[c] + 1
else
probs.[c] <- 1
[for c in probs.Keys -> (Branche(c,Nil,Nil), probs.[c]) ] |> List.sortWith (fun (_,n1) (_,n2) -> n1 - n2)
let rec creerArbre probs =
match probs with
| [] -> Nil
| [(a,_)] -> a
| (a1,v1) :: (a2,v2) :: reste -> let rec inserer e l =
match l with
| [] -> [e]
| (_,v) as t :: q -> if v > snd e then e::l else t :: inserer e q
let probs' = inserer (Branche('_',a1,a2),v1 + v2) reste
creerArbre probs'
let rec listeCodes arbre (acc: string): Map<char,string> =
match arbre with
| Nil -> Map.empty;
| Branche(c, Nil, Nil) -> Map.add c acc Map.empty
| Branche(_, g, d) -> let dictg = listeCodes g (acc + "1")
let dictd = listeCodes d (acc + "0")
dictg |> Map.fold (fun acc c s -> Map.add c s acc) dictd
let Huffman phrase =
let prob = probabilites phrase
let arbre = creerArbre prob
let codes = listeCodes arbre ""
let listeCars = [ for c in phrase -> codes.[c] ]
(listeCars, codes)
let test = Huffman "Test de l'algo de Huffman !"
Printf.printfn "%A" test
Edit: j'ai testé un peu les performances de l'algo, il boucle infiniment pour un fichier de 4Mo à cause de la concaténation des chaines finales (qui est inutile et rendra le décodage plus difficile. J'ai donc supprimé cette opération et on passe d'un temps "infini" à 4 secondes.
@bluestorm: je vais apprendre OCaml aussi donc ça me sera utile. Merci.
Pour avoir une "insertion dans la liste des nœuds de travail" efficace, utilise plutôt une file de priorité qu'une liste triée. C'est l'implémentation la plus simple. Il y a aussi moyen de s'en sortir avec simplement deux piles, je crois, mais c'est plus compliqué et je ne m'en souviens plus. J'avais écrit une implémentation OCaml (je crois) de cette deuxième méthode dans l'atelier Huffman, tu devrais aller regarder si ça t'intéresse.
edit : en OCaml, on peut implémenter l'union de deux Map de façon plus efficace qu'en faisant un fold (avec la fonction `merge` ajoutée dans OCaml 3.12).
Ils sont beaux tout vos codes, bon moi perso je suis un "débutant" de python disons que je n'ai pas eu faute de temps l'occasion de commencer la POO ... mais j'ai testé les deux ou trois codes proposés en python et dans le logiciel que j'utilise WinPython, aucun d'eux ne fonctionne ... :(
Enfin il fonctionne mais il y a une erreur de syntaxe à priori ... et je ne vois pas laquelle ... disons que ce n'est pas moi qui va corriger une possible erreur de l'un de vous tellement vous me dépasser :/
Je reprends le code de @Pmol :
def arbre(liste):
tree = [liste[0]]
for lettre, nb in liste[1:]:
elem = tree.pop()
if nb > elem[1]:
tree.append(((elem[0], lettre), elem[1]+nb))
else:
tree.append(((lettre, elem[0]), elem[1]+nb))
return tree[0][0]
def code(tree, dico={}, c=''):
"""Renvoi un dictionnaire {lettre : code}"""
if isinstance(tree[0], str):
dico[tree[0]] = c + '0'
else:
dico = code(tree[0], dico, c + '0')
if isinstance(tree[1], str):
dico[tree[1]] = c + '1'
else:
dico = code(tree[1], dico, c + '1')
return dico
def huffman(text):
"""Trouve le code de Huffman pour le texte"""
association = [(i, text.count(i)) for i in set(text)]
association.sort(lambda x, y: cmp(x[1], y[-1]))
tree = arbre(association)
dico = code(tree)
return ''.join(dico[i] for i in text)
def arbre(liste):
tree = [liste[0]]
for lettre, nb in liste[1:]:
elem = tree.pop()
if nb > elem[1]:
tree.append(((elem[0], lettre), elem[1]+nb))
else:
tree.append(((lettre, elem[0]), elem[1]+nb))
return tree[0][0]
def code(tree, dico={}, c=''):
"""Renvoi un dictionnaire {lettre : code}"""
if isinstance(tree[0], str):
dico[tree[0]] = c + '0'
else:
dico = code(tree[0], dico, c + '0')
if isinstance(tree[1], str):
dico[tree[1]] = c + '1'
else:
dico = code(tree[1], dico, c + '1')
return dico
def huffman(text):
"""Trouve le code de Huffman pour le texte"""
association = [(i, text.count(i)) for i in set(text)]
association.sort(lambda x, y: cmp(x[1], y[-1]))
tree = arbre(association)
dico = code(tree)
return ''.join(dico[i] for i in text)
print huffman('aaaabbc')
Si je demande ça, mon logiciel renvoie ça :
>>> Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "C:\Users\YC\Desktop\WinPython\python-3.3.5.amd64\lib\site-packages\spyderlib\widgets\externalshell\sitecustomize.py", line 585, in runfile
execfile(filename, namespace)
File "C:\Users\YC\Desktop\WinPython\python-3.3.5.amd64\lib\site-packages\spyderlib\widgets\externalshell\sitecustomize.py", line 48, in execfile
#!/usr/bin/env python3
from functools import cmp_to_key
cmp = lambda a,b: (a > b) - (a < b)
def arbre(liste):
tree = [liste[0]]
for lettre, nb in liste[1:]:
elem = tree.pop()
if nb > elem[1]:
tree.append(((elem[0], lettre), elem[1]+nb))
else:
tree.append(((lettre, elem[0]), elem[1]+nb))
return tree[0][0]
def code(tree, dico={}, c=''):
"""Renvoi un dictionnaire {lettre : code}"""
if isinstance(tree[0], str):
dico[tree[0]] = c + '0'
else:
dico = code(tree[0], dico, c + '0')
if isinstance(tree[1], str):
dico[tree[1]] = c + '1'
else:
dico = code(tree[1], dico, c + '1')
return dico
def huffman(text):
"""Trouve le code de Huffman pour le texte"""
association = [(i, text.count(i)) for i in set(text)]
association.sort(key=cmp_to_key(lambda x, y: cmp(x[1], y[-1])))
tree = arbre(association)
dico = code(tree)
return ''.join(dico[i] for i in text)
def arbre(liste):
tree = [liste[0]]
for lettre, nb in liste[1:]:
elem = tree.pop()
if nb > elem[1]:
tree.append(((elem[0], lettre), elem[1]+nb))
else:
tree.append(((lettre, elem[0]), elem[1]+nb))
return tree[0][0]
def code(tree, dico={}, c=''):
"""Renvoi un dictionnaire {lettre : code}"""
if isinstance(tree[0], str):
dico[tree[0]] = c + '0'
else:
dico = code(tree[0], dico, c + '0')
if isinstance(tree[1], str):
dico[tree[1]] = c + '1'
else:
dico = code(tree[1], dico, c + '1')
return dico
def huffman(text):
"""Trouve le code de Huffman pour le texte"""
association = [(i, text.count(i)) for i in set(text)]
association.sort(key=cmp_to_key(lambda x, y: cmp(x[1], y[-1])))
tree = arbre(association)
dico = code(tree)
return ''.join(dico[i] for i in text)
print(huffman('aaaabbc'))
P.S.: si le message d'erreur change, précise-le.
- Edité par quelqun_dautre 10 janvier 2015 à 18:45:01
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.