Discussion :

[n0-sheep]

Bonjour a tous,
Je suis en train de lire Clean Code, et me suis essayé a l'écriture d'un code clair, simple et propre.
J'aurai voulu votre aide pour savoir ce que je pourrai encore améliorer au niveau de la clarté ou de l'implémentation. J'ai du mal avec la notion : un niveau d'abstraction par fonction.

Le but du fichier : crypter une string en 0 et en 1 avec l'algorithme de ShannonFano. Vous verez il est très court et pas compliqué, ce qui m'intéresse c'est surtout l'aspect "code"

Voila, je vous remercie d'avance pour votre aide !

Edit, ça sera plus simple de copier le code ici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
 
class shannonFano{
 
public:
 
    void afficherTexteOriginal(){
        cout << texteACoder;
    }
    void afficherTexteCode(){
        cout << messageCode;
    }
    void afficherCodesDesCaracteres(){
        for(auto car : caracteresPresents){
            cout << car << " " << codeDuCaractere[car] << endl;
        }
    }
 
    shannonFano(string texteACoder):texteACoder(texteACoder){
        extraireCaracteresDifferents();
        calculerOccurenceDeChaqueCaractere();
        trierCaracteresParOccurencesCroissantes();
        calculerTableauCumulatif();
        calculerLeCodeDeChaqueCaractere();
        calculerLeMessageCode();
    }
 
private:
 
    void extraireCaracteresDifferents(){
        unordered_set<char> dejaVu;
        for(auto caractere : texteACoder)
            dejaVu.insert(caractere);
        caracteresPresents.insert(caracteresPresents.begin(), dejaVu.begin(), dejaVu.end());
    }
 
    void calculerOccurenceDeChaqueCaractere(){
        //initialisation a 0 (necessaire?)
        for(auto caractere : caracteresPresents)
            occurencesDuCaractere[caractere] = 0;
 
        //remplissage
        for(auto caractere : texteACoder)
            occurencesDuCaractere[caractere] += 1;
    }
 
    void trierCaracteresParOccurencesCroissantes(){
        sort(caracteresPresents.begin(), caracteresPresents.end(), comparerCaractereParOccurence(this));
    }
    struct comparerCaractereParOccurence{ //et ordre alphabetique
        shannonFano* s;
        comparerCaractereParOccurence(shannonFano* s) : s(s){}
        bool operator()(const char& a, const char& b){
            if(s->occurencesDuCaractere[a] == s->occurencesDuCaractere[b])
                return a < b;
            else
                return s->occurencesDuCaractere[a] < s->occurencesDuCaractere[b];
        }
    };
 
    void calculerTableauCumulatif(){
        int somme(0);
        for(auto caractere : caracteresPresents){
            somme += occurencesDuCaractere[caractere];
            cumulOccurences.push_back(somme);
        }
    }
 
    void calculerLeCodeDeChaqueCaractere(){
        if(caracteresPresents.size() == 1)
            codeDuCaractere[caracteresPresents.front()].push_back(CODE_GAUCHE);
        else
            calculerLeCodeDeChaqueCaractereEntre(0, (int)caracteresPresents.size()-1);
    }
    void calculerLeCodeDeChaqueCaractereEntre(int debut, int fin){ //fonction recursive
        if(fin <= debut) return;
 
        int indexCoupure = separe2PaquetsOccurencesEgales(debut, fin);
 
        //moitie gauche
        for(int i = debut; i <= indexCoupure-1; ++i)
            codeDuCaractere[caracteresPresents[i]].push_back(CODE_DROITE);
        calculerLeCodeDeChaqueCaractereEntre(debut, indexCoupure-1);
 
        //moitie droite
        for(int i = indexCoupure; i <= fin; ++i)
            codeDuCaractere[caracteresPresents[i]].push_back(CODE_GAUCHE);
        calculerLeCodeDeChaqueCaractereEntre(indexCoupure, fin);
    }
    int  separe2PaquetsOccurencesEgales(int debut, int fin){
        int offset = (cumulOccurences[debut]-1); //il faudrait trouver un meilleur nom...
        int valeurDeSeparation = (cumulOccurences[fin]-offset)/2 + offset;
        int indexCoupure = 0;
        for(indexCoupure = debut; indexCoupure <= fin; ++indexCoupure){
            if(cumulOccurences[indexCoupure] > valeurDeSeparation)
                break;
        }
        return indexCoupure;
    }
 
    void calculerLeMessageCode(){
        for(auto car : texteACoder){
            messageCode.append(codeDuCaractere[car]);
        }
    }
 
 
    //var
 
    static char constexpr CODE_GAUCHE ='0';
    static char constexpr CODE_DROITE ='1';
 
    string texteACoder;
    string messageCode;
    vector<char> caracteresPresents;
    unordered_map<char, int> occurencesDuCaractere;
    unordered_map<char, string> codeDuCaractere;
    vector<int> cumulOccurences;
};
 
