/*************************************************************************************************************************************/
/* */
/* C O D A G E D E H U F F M A N : */
/* */
/* */
/* Author of '$xtc/HuffmanCoding.01$vv$c' : */
/* */
/* Jean-Francois COLONNA (LACTAMME, 20151130094521). */
/* */
/*************************************************************************************************************************************/
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N G E N E R A L E S : */
/* */
/*************************************************************************************************************************************/
#include "INCLUDES.01.I"
#include "HuffmanCoding.01.vv.I"
#define NUMERO_DU_TEST \
02 \
/* Selecteur des chaines de test {01,02,03,...}. */
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N D E S C H A I N E S D E T E S T : */
/* */
/*************************************************************************************************************************************/
CHAR ChaineA_01[]="AAAAABBBBBBBCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF";
Entier LongueurChaineA_01;
CHAR *ChaineB_01;
Entier LongueurChaineB_01;
Entier NombreDeBitsChaineB_01;
CHAR *ChaineR_01;
Entier LongueurChaineR_01;
/* Graphe de Huffman associe a la chaine precedente (issue de l'article "A quick tutorial */
/* on generating a huffman tree, 'v https://www.siggraph.org/education/materials/HyperGraph/ */
/* video/mpeg/mpegfaq/huffman_tutorial.html'). */
/* */
/* */
/* 00:005:A 01:007:B */
/* \ / */
/* \ / */
/* G D */
/* \ / */
/* \/ */
/* 03:010:C 02:012:* 05:015:D 06:020:E */
/* \ / \ / */
/* \ / \ / */
/* G D G D */
/* \ / \ / */
/* \/ \/ */
/* 04:022:* 07:035:* */
/* \ / */
/* \ / */
/* \ / */
/* \ / */
/* \ / */
/* \ / */
/* \ / */
/* G D */
/* \ / */
/* \ / */
/* \ / */
/* \ / */
/* \ / */
/* \ / */
/* \/ */
/* 09:045:F 08:057:* */
/* \ / */
/* \ / */
/* G D */
/* \ / */
/* \/ */
/* 10:102:* */
/* */
/* */
/* Les aretes sont etiquettees "G" ("Gauche") ou "D" ("Droite"). En chaque noeud, on */
/* trouve "NumeroNoeud:Frequence:Caractere" ; un "Caractere" de type "*" signifiant un */
/* cumul : */
/* */
/* 012 = 005+007 */
/* 022 = 010+012 */
/* 035 = 015+020 */
/* 057 = 022+035 */
/* 102 = 045+057 */
/* */
/* Le codage binaire entropique de Huffman (en longueur variable) utilise la convention : */
/* */
/* "G" ("Gauche") ---> 1 */
/* "D" ("Droite") ---> 0 */
/* */
CHAR ChaineA_02[]="this is an example for huffman encoding";
Entier LongueurChaineA_02;
CHAR *ChaineB_02;
Entier LongueurChaineB_02;
Entier NombreDeBitsChaineB_02;
CHAR *ChaineR_02;
Entier LongueurChaineR_02;
/* Chaine de test correspondant au programme 'v $xu/HuffmanCoding/codage.01$vv$c'. */
CHAR ChaineA_03[]="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
Entier LongueurChaineA_03;
CHAR *ChaineB_03;
Entier LongueurChaineB_03;
Entier NombreDeBitsChaineB_03;
CHAR *ChaineR_03;
Entier LongueurChaineR_03;
/* Chaine de test possedant plusieurs fois un caractere unique. */
CHAR ChaineA_04[]="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
Entier LongueurChaineA_04;
CHAR *ChaineB_04;
Entier LongueurChaineB_04;
Entier NombreDeBitsChaineB_04;
CHAR *ChaineR_04;
Entier LongueurChaineR_04;
/* Chaine de test possedant plusieurs fois deux caracteres differents. */
CHAR *ChaineA_05;
Entier LongueurChaineA_05=NOMBRE_DE_CARACTERES;
CHAR *ChaineB_05;
Entier LongueurChaineB_05;
Entier NombreDeBitsChaineB_05;
CHAR *ChaineR_05;
Entier LongueurChaineR_05;
/* Chaine de test possedant une fois tous les codes de 0 a 255. */
CHAR *ChaineA_06;
Entier LongueurChaineA_06=(NOMBRE_DE_CARACTERES*(NOMBRE_DE_CARACTERES+1)/2);
CHAR *ChaineB_06;
Entier LongueurChaineB_06;
Entier NombreDeBitsChaineB_06;
CHAR *ChaineR_06;
Entier LongueurChaineR_06;
/* Chaine de test possedant N fois tous les codes N de 0 a 255. */
/*************************************************************************************************************************************/
/* */
/* C H O I X D E L A C H A I N E D E T E S T : */
/* */
/*************************************************************************************************************************************/
#define CONCATENE_1(argument1,argument2) \
argument1 ## _ ## argument2
#define CONCATENE_2(argument1,argument2) \
CONCATENE_1(argument1,argument2)
/* On notera que l'on ne peut ecritre directement : */
/* */
/* CONCATENE_2(argument1,argument2) \ */
/* argument1 ## _ ## argument2 */
/* */
/* car cela n'assure pas la substitution de 'NUMERO_DU_TEST' par sa valeur, mais au lieu */
/* de cela, concatene la chaine "NUMERO_DU_TEST" et produit donc des symboles aberrants */
/* tels 'ChaineA_NUMERO_DU_TEST' au lieu, par exemple, de 'ChaineA_02'... */
#define CHAINE_A \
CONCATENE_2(ChaineA,NUMERO_DU_TEST)
#define LONGUEUR_CHAINE_A \
CONCATENE_2(LongueurChaineA,NUMERO_DU_TEST)
#define CHAINE_B \
CONCATENE_2(ChaineB,NUMERO_DU_TEST)
#define LONGUEUR_CHAINE_B \
CONCATENE_2(LongueurChaineB,NUMERO_DU_TEST)
#define NOMBRE_BITS_CHAINE_B \
CONCATENE_2(NombreDeBitsChaineB,NUMERO_DU_TEST)
#define CHAINE_R \
CONCATENE_2(ChaineR,NUMERO_DU_TEST)
#define LONGUEUR_CHAINE_R \
CONCATENE_2(LongueurChaineR,NUMERO_DU_TEST)
/*************************************************************************************************************************************/
/* */
/* P R O G R A M M E P R I N C I P A L : */
/* */
/*************************************************************************************************************************************/
main()
{
{
LongueurChaineA_01 = (int)strlen(ChaineA_01);
CodageDeHuffman_InitialisationChaines(ChaineB_01,ChaineR_01,ChaineA_01,LongueurChaineA_01);
/* Initialisations par defaut et systematique de la chaine '01'... */
}
{
LongueurChaineA_02 = (int)strlen(ChaineA_02);
CodageDeHuffman_InitialisationChaines(ChaineB_02,ChaineR_02,ChaineA_02,LongueurChaineA_02);
/* Initialisations par defaut et systematique de la chaine '02'... */
}
{
LongueurChaineA_03 = (int)strlen(ChaineA_03);
CodageDeHuffman_InitialisationChaines(ChaineB_03,ChaineR_03,ChaineA_03,LongueurChaineA_03);
/* Initialisations par defaut et systematique de la chaine '03'... */
}
{
LongueurChaineA_04 = (int)strlen(ChaineA_04);
CodageDeHuffman_InitialisationChaines(ChaineB_04,ChaineR_04,ChaineA_04,LongueurChaineA_04);
/* Initialisations par defaut et systematique de la chaine '04'... */
}
{
Entier index;
ChaineA_05 = malloc(LongueurChaineA_05);
for (index=PREMIER_CARACTERE ; index<=DERNIER_CARACTERE ; index++)
{
ChaineA_05[index] = index;
}
CodageDeHuffman_InitialisationChaines(ChaineB_05,ChaineR_05,ChaineA_05,LongueurChaineA_05);
/* Initialisations par defaut et systematique de la chaine '05' qui contient tous */
/* les octets possibles de 0 a 255... */
}
{
Entier index=PREMIER_CARACTERE;
Entier index_1;
ChaineA_06 = malloc(LongueurChaineA_06);
for (index_1=PREMIER_CARACTERE ; index_1<=DERNIER_CARACTERE ; index_1++)
{
Entier index_2;
for (index_2=1 ; index_2<=IndexVersNombre(index_1) ; index_2++)
{
ChaineA_06[index] = index_1;
index++;
}
}
CodageDeHuffman_InitialisationChaines(ChaineB_06,ChaineR_06,ChaineA_06,LongueurChaineA_06);
/* Initialisations par defaut et systematique de la chaine '06' qui contient N fois tous */
/* les octets possibles N de 0 a 255... */
}
CodageDeHuffman_Initialisations();
/* Initialisations diverses systematiques (et donc parfois redondantes...) independantes */
/* de la chaine de caracteres 'A'. */
CodageDeHuffman_GenerationFrequences(CHAINE_A,LONGUEUR_CHAINE_A);
/* Analyse frequentielle de la chaine de caracteres 'A'. */
CodageDeHuffman_GenerationDeLArbre();
CodageDeHuffman_EditionDeLArbre();
/* Generation et edition eventuelle de l'arbre de Huffman. */
CodageDeHuffman_ParcoursRecursifDeLArbre(CodageDeHuffman_RacineDeLArbre,0,0);
CodageDeHuffman_EditionDesCodesDeHuffman();
/* Generation et edition eventuelle du codage entropique de Huffman. */
NOMBRE_BITS_CHAINE_B = CodageDeHuffman_CompactageChaine(CHAINE_B,CHAINE_A,LONGUEUR_CHAINE_A);
LONGUEUR_CHAINE_B = (NOMBRE_BITS_CHAINE_B+NBITOC-1)/NBITOC;
LONGUEUR_CHAINE_R = CodageDeHuffman_DeCompactageChaine(CHAINE_R,CHAINE_B,NOMBRE_BITS_CHAINE_B);
/* Compactage/DeCompactage de la chaine de caracteres 'A'. */
printf("\nLes %"For10" octets (=%"For10" bits) de la chaine 'A' ont ete compactes en %"For10" octets (=%"For10" bits).\n"
,LONGUEUR_CHAINE_A,LONGUEUR_CHAINE_A*NBITOC
,LONGUEUR_CHAINE_B,NOMBRE_BITS_CHAINE_B
);
CodageDeHuffman_Verifications(CHAINE_A,LONGUEUR_CHAINE_A,CHAINE_R,LONGUEUR_CHAINE_R);
/* Validation (on doit retomber sur nos pieds...). */
CodageDeHuffman_DesinitialisationChaines(ChaineB_06,ChaineR_06);
CodageDeHuffman_DesinitialisationChaines(ChaineB_05,ChaineR_05);
CodageDeHuffman_DesinitialisationChaines(ChaineB_04,ChaineR_04);
CodageDeHuffman_DesinitialisationChaines(ChaineB_03,ChaineR_03);
CodageDeHuffman_DesinitialisationChaines(ChaineB_02,ChaineR_02);
CodageDeHuffman_DesinitialisationChaines(ChaineB_01,ChaineR_01);
}