blob: fcdc3afb07e94386c2159b0b52dbc64786ae4992 (
plain)
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
|
\chapter{Manuel d'utilisation}
\paragraph{}
Ce projet génère deux binaire. Le premier appelé testTas n'est qu'une petite application nous permettant d'utiliser l'API
C++ générée par notre classe de file de priorités. Voici un exemple d'exécution:
\begin{verbatim}
Priority list type: 0 - Binary Heap
Choice: Please select an action
a - Add a key into the priority list
c - Change priority list type
d - Delete a Key from the priority list
e - Extract Min onto the priority list
l - Lower Key onto a key of the priority list
p - Print the current priority list on the screen
r - Remove the whole priority list
t - Test the priority list algorithms
q - Quit
\end{verbatim}
A partir de cet instant, le programme nous propose un menu nous permettant d'effectuer plusieurs actions sur le tas. La
fonction 'a' permet d'ajouter une clef dans le tas en cours. Comme il est impossible d'effectuer une recherche sur un tas
pour y retrouver le pointeur d'un élément, le programme nous propose de sauvegarder le pointeur résultat dans un tableau:
\begin{verbatim}
Choice: Please select a slot to save the cell
0 - Empty slot
1 - Empty slot
2 - Empty slot
3 - Empty slot
4 - Empty slot
5 - Empty slot
6 - Empty slot
7 - Empty slot
8 - Empty slot
9 - Empty slot
n - Don't store
c - Cancel
\end{verbatim}
Ce tableau apparaitra régulièrement dans toutes les fonctions du menu afin de choisir une cellule sur laquelle agir. Toutes
les fonctions du menu parlent d'elles mêmes. La fonction 't' va lancer une batterie de tests sur les algorithmes de la
file de priorité sélectionnée.
\paragraph{}
Le deuxième binaire généré est 'Huffman'. Il sert à utiliser l'algorithme d'huffman implémenté. Voici sa ligne d'aide:
\begin{verbatim}
$ ./Huffman -h
Huffman [{-f|-i} file] {type}
Huffman -h
This will encode the input file with the Huffman code
using the priority list defined by type.
Type is a number taken from this list:
0 : Binary Heap (default)
1 : Binomial Heap
2 : Fibonacci Heap
3 : Sorted chained list
-f file means that you specify a dictionnary file which is
structured as described into the README file.
-i file means that you specify a file to encode. It will
built a quiet dumb dictionnary.
By default, a dictionnary will be built from stdin.
-h prints this help and exit.
\end{verbatim}
La structure d'un dictionnaire est la suivante:
\begin{verbatim}
Mot1 : Fréquence1
Mot2 : Fréquence2
...
\end{verbatim}
Chaque mot est une chaîne de caractères servant à identifier la fréquence associée. Voici un exemple complet de dictionnaire
et d'utilisation du programme avec ce dictionnaire:
\begin{verbatim}
Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ cat dict.sample
MOT1 : 2000
MOT2 : 1234
MOT3 : 15987
MOT4 : 1203
MOT5 : 192837
MOT6 : 12987
Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ ./Huffman -f dict.sample
MOT3 (15987) = 00
MOT1 (2000) = 0100
MOT4 (1203) = 01010
MOT2 (1234) = 01011
MOT6 (12987) = 011
MOT5 (192837) = 1
Bitstream length : 283957 bits (= 35495 bytes)
Real size input : 7239936 bits (= 904992 bytes)
Size squeezed by : 96.0779 percents
Dictionnary size : 336 bits (= 42 bytes)
Total bitstream length : 284293 bits (= 35537 bytes)
Real gain (4 bytes header) : 96.0728 percents
\end{verbatim}
Il est indiqué que le programme est capable de générer un dictionnaire à partir d'un fichier. Il s'agit simplement de compter
les caractères provenant de l'entrée et d'en générer un dictionnaire. Exemple:
\begin{verbatim}
$ cat dict.sample | Huffman
\32 (12) = 00
6 (1) = 01000
4 (2) = 01001
3 (4) = 0101
0 (4) = 0110
5 (2) = 01110
7 (3) = 01111
1 (6) = 1000
M (6) = 1001
: (6) = 1010
\10 (6) = 1011
O (6) = 1100
8 (3) = 11010
9 (3) = 11011
2 (6) = 1110
T (6) = 1111
Bitstream length : 294 bits (= 37 bytes)
Real size input : 608 bits (= 76 bytes)
Size squeezed by : 51.6447 percents
Dictionnary size : 512 bits (= 64 bytes)
Total bitstream length : 806 bits (= 101 bytes)
Real gain (4 bytes header) : -38.1579 percents
\end{verbatim}
|
