Partage

Différents algorithmes de compression

Tous langages

<< 1 2

29 juin 2008 à 17:23:22

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.

bluestorm

29 juin 2008 à 17:46:51

Commence par écrire "Dico" correctement :pirate:

lastsseldon

29 juin 2008 à 18:11:47

GuilOooo> Les codes Haskell (et fonctionnels d'une manière générale) sont toujours très denses, donc non, rien à faire

.

Zulon> Huhu, rigolo. Une version en Io :

Leaf writeGraph := method(path,
    """T#{path} [label="char '#{value}'\nweight = #{weight}\ncode = '#{path}'", shape=box]""" interpolate println
)
Tree writeGraph := method(path,
    root := if(path == "",
                """T#{path} [label="root\nweight = #{weight}", shape=octagon]""",
                """T#{path} [label="weight = #{weight}"]""")
    root interpolate println
    lbranch writeGraph(path .. "0")
    rbranch writeGraph(path .. "1")

    """T#{path} -> T#{path .. "0"} [label=" 0"]""" interpolate println
    """T#{path} -> T#{path .. "1"} [label=" 1"]""" interpolate println
)
writeGraph := method(tree,
    "digraph huffman_tree {" println
    tree writeGraph("")
    "}" println
)
writeGraph(huffTree)

$ io Huffman.io "go go gophers" | dot -Tpng -o huff.png

Sobe

29 juin 2008 à 18:48:48

Super lasts !

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 ! :ninja:

) !

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 :

CODE Io :

# Encapsulation
Tree makeHuffTree := method( string,
    treeList fromString(string)
    while(treeList size > 1, treList couple)
    treeList pop
)

# Coeur
huffTree makeHuffTree(string)
table := Map clone
huffTree getCode("", table)

rz0

30 juin 2008 à 16:53:08

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

Anonyme

30 juin 2008 à 18:01:03

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).

lastsseldon

5 juillet 2008 à 20:40:15

Un Huffman en Forth, pour le plaisir des yeux

( 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

)

bluestorm

5 juillet 2008 à 20:46:19

Extrêmement bas niveau ?
Are you joking ?
Zulon code en perl !

nicknick63

5 juillet 2008 à 23:25:13

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.

wgmpgp

6 juillet 2008 à 2:32:48

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.

Le code parlera de lui-même :-°

$!/-?\!/>,?\<!/<?\:+;\
  \==/ \===/  \==/   |
/===================>/
|
|
\!/=!/:+>+<;-?\:>!/-;<+:>?\;<====\
  |  \========/   \=======/      |
  |  /===========================/
  |  |
  |  |
  |  \>!/:+>+<;-?\:>!/-;<+:>?\;<=\
  |     \========/   \=======/   |
  |                              :
  |  /===========<===============/
  |  |
  |  \>!/<->-?\<=================\
  |     \=====/                  |
  |  /===========================/
  |  |   /==============+<!/->+<?\=====================================>=========\
  |  |   |                 \=====/                                               |
  |  |   |                                                                       |
  |  |   /\                                                                      |
  |  |   ?|                                                                      !
  |  \===/\============!/:<+++++++++=!/-;-:>+<?\!/>!+++++++\/.!/-?\;;.:<?\>!/-?\+\
  |                     |             |        ; | /+++++++/|  \==/      |  \==/ ;
  |                     |             |        ? | \+++++++\|            |       |
  |                     |             \=======:/ | /+++++++/|            |       |
  |                     |                      \:/ \+++++++\|            |       |
  |                     |                          /+++++++/|            |       |
  |                     \========>===============\ \+++++++=/            |       |
  |                                              \=======================/       |
  \?===========================================================================>=/

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

$!/-?\!/>,?\<!/<?\>=================================================\
  \==/ \===/  \==/                                                  |
      /?>>/?<.>-\!------------------------------------------------\!/
      |   \=====/                                                 |
      \===========================================================/

GuilOooo

6 juillet 2008 à 13:06:21

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.

wgmpgp

6 juillet 2008 à 13:18:31

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 :-°

Anonyme

6 juillet 2008 à 15:31:02

Hey, ça a l'air marrant SNUSP. Au même titre que Befunge

.

Par contre, pour un truc en 3d, chaud quoi, comment vous l'écririez dans un fichier texte ? Un par cote :-°

GuilOooo

6 juillet 2008 à 15:38:40

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.

Anonyme

6 juillet 2008 à 15:52:18

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 :-°

bluestorm

19 août 2008 à 10:56:35

Citation : GuilOooo

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 :
diccoDeBase = Data.Map.insert "h" 1 (Data.Map.singleton "a" 2)
chaine = lzwLike "" "hahaha" diccoDeBase
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

Anonyme

1 mars 2010 à 10:24:23

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

Anonyme

3 mars 2010 à 18:32:01

Personne ne commente ?

nicknick63

3 mars 2010 à 22:51:45

Je suis pas sur que le SdZ réunisse de nombreux amateurs de Fortran…

lastsseldon

4 mars 2010 à 2:12:59

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

hello
1h1e2l1o
aaaabbaadaaabb
4a2b2a1d3a2b

Personne ne commente ?

Anonyme

4 mars 2010 à 8:17:36

Tu n'avais pas proposé une solution plus courte au début ? Quelle est la différence avec celle-ci ?

Einstein++

1 avril 2011 à 5:28:26

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.

bluestorm

1 avril 2011 à 9:50:45

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.

Einstein++

1 avril 2011 à 22:32:19

Citation : bluestorm

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.

bluestorm

1 avril 2011 à 23:50:00

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).

Shadock69

9 janvier 2015 à 22:28:32

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

exec(compile(open(filename, 'rb').read(), filename, 'exec'), namespace)

File "C:/Users/YC/Desktop/Info/algorithmedecompression.py", line 70

print huffman('aaaabbc')

SyntaxError: invalid syntax

>>>

Si quelqu'un peut m'expliquer ? :D

Voilà c'est tout, je n'ai malheureusement pas de pierre à apporter à l'édifice, et je serai curieux de voir ce que ça donne en brainfuck

Yann

61=5^3-4^3 donc d'après le grand théorème de Fermat 61 n'est pas le cube d'un entier.

quelqun_dautre

10 janvier 2015 à 3:12:02

Tu utilises Python3, le code était écrit pour Python2. Il suffit de changer les print.

yjltg.

Shadock69

10 janvier 2015 à 4:46:06

Les print ? il n'y en a qu'un... et j'ai essayé d'autre syntaxe genre :

print(Huffman('essai'))

print Huffman('essai')

print Huffman 'essai'

Je ne vois pas ou est le problème...

61=5^3-4^3 donc d'après le grand théorème de Fermat 61 n'est pas le cube d'un entier.

quelqun_dautre

10 janvier 2015 à 18:44:19

#!/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

yjltg.

Shadock69

10 janvier 2015 à 19:24:55

C'est bon ça marche merci beaucoup !!!

61=5^3-4^3 donc d'après le grand théorème de Fermat 61 n'est pas le cube d'un entier.

<< 1 2