int main(int argc, const char * argv[])
{
    cout << "Entrez un texte a coder : ";
    string texte;
    cin >> texte;
 
    shannonFano texteCrypte(texte);
 
    cout << "Le texte : ";
    texteCrypte.afficherTexteOriginal();
    cout << endl;
 
    cout << "Se code en : ";
    texteCrypte.afficherTexteCode();
    cout << endl;
 
    cout << "Avec les clefs suivantes : \n";
    texteCrypte.afficherCodesDesCaracteres();
    cout << endl;
 
    return 0;
}

[LittleWhite]

Bonjour,

Il faut faire attention à using namespace std; : http://cpp.developpez.com/faq/cpp/?page=namespace#NAMESPACE_no_using

Ensuite, je conseille de séparer votre code en .hpp pour les déclarations (classes) et .cpp pour les définitions de fonctions.
Le main seul, devrait être dans un fichier main.cpp

Pour moi, le constructeur ne devrait pas faire tout le travail, d'un coup. Il devrait juste préparer la classe. Et ce n'est qu'une fois que le main dit : ok, je veux chiffrer la chaine, qu'il la chiffre. De plus, s'il existe une méthode de chiffrement autre que le constructeur, on pourra plus facilement créer un héritage.

Pour comparerCaractereParOccurence, je doute que les pointeurs soient obligatoires et je les éviterai au possible.

[koala01]

Salut,

Déjà, quelques fonctions peuvent être assez facilement simplifiées.

Pour compter le nombre d'occurrences des différents caractères qui interviennent dans une chaine par exemple:

On sait que, quoi qu'il arrive, il n'y a qu'un ensemble fini de caractères, vu qu'il s'agit d'un type de données représenté par (généralement) 8 bits. On sait donc que, quoi qu'il arrive, il n'y aura jamais que 255 "char" différents

On sait aussi que la valeur que prend un char dans une chaine de caractères correspond à l'indice du "glyphe" qui permet de représenter le caractère dans une table que l'on appelle la table de caractères ASCII.

