L’algorithme d'Huffman en c# !

Version imprimable

13/12/2010, 10h31
Sylvanocry

L’algorithme d'Huffman en c# !
Bonjour les loulous,

Je suis actuellement en train de me pencher sur l'algorithme d'Huffman en C#, langage que je ne maîtrise pas encore... (Il faut bien un début à tout !)

Je l'ai déjà fait en C, et j'aimerai refaire un peu la même chose en C#, juste pour connaître les différences entre les deux langages.

Je suis face à un problème que je n'arrive pas à résoudre. Pour ceux qui ne connaisse pas, l'algorithme d'Huffman est là : http://fr.wikipedia.org/wiki/Codage_de_Huffman

J'essaye de compresser des fichiers textes. Ce qui fait que je compte le nombre d’occurrence de mes lettres, et je les places comme suis :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 A 1 l 1 l 2 e 1 r 1 1 l 3 e 2 s 1 2 m 1 e 3 c 1 s 2 3 o 1 n 1 4 y 1 5 c 2 r 2 o 2 i 1 t 1 6 ! 1
Maintenant, j'aimerai créer une liste, pour ensuite l'utiliser et créer un arbre avec celle ci. (Cas d'école me voilà !)

Je fais ceci :
Code:

1 2 3 4 5 6 7 8 9 struct Maillon { char octet; int occurence; struct Maillon * filsGauche; struct Maillon * filsDroit; struct Maillon * suivant; }
Mais d'après mes quelques recherches, je ne peux pas utiliser de pointeurs dans une structure et sur une structure, à cause du Garbage collector.

Donc, je vous demande ici même, puis je utiliser les pointeurs ? Ou, sinon, comment puis je pallier au problème ?

Merci à tous =)

Sylvanocry.
13/12/2010, 10h48
Nathanael Marchand
En C#, tu n'utilises pas les pointeurs (ou du moins très très rarement) explicitement.
Ca donne:
Code:

1 2 3 4 5 6 7 8 class Maillon { char octet; int occurence; Maillon filsGauche; Maillon filsDroit; Maillon suivant; }
13/12/2010, 10h57
tomlev
Citation:

Envoyé par Sylvanocry

Donc, je vous demande ici même, puis je utiliser les pointeurs ?

Tu peux, mais seulement dans un contexte "unsafe". Et de toutes façons ce n'est pas du tout comme ça qu'on fait habituellement en C#. L'utilisation des pointeurs se limite à quelques usages très spécifiques, par exemple quand le code C# doit interagir avec du code natif.

Citation:

Envoyé par Sylvanocry

Ou, sinon, comment puis je pallier au problème ?

Déjà, déclare Maillon comme une classe plutôt que comme une structure, sinon tu ne pourras pas les "imbriquer" comme tu fais.
Code:

1 2 3 4 5 6 7 8 class Maillon { public char octet; public int occurence; public Maillon filsGauche; public Maillon filsDroit; public Maillon suivant; }
Changements par rapport à ton code d'origine :

- ajout du modificateur public sur les champs (sinon c'est private par défaut). Soit dit en passant : en général, en C# on évite d'exposer publiquement des champs ; on met les champs en privé et on utilise des propriétés pour y accéder (un propriété est en fait une paire de méthodes get/set). Mais pour que ça reste simple, j'ai juste mis public, sinon ça fait beaucoup de choses à la fois à assimiler...

- les membres filsGauche, filsDroit et suivant ne sont plus déclarés comme des pointeurs : ce sont en fait des références. En C#, toutes les variables dont le type est un "type référence" (class) contiennent en fait une référence qui pointe vers l'objet sur le tas. Cette référence peut éventuellement être "null", c'est à dire qu'elle ne pointe vers aucun objet. Par opposition, les variables de "type valeur" (struct) contiennent directement la valeur.

Sinon, je ne connais pas l'algo en question, mais octet représente-t-il réellement un octet, ou un caractère ? En C on considère souvent que c'est la même chose, mais en C# ce n'est pas pareil. Il y a un type byte (octet) et un type char (charactère unicode). A toi de voir ce qui convient le mieux selon le besoin...
13/12/2010, 11h06
theMonz31

sinon, si tu as la flemme :

Huffman en C#

Bonjour à vous deux,

D'une part merci beaucoup pour ces explications. Cela va m'aider à avancer de façon plus structurée.

J'ai donc mis mon ancienne structure de cette façon :

Code:

1
2
3
4
5
6
7
8
    class Maillon
    {
        public char octet;
        public int occurence;
        public Maillon filsGauche;
        public Maillon filsDroit;
        public Maillon suivant;
    }

Maintenant que tout est un peu plus claire, je me penche sur mes anciennes fonctions...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
          int liste_longueur(Maillon l)
        {
 
            Maillon courant = null;
            int taille = 0;
            courant = l;
 
            while (courant != null)
            {
                taille++;
                courant = courant->suiv;
            }
 
            return taille;
        }

Les pointeurs en C, c'était rigolo :(

Je vous fais par de la suite des évènements d'ici peu.

13/12/2010, 11h14
tomlev

L'opérateur -> ne s'utilise qu'avec les pointeurs (comme en C d'ailleurs)
Utilise le point à la place

Re bonjour.

Pour l'instant j'ai fait ces petits fichier là : (et j'en suis pas peu fier. (oui j'ai un certain égo à satisfaire.))

Ce fichier, Form.cs me permet de lire un fichier texte, et de compter les occurrences de lettres.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
 
 
namespace Algo_de_huffman
{
    public partial class Form1 : Form
    {
        private char[]   BufDeLettre ;
        public Liste liste;
 
        public Form1()
        {
            InitializeComponent();
        }
 
        private void m_buttonComp_Click(object sender, EventArgs e)
        {
            if (textBox1.Text == "")
            {
                MessageBox.Show("Entrer un fichier text !");
            }
            else
                lectureFichier(textBox1.Text);
        }
 
        public void lectureFichier(string fichier)
        {
            string line;
            DataGridViewColumn col = new DataGridViewTextBoxColumn();
            DataGridViewColumn col1 = new DataGridViewTextBoxColumn();
            col.Name = "Caractère";
            this.dataGridView1.Columns.Add(col);
 
 
            col1.Name = "Occurence";
            this.dataGridView1.Columns.Add(col1);
 
            DataGridViewRowCollection rows = this.dataGridView1.Rows;
 
            System.IO.StreamReader file = new System.IO.StreamReader(fichier);
            BufDeLettre = new char[256];
 
            textBox2.Text = file.ReadToEnd();
            file.BaseStream.Position = 0;
            while ((line = file.ReadLine()) != null)
            {
                for (int i = 0 ; i < line.Length; i++)
                {
                    BufDeLettre[line[i]]++;
                    rows.Add(line[i], (int)BufDeLettre[line[i]]);
                }
            }
 
            file.Close();
 
        }
 
    }
}

J'ai ce petit affichage fort sympathique : http://img580.imageshack.us/img580/4281/screencf.png