On sait enfin (mais on ne va pas le prendre en compte pour l'instant) que l'indice du premier caractère affichable est l'indice 32 qui correspond à l'espace.

Si donc on crée un tableau qui peut contenir 255 valeurs différentes et qu'on s'assure que la valeur correspond à 0 au départ, on peut parfaitement se "contenter" d'incrémenter la valeur qui se trouve à l'indice de ce tableau qui correspond à l'indice du caractère recherché dans la table de caractères ASCII.

L'explication a l'air assez compliquée comme cela, mais en réalité, la manière de s'y prendre est particulièrement simple.

Je te la présente, pour la facilité, sous la forme d'une fonction libre, mais il est assez facile de la convertir en fonction membre d'une classe elle prend la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
/** compte le nombre d'occurrences d'un caractère donné dans un message particulier
  *
  * @param[in,out] frequencies le tableau qui représente le nombre de fois que les
  * différents caractères ont été trouvés dans les différents messages
  * @param[in,out] message le message que l'on veut tester
  *
  */
void countFrequency(std::vector<size_t> & frequencies, std::string const & message){
    for(auto it : message)
        ++frequencies[it];
}

qui pourrait être utilisée sous une forme proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
int main()
{
    std::vector<size_t> frequencies(255);
    countFrequency(frequencies,"hello World");
    countFrequency(frequencies,"salut tout le monde");
    /* ici, on a le nombre d'occurrences de tous les caractères des deux messages */
    return 0;
}

A partir de là, on sait le nombre de fois que chaque caractère est apparu dans les différents message que l'on a analysé.

Mais, bien sur, ce qui nous intéresse, c'est de pouvoir mettre en relation chaque caractère avec le nombre de fois qu'il apparaît dans le message.

Nous avons donc besoin d'une structure qui puisse représenter cette relation.
Elle prendra la forme toute simple de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
struct CharacterFrequence{
    CharacterFrequence(size_t frequence, char character):
        frequence(frequence), character(character){}
    size_t frequence; // le nombre de fois que le caractère apparaît
    char character; // le caractère en question
};

Grâce à cette structure, nous pourrons obtenir la liste des caractères qui apparaissent au moins une fois dans les différents message (les autres ne nous intéressent pas particulièrement) et savoir exactement quel caractère apparaît combien de fois.

Cela pourrait se faire au travers d'une fonction proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
std::vector<CharacterFrequence> characterFrequences(std::vector<size_t> const & frequences){
    std::vector<CharacterFrequence> result;
    for(size_t index = 0; index < frequences.size(); ++index){
        /* on ne prend que les caractères qui appaissent au moins une fois */
        if(frequences[index]> 0){
            CharacterFrequence toadd(frequences[index], reinterpret_cast<char>(index));
            result.push_back(toadd);
        }
    }
}

Cette fonction pourrait, en conjonction avec celle que j'ai définie plus haut, s'utiliser sous une forme proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
int main()
{
    std::vector<size_t> frequences(255);
    countFrequency(frequences,"hello World");
    countFrequency(frequences,"salut tout le monde");
    /* ici, on a le nombre d'occurrences de tous les caractères des deux messages */
    std::vector<CharacterFrequence> usedCharacters = characterFrequences(frequences);
    return 0;
}

Nous pourrions d'ailleurs créer une petite fonction qui nous afficherait chaque caractère et le nombre de fois qu'il apparait, sous la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
void print(std::vector<CharacterFrequence> const & frequencies){
    for(auto const & it : frequencies){
        // évitons l'affichage des 31 premier caractères: ils
        // ne sont pas affichable :-P
        if(it.character>=32)
            std::cout<< it.character<<" : "<<it.frequence<<" | ";
    }
    std::cout<<std::endl<<"found "<<frequencies.size()<<" used characters";
}

ce qui nous permettrait de tester le tout sous la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
int main()
{
    std::vector<size_t> frequences(255);
    countFrequency(frequences,"hello World");
    countFrequency(frequences,"salut tout le monde");
    /* ici, on a le nombre d'occurrences de tous les caractères des deux messages */
    std::vector<CharacterFrequence> usedCharacters = characterFrequences(frequences);
    print(usedCharacters);
    return 0;
}

Eh m...de!!! L'affichage nous montre bien que l'on a utilisé 14 caractères différents, mais les éléments ne sont pas triés comme on l'aurait voulu!

L'astuce, c'est que, pour l'instant, le tableau est naturellement trié sur la base de l'index qui a servi à créer les éléments de type CharacterFrequence, et que cet index correspond à l'index d'un caractère dans la table ASCII. Autrement dit, les différents éléments sont triés par ordre des caractères qu'ils représentent.

Or, nous voulons les trier par ordre d'occurrence, c'est à dire sur base de la valeur du champs frequence.

Et pour corser le tout, nous voudrions qu'ils soient triés par ordre décroissant, alors que les algorithmes de tri utilisent généralement par ordre croissant.

Et comme si cela ne suffisait pas, il faut tenir compte du fait que plusieurs caractères différents peuvent apparaître le même nombre de fois.

Il ne faudrait pas se retrouver dans une situation dans laquelle l'ordre dans lequel apparaissent les différents éléments pourraient dépendre de la méthode de tri utilisée car cela poserait de sérieux problèmes lorsqu'il s'agit de "décrypter" les messages.

Qu'à cela ne tienne. La solution est d'indiquer la manière dont on veut que le tri soit effectué par ce que l'on appelle un foncteur (ou objet fonction).

Un foncteur n'est rien de plus qu'une structure qui ne contient (généralement) qu'une et une seule chose : une définition de l'opérateur ().

Dans notre cas, il pourrait prendre la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct CharacterFrequenceComparator{
    /** compare deux structures de type CharacterFrequence et
      * indique si la première peut être considérée comme "plus grande" que la deuxième
      *
      * @param[in] first l'élément se trouvant traditionnellement à gauche de l'opérateur
      * de comparaison
      * @param[in] second l'élément se trouvant traditionnellement à droite de l'opérateur
      * de comparaison
      * @return true si l'élément se trouvant à gauche de l'opérateur de comparaison
      * doit apparaître avant celui qui se trouve à droite de l'opérateur, false si ce n'est pas
      * le cas
      */
    bool operator()(CharacterFrequence const & first,
                             CharacterFrequence const & second) const{
       // si la fréquence du premier est plus élevée que celle du deuxième, on est sur de notre coup
      // sinon, on vérifie si la fréquence des deux est égale, et on choisi le caractère le plus grand
        return first.frequence > second.frequence || 
                                                    // 
                  ( first.frequence == second.frequence &&
                    first.character > second.character);
 
    }
};

Grâce à notre foncteur, nous pouvons utiliser la fonction std::sort pour trier notre tableau de CharacterFrequence.

Nous pouvons donc utiliser le tout sous une forme qui serait proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    std::vector<size_t> frequences(255);
    countFrequency(frequences,"hello World");
    countFrequency(frequences,"salut tout le monde");
    /* ici, on a le nombre d'occurrences de tous les caractères des deux messages */
    std::vector<CharacterFrequence> usedCharacters = characterFrequences(frequences);
    print(usedCharacters);
    std::sort( usedCharacters.begin(),usedCharacters.end(),
               CharacterFrequenceComparator());
    print(usedCharacters);
    return 0;
}

Et là, nous avons fait la moitié du chemin parce que nous avons, en quelques fonctions simples, pu obtenir la liste de tous les caractères qui apparaissent dans les différents message et le nombre de fois qu'il le font. Et, qui plus est, nous les avons triés d'une manière qui permettra la suite du processus

Maintenant, il ne te reste plus qu'à mettre au point le reste de l'algorithme