Maintenant que mon tableau est fait, et que mes occurrences de lettres comptées, j'aimerai utiliser ce fichier pour créer une liste de maillon (un maillon représenté par une valeur, un maillon suivant, et la lettre qu'il représente (pour l'instant) ).

Je m'y suis pris de cette façon :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Algo_de_huffman
{
 
    class Liste
    {
        public char val;
       // public int occurence;
       // public Maillon filsGauche;
       // public Maillon filsDroit;
        public Liste suivant;
 
        Liste liste_creer()
        {
            return null;
        }
 
 
        // Cette fonction peut s'écrire de cette façon :         
        // return l ? liste_longueur(l->suiv) +1 : 0 ;
        int liste_longueur(Liste l)
        {
 
            Liste courant = null;
            int taille = 0;
            courant = l;
 
            while (courant != null)
            {
                taille++;
                courant = courant.suivant;
            }
 
            return taille;
        }
 
 
 
        Liste liste_nieme(Liste l, int indice)
	    {
            Liste adresse;
            int indice_courant = 0;
 
            for (adresse = l; adresse != null; adresse = adresse.suivant)
            {
                if (indice_courant == indice)
                    return adresse; //adresse du indicième maillon  indice = 0: 1er maillon, indice = 1 : 2ème maillon ...
                indice_courant++;
            }
            return null; //jamais atteint
	    }
 
 
 
        void liste_inserer_debut(Liste l, int valeur)
        {
            Liste nouv = null;
            nouv.val = (char)valeur;
            nouv.suivant = l;
            l = nouv;
        }
 
        void liste_inserer(Liste l, Liste avant, int valeur)
        {
            liste_inserer_debut(avant.suivant, valeur);
        }
 
 
        void liste_supprimer(Liste l, int indice)			// liste_supprimer (liste & l , element e)
        {
                            				// inutile ou assert ( l ! = NULL )
            if (indice == 0)					// if ( l == element )
            { // supprimer un élément
                Liste a_detruire = l;
                l = l.suivant;
 
            }
            else
            {
                liste_supprimer(l.suivant, indice - 1);
            }
        }
 
    }
}

Mon problème est au niveau du premier code, quand je fais " public Liste liste;"
Cela ne peut pas fonctionner? Comment puis je fais pour utiliser mon module de liste dans mon Form.cs pour créer ma liste à partir du tableau ?

Désolé pour ces questions qui doivent vous paraître plus qu'idiote.

Merci de votre temps,

Sylvanocry

Code:

1
2
3
4
public Liste liste = null;
...
liste = listeEnParam;//On référence la liste
liste.Prop = 1;//on manipule les propriétés

Quand tu écris ça, tu t'exposes à une nullreferenceException

Code:

1
2
3
4
5
6
7
void liste_inserer_debut(Liste l, int valeur)
        {
            Liste nouv = null;
            nouv.val = (char)valeur;//nouv est null, donc nouv.val KABOOOM
            nouv.suivant = l;
            l = nouv;
        }

A aucun moment tu n'initialises ta variable liste. Il faut explicitement appeler le constructeur, soit directement à la déclaration, soit ailleurs dans le code.

Code:

public Liste liste = new Liste();

D'autre part, ta classe Liste contient plein de méthodes qui prennent en paramètre une liste, et ne travaillent que sur cette liste passée en paramètre (et jamais sur la liste courante "this"). En programmation orientée objet, on ne s'y prend pas comme ça. En général les méthodes d'instance d'une classe travaillent sur l'instance courante de la classe. Tu devrais réécrire tes méthodes comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 int liste_longueur() // pas de paramètre, on va travailler sur this { Liste courant = null; int taille = 0; courant = this; while (courant != null) { taille++; courant = courant.suivant; } return taille; }

13/12/2010, 16h06
Nathanael Marchand

De plus je dirais qu'il existe deja nativement des conteneurs dans .Net: des lists, hashsets, stacks, queues, dictionaries, etc.
Pourquoi s'embeter à réinventer la roue?
13/12/2010, 18h22
tomlev

Citation:

Envoyé par PitMaverick78

De plus je dirais qu'il existe deja nativement des conteneurs dans .Net: des lists, hashsets, stacks, queues, dictionaries, etc.
Pourquoi s'embeter à réinventer la roue?

Tout à fait d'accord dans le principe, mais pour débuter ça fait pas de mal de réinventer un peu pour bien comprendre le langage ;)
14/12/2010, 00h16
Guulh

Citation:

Envoyé par tomlev

Tout à fait d'accord dans le principe, mais pour débuter ça fait pas de mal de réinventer un peu pour bien comprendre le langage ;)

Absolument :) Découvrir, l'expérience aidant, que le code que l'on a produit lorsque l'on ne connait pas bien C# peut se ré-écrire en moins de 10 lignes (à mon avis ici, deux trois coups de Linq suffisent pour implémenter l'algo d'Huffman) est un mélange bizarre de satisfaction d'avoir progressé et d'impression d'avoir perdu son temps :)
Ceci dit, on aborde les problèmes différemment dans un langage bas niveau comme C et dans un langage au framework très complet comme C#. J'ai connu des devs qui n'arrivaient pas à s'y faire, et qui persistaient à utiliser leur implémentation de liste chaînée maison (ou leurs loggers ou leur surcouche aux sockets-mais-si-je-te-dis-que-ton-wcf-et-ton-remoting-c'est-tout-pourri). Il y a des habitudes à perdre :)