Introduzione
Codifica di Huffman
Codifica dinamica di Huffman
Implementazione dell'algoritmo di Huffman

Introduzione

A prima vista, il concetto di compressione di dati potrebbe sembrare troppo bello per essere vero. L'idea di restringere le informazioni senza perdere nulla sembra essere un'affermazione che va contro una delle leggi minori di Newton: la legge di conservazione dei dati.
A dispetto dell'aura mistica che ne fa da contorno, la compressione delle informazioni è basata su una semplice idea: la mappazione della rappresentazione dei dati da un gruppo di simboli ad un altro più conciso.
I programmi di compattazione e l'hardware dedicato, usano metodi differenti per raggiungere questo fine. Due schemi di compressione, la codifica di Huffman e la codifica LZW (Lempel and Ziv, i due creatori, e Welch, che fece sostanziali modifiche), sono la base per molti compattatori che usiamo oggigiorno.
Queste tecniche rappresentano anche due diverse scuole di algoritmi di compressione. Una comprensione di come ciascun algoritmo lavora fornisce una eccellente conoscenza sulla compattazione in generale. Sia Huffman che l'LZW sono tecniche di compressione 'lossless'. Sono appropriati per essere usati con un qualsiasi tipo di dato perchè il risultato della espansione è identico all'input originale. Joint Photographics Experts Group (JPEG), Motion Picture Experts Group (MPEG), e altri algoritmi cuttingedge e image compression ottengono fantastiche compattazioni alle spese di una esatta riproduzione dei dati.
Queste tecniche lavorano bene con immagini e suoni, ma non sono appropriate per dati generali. La codifica di Huffman, originariamente proposta nei primi anni '50, riduce il numero di bit usati per rappresentare caratteri frequenti ed aumenta quello dei caratteri non frequenti. La tecnica LZW, invece, usa i dati immessi per costruire un alfabeto espanso, basato sulle stringhe incontrate. Questi due differenti approcci lavorano entrambi riducendo le informazioni ridondanti nell'immissione delle informazioni.

Codifica di Huffman

La codifica di Huffman è probabilmente il metodo più conosciuto per la compressione dei dati. La semplicità e l'eleganza di questa tecnica lo hanno reso duraturo, accademico e favorito. Ma la codifica di Huffman ha anche applicazioni pratiche; per esempio, la codifica statica di Huffman è usata nell'ultima fase della compressione JPEG. La compattazione NMP-5 per modem usa la compressione dinamica di Huffman in una parte del proprio processo. Infine, la codifica Shannon-Fano, una parente stretta della codifica di Huffman, è usata in una fase dell'algoritmo di implosione del PKZIP.
La codifica di Huffman lavora, come premesso, sui simboli usati più frequentemente di altri nella rappresentazione dei dati. La rappresentazione più comune, l'alfabeto ASCII, usa 8 bit per ogni carattere. In inglese la lettera E è usata più spesso della lettera Q, però noi usiamo lo stesso numero di bit per rappresentarle. Se noi usiamo solo 4 bit per la lettera E e 12 per la lettera Q, noi risparmieremo alcuni bit scorrendo un testo inglese. La codifica di Huffman formalizza questa idea di relazione tra la lunghezza e la frequenza di un simbolo. La codifica statica richiede una tabella delle probabilità prima d'iniziare a comprimere i dati. Questa tabella può essere compilata tramite un'osservazione statistica, oppure è lo stesso compattatore che visita l'input dei dati per trovare la periodicità dei simboli prima d'iniziare la compressione dei dati.
Il compattatore e il decompattatore possono costruire un albero di codifica con queste informazioni. L'albero di codifica è un albero binario con una foglia per ogni simbolo. Per costruire l'albero, il compattatore parte con i due simboli con la minor frequenza. Quindi li combina con due foglie sotto un nodo; a questo nodo, a sua volta, è assegnata la somma delle due probabilità. Il compattatore considera quindi questi nodi insieme con il resto dei simboli nella lista delle probabilità, e seleziona di nuovo i due con frequenza minore. Continua a costruire e a combinare fino a che non ottiene un singolo albero con la probabilità alla radice uguale a uno.
L'albero risultante ha foglie con distanza variabile dalla radice. Le foglie che rappresentano i simboli con la più alta frequenza sono i più vicini alla radice, mentre quelli con una bassa frequenza sono più lontani.
Per codificare un simbolo, il compattatore percorre i sentieri dalla radice dell'albero sino alla foglia corrispondente. Supponiamo che il compattatore voglia codificare la lettera S. Partirà dalla foglia corrispondente alla lettera S e salterà al nodo di origine, rilevando quale ramo (0 o 1) è accessibile. Continuerà poi a saltare fino a trovare la radice. La lista dei rami, rovesciata, descriverà il cammino dalla radice fino ad S: questa è la codi-fica di un simbolo di Huffman.
I caratteri con la più alta frequenza avranno così un codice più corto, mentre gli altri avranno via via un codice più lungo.
Per decodificare, il decompattatore fa il procedimento inverso. Parte dalla radice dell'albero. Se il primo bit è uno, allora salta al ramo uno dalla radice.
Continua leggendo bit e saltando fino a trovare la foglia che decodifica il carattere. Più di una proprietà della codifica di Huffman merita di essere discussa.
Poichè i simboli sono sempre foglie, i simboli dei nodi non avranno mai figli. Quando il decompattatore arriva ad un nodo di una foglia, deve fermarsi dal leggere dati immediatamente perchè sa di aver trovato la foglia. In altre parole, un codice di Huffman non è mai prefisso di un'altro. Questo significa che nonostante la lunghezza dei codici sia variabile, il compressore saprà sempre quando un codice finisce ed un altro inizia, e non ci sarà bisogno di esplicare lo spazio delimitato tra i codici.

Codifica dinamica di Huffman

La più grande difficoltà con la codifica di Huffman, come è facile notare dalla discussione precedente, è che questa richiede una tabella delle proba-bilità per ogni tipo di dato da comprimere. Questo non è un problema se sai di dover comprimere sempre ad esempio testi in inglese; bisogna solamente fornire al compattatore e al decompattatore un albero adatto ai testi inglese.
Il protocollo JPEG definisce un albero standard per la compressione tipo JPEG.
In un caso generale, quando non si conosce la frequenza dei simboli per l'input dei dati, la codifica statica di Huffman non può essere usata effettivamente.
Fortunatamente, una versione dinamica della compressione di Huffman può costruire l'albero al volo durante la lettura e l'attivazione della compressione. L'albero è costantemente aggiornato per riportare i cambiamenti delle frequenze dei dati.
Per inizializzare l'albero basta introdurre una foglia vuota. Una foglia vuota è semplicemente un nodo senza simbolo; questa foglia ha frequenza zero.
L'albero iniziale, che è valido sia per il compattatore sia per il decompattatore, ha soltanto la radice e una sola foglia vuota.
Il compattatore inizia a leggere un carattere. Attacca quindi questo carattere al ramo uno della radice, lasciando la foglia vuota nel ramo zero. Il carattere è spedito al decompattatore come carattere ASCII, e questi pensa ad adattare il suo albero.
Per ogni carattere letto susseguentemente, il compressore effettua i seguenti passi. Vede se il codice è nell'albero di codifica. Se c'è, il compattatore lo invia nella stessa maniera del caso di codifica statica. Se non lo trova allora lo invia verso una foglia vuota. Quindi spedisce il nuovo carattere come codice ASCII. Infine, il compattatore aggiunge due codici, uno per una nuova foglia vuota sul ramo zero e un altro per un nuovo codice sul ramo uno.
Quando l'albero è pieno (ad esempio quando tutti i caratteri sono stati visitati) il compattatore cambia solamente l'ultima foglia vuota nell'ultimo carattere.
Il programma di decompattamento può fare modifiche al suo albero perchè ha esattamente lo stesso del compattatore. Quando riceve un codice di una foglia vuota, legge il successivo codice dai dati compressi come un carattere ASCII.
Quindi impiega la stessa routine del compattatore per aggiornare l'albero.
Tuttavia la foglia vuota e l'albero non inizializzato non risolve i problemi di tenuta di traccia e cambio di frequenze. Per fare ciò, bisogna introdurre la dimensione di ogni nodo dell'albero e aggiornare questa grandezza durante l'elaborazione dei dati. Bisogna anche mantenere una lista di designazione (e di grandezza) dei nodi ordinata per dimensione.
Ogni carattere parte da dimensione uno (le foglie vuote da zero). Ogni volta che il compattatore trasmette un carattere che è nella tabella, è incrementata la dimensione del carattere del nodo. Se questo cambiamento fa diventare un nodo più grande dei nodi che sono ritenuti più grandi nella lista delle dimensioni, il compattatore scambia il carattere del nodo con il nodo più grande che è diventato più piccolo. Il termine swapping, sta a significare il commercio di nodi origine e i rami solo designati; i figli dei nodi scambiati non sono colpiti, così non c'è pericolo che un nodo vuoto diventi interno, o che un nodo interno diventi una foglia.
Il compattatore allora salta in cima all'albero dei caratteri originari, che devono essere cambiati dopo l'ultimo scambio. Continua quindi il processo via via sempre più in alto fino ad arrivare sino alla radice dell'albero.

Implementazione dell'algoritmo di Huffman

Come al solito, ci sono degli ostacoli quando si vuole implementare l'algoritmo dinamico, legati alla sua eleganza. Il primo problema è che non si può effettuare lo scambio dei nodi mentre si trasmette un codice, siccome si richiede di partire da un nodo e di produrre l'albero dei generatori dai generatori. Non si possono effettuare queste due operazioni allo stesso tempo, poichè lo scambio dei nodi causa lo scambio dei generatori, che a sua volta causa il cambiamento della trasmissione del codice. Potrebbe essere spedito un codice al decompattature prima di sapere cosa fare con esso. Un modo per risolvere questo problema è quello di fare due passate nella compressione, una per trasmettere e una per aggiornare. Il decompattatore fa anche lui due passate, una per ricevere (andando verso il basso) e una per aggiornare (tornando verso l'alto).
Il secondo problema è dato dalle foglie vuote. Siccome le foglie vuote hanno dimensione zero, è possibile che qualche foglia diventi di dimensione maggiore rispetto a quella dei propri generatori alla partenza del processo di aggiornamento. Quindi lo scambio tra genitori e figli scalerà l'albero, lasciando i genitori come propri figli. Fortunatamente, semplicemente interrompendo qualsiasi scambio tra genitori e figli si potrà evitare il problema.
Quindi, non c'è alcun modo per il decompattatore di rilevare la fine della trasmissione se il compattatore deve emettere byte interi (come nel programma di compressione dei file). Supponiamo per esempio una trasmissione lunga 81 bit. Quando il decompattatore legge il primo bit dell'undicesimo byte, non ha modo di sapere che i rimanenti sette sono spazzatura. Dunque la codifica per la compressione dei file deve conoscere la lunghezza del file per la compressione dei dati, facendola un po' di byte più lunga.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

typedef unsigned int BYTECOUNTER;

/* ---- Huffman tree structure ---- */

struct htree {

unsigned char ch; /* character value */

BYTECOUNTER cnt; /* character frequency */

int parent; /* offset to parent node */

int right; /* offset to right child node */

int left; /* offset to left child node */

};

struct htree *ht;

void buildtree(void);

FILE *OpenHelpFile(void);

static void compress(FILE *, int, int);

static void outbit(FILE *fo, int bit);

int main(int argc, char *argv[])

{ FILE *fi, *fo;int c; BYTECOUNTER bytectr = 0;int freqctr = 0;clrscr();

if (argc < 3) { printf("\nusa: huffc infile outfile");exit(1); }

if ((fi = fopen(argv[1], "rb")) == NULL) {

printf("\nCannot open %s", argv[1]);exit(1); }

if ((fo = fopen(argv[2], "wb")) == NULL) {

printf("\nCannot open %s", argv[2]);fclose(fi);exit(1); }

ht = calloc(256, sizeof(struct htree));

/* - read the input file and count character frequency - */

while ((c = fgetc(fi)) != EOF) {

c &= 255;if (ht[c].cnt == 0) { freqctr++; ht[c].ch = c;}

ht[c].cnt++;bytectr++; }

/* --- write the byte count to the output file --- */

fwrite(&bytectr, sizeof bytectr, 1, fo);

/* --- write the frequency count to the output file --- */

fwrite(&freqctr, sizeof freqctr, 1, fo);

/* -- write the frequency array to the output file -- */

for (c = 0; c < 256; c++) {

if (ht[c].cnt > 0) {

fwrite(&ht[c].ch, sizeof(char), 1, fo);

fwrite(&ht[c].cnt, sizeof(BYTECOUNTER), 1, fo);} }

/* ---- build the huffman tree ---- */

buildtree();

/* ------ compress the file ------ */

fseek(fi, 0L, 0);

while ((c = fgetc(fi)) != EOF) compress(fo, (c & 255), 0);

outbit(fo, -1); fclose(fi); fclose(fo);return(0);

}

/* ---- compress a character value into a bit stream ---- */

static void compress(FILE *fo, int h, int child)

{ if (ht[h].parent != -1) compress(fo, ht[h].parent, h);

if (child) {

if (child == ht[h].right) outbit(fo, 0);

else if (child == ht[h].left) outbit(fo, 1); }

}

static char out8;

static int ct8;

/* -- collect and write bits to the compressed output file -- */

static void outbit(FILE *fo, int bit)

{ if (ct8 == 8 || bit == -1) {

while (ct8 < 8) { out8 <<= 1;ct8++;}

fputc(out8, fo);ct8 = 0; }

out8 = (out8 << 1) | bit; ct8++;

}

void buildtree(void)

{ int treect = 256; int i,root;

for (i = 0; i < treect; i++) {

ht[i].parent = -1;ht[i].right = -1;ht[i].left = -1;}

/* ---- build the huffman tree ----- */

while (1) {

int h1 = -1, h2 = -1;

/* ---- find the two smallest frequencies ---- */

for (i = 0; i < treect; i++) {

if (i != h1) { struct htree *htt = ht+i;

if (htt->cnt > 0 && htt->parent == -1) {

if (h1 == -1 || htt->cnt < ht[h1].cnt) {

if (h2 == -1 || ht[h1].cnt < ht[h2].cnt)

h2 = h1; h1 = i; }

else if (h2 == -1 || htt->cnt < ht[h2].cnt) h2 = i;} } }

if (h2 == -1) { root = h1; break; }

/* --- combine two nodes and add one --- */

ht[h1].parent = treect;ht[h2].parent = treect;

ht = realloc(ht, (treect+1) * sizeof(struct htree));

ht[treect].cnt = ht[h1].cnt + ht[h2].cnt;

ht[treect].right = h1;ht[treect].left = h2;

ht[treect].parent = -1; treect++; }

}





#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include <conio.h>

#define EXIT_OK 0

#define EXIT_FAILED -1

FILE *infile, *outfile;

unsigned long int textsize = 0, codesize = 0, printcount = 0;

void Error(char *message);

#define N 4096 /* Size of string buffer */

#define F 60 /* Size of look-ahead buffer */

#define THRESHOLD 2

#define NIL N /* End of tree's node */

unsigned char text_buf[N + F - 1];

int match_position, match_length,lson[N + 1], rson[N + 257], dad[N + 1];

void InitTree(void),InsertNode(int r),DeleteNode(int p);

#define N_CHAR (256 - THRESHOLD + F)

/* character code (= 0..N_CHAR-1) */

#define T (N_CHAR * 2 - 1) /* Size of table */

#define R (T - 1) /* root position */

#define MAX_FREQ 0x8000

/* update when cumulative frequency */

/* reaches to this value */

typedef unsigned char uchar;

uchar p_len[64] = {

0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08};

uchar p_code[64] = {

0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,

0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,

0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,

0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,

0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,

0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,

0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,

0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF};

uchar d_code[256] = {

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,

0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,

0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,

0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,

0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,

0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,

0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,

0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,

0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,

0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,

0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,

0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,

0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,

0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,

0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,

0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,

0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,

0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,

0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,

0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,};

uchar d_len[256] = {

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,};

unsigned freq[T + 1]; /* cumulative freq table */

int prnt[T + N_CHAR],son[T];unsigned getbuf = 0;uchar getlen = 0;

int GetBit(void),GetByte(void);

unsigned putbuf = 0;uchar putlen = 0;

void Putcode(int l, unsigned c),StartHuff(void),reconst(void),update(int c);

unsigned code, len;

void EncodeChar(unsigned c);

void EncodePosition(unsigned c),EncodeEnd(void);

int DecodeChar(void),DecodePosition(void);

void Encode(void),Decode(void);

int main(int argc, char *argv[])

{ char *s;clrscr();

if (argc != 4) {

printf("Usage:lzhuf e(compression)|d(uncompression)"

" infile outfile\n");return EXIT_FAILED;}

if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)

|| (s = argv[2], (infile = fopen(s, "rb")) == NULL)

|| (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {

printf(" $@ H H H (J %s\n", s); return EXIT_FAILED;}

if (toupper(*argv[1]) == 'E') Encode(); else Decode();

fclose(infile); fclose(outfile); return EXIT_OK;

}

void Error(char *message)

{ printf("\n%s\n", message);exit(EXIT_FAILED);}

void InitTree(void) /* Initializing tree */

{ int i; for (i = N + 1; i <= N + 256; i++)

rson[i] = NIL; /* root */

for (i = 0; i < N; i++)

dad[i] = NIL; /* node */

}

void InsertNode(int r) /* Inserting node to the tree */

{ int i, p, cmp; unsigned char *key; unsigned c;

cmp = 1;key = &text_buf[r]; p = N + 1 + key[0];

rson[r] = lson[r] = NIL;match_length = 0;

for ( ; ; ) {

if (cmp >= 0) {

if (rson[p] != NIL)

p = rson[p];

else {

rson[p] = r;

dad[r] = p;

return;

}

} else {

if (lson[p] != NIL)

p = lson[p];

else {

lson[p] = r;

dad[r] = p;

return;

}

}

for (i = 1; i < F; i++)

if ((cmp = key[i] - text_buf[p + i]) != 0)

break;

if (i > THRESHOLD) {

if (i > match_length) {

match_position = ((r - p) & (N - 1)) - 1;

if ((match_length = i) >= F)

break;

}

if (i == match_length) {

if ((c = ((r - p) & (N - 1)) - 1) < match_position) {

match_position = c;

}

}

}

}

dad[r] = dad[p];

lson[r] = lson[p];

rson[r] = rson[p];

dad[lson[p]] = r;

dad[rson[p]] = r;

if (rson[dad[p]] == p)

rson[dad[p]] = r;

else

lson[dad[p]] = r;

dad[p] = NIL; /* remove p */

}

void DeleteNode(int p) /* Deleting node from the tree */

{ int q; if (dad[p] == NIL)

return; /* unregistered */

if (rson[p] == NIL)

q = lson[p]; else

if (lson[p] == NIL)

q = rson[p]; else {

q = lson[p];

if (rson[q] != NIL) {

do {q = rson[q];

} while (rson[q] != NIL);

rson[dad[q]] = lson[q];

dad[lson[q]] = dad[q];

lson[q] = lson[p];

dad[lson[p]] = q;

}

rson[q] = rson[p];

dad[rson[p]] = q;

}

dad[q] = dad[p];

if (rson[dad[p]] == p)

rson[dad[p]] = q;

else

lson[dad[p]] = q;

dad[p] = NIL;

}

int GetBit(void) /* get one bit */

{ int i; while (getlen <= 8) {

if ((i = getc(infile)) < 0) i = 0;

getbuf |= i << (8 - getlen);

getlen += 8; }

i = getbuf;

getbuf <<= 1;

getlen--;

return (i < 0);

}

int GetByte(void) /* get a byte */

{ unsigned i;while (getlen <= 8) {

if ((i = getc(infile)) < 0) i = 0;

getbuf |= i << (8 - getlen);

getlen += 8;

}

i = getbuf;

getbuf <<= 8;

getlen -= 8;

return i >> 8;

}

void Putcode(int l, unsigned c) /* output c bits */

{ putbuf |= c >> putlen;

if ((putlen += l) >= 8) {

putc(putbuf >> 8, outfile);

if ((putlen -= 8) >= 8) {

putc(putbuf, outfile);

codesize += 2;

putlen -= 8;

putbuf = c << (l - putlen);

} else {

putbuf <<= 8;

codesize++;

}

}

}

void StartHuff(void)

{int i, j;

for (i = 0; i < N_CHAR; i++) {

freq[i] = 1;

son[i] = i + T;

prnt[i + T] = i;

}

i = 0; j = N_CHAR;

while (j <= R) {

freq[j] = freq[i] + freq[i + 1];

son[j] = i;

prnt[i] = prnt[i + 1] = j;

i += 2; j++;

}

freq[T] = 0xffff;

prnt[R] = 0;

}

void reconst(void)

{

int i, j, k;

unsigned f, l;



/* halven cumulative freq for leaf nodes */

j = 0;

for (i = 0; i < T; i++) {

if (son[i] >= T) {

freq[j] = (freq[i] + 1) / 2;

son[j] = son[i];

j++;

}

}

/* make a tree : first, connect children nodes */

for (i = 0, j = N_CHAR; j < T; i += 2, j++) {

k = i + 1;

f = freq[j] = freq[i] + freq[k];

for (k = j - 1; f < freq[k]; k--);

k++;

l = (j - k) * 2;



/* movmem() is Turbo-C dependent

rewritten to memmove() by Kenji */



/* movmem(&freq[k], &freq[k + 1], l); */

(void)memmove(&freq[k + 1], &freq[k], l);

freq[k] = f;

/* movmem(&son[k], &son[k + 1], l); */

(void)memmove(&son[k + 1], &son[k], l);

son[k] = i;

}

/* connect parent nodes */

for (i = 0; i < T; i++) {

if ((k = son[i]) >= T) {

prnt[k] = i;

} else {

prnt[k] = prnt[k + 1] = i;

}

}

}

void update(int c)

{

int i, j, k, l;

if (freq[R] == MAX_FREQ) {

reconst();

}

c = prnt[c + T];

do {

k = ++freq[c];

/* swap nodes to keep the tree freq-ordered */

if (k > freq[l = c + 1]) {

while (k > freq[++l]);

l--;

freq[c] = freq[l];

freq[l] = k;

i = son[c];

prnt[i] = l;

if (i < T) prnt[i + 1] = l;

j = son[l];

son[l] = i;

prnt[j] = c;

if (j < T) prnt[j + 1] = c;

son[c] = j;

c = l;

}

} while ((c = prnt[c]) != 0); /* do it until reaching the root */

}

void EncodeChar(unsigned c)

{

unsigned i;

int j, k;

i = 0;

j = 0;

k = prnt[c + T];

/* search connections from leaf node to the root */

do {

i >>= 1;

/*

if node's address is odd, output 1

else output 0

*/

if (k & 1) i += 0x8000;

j++;

} while ((k = prnt[k]) != R);

Putcode(j, i);

code = i;

len = j;

update(c);

}

void EncodePosition(unsigned c)

{

unsigned i;

/* output upper 6 bits with encoding */

i = c >> 6;

Putcode(p_len[i], (unsigned)p_code[i] << 8);

/* output lower 6 bits directly */

Putcode(6, (c & 0x3f) << 10);

}

void EncodeEnd(void)

{

if (putlen) {

putc(putbuf >> 8, outfile);

codesize++;

}

}

int DecodeChar(void)

{

unsigned c;

c = son[R];

/* start searching tree from the root to leaves. 

* choose node #(son[]) if input bit == 0

* else choose #(son[]+1) (input bit == 1) */

while (c < T) {

c += GetBit();

c = son[c];

}

c -= T;

update(c);

return c;

}

int DecodePosition(void)

{

unsigned i, j, c;

/* decode upper 6 bits from given table */

i = GetByte();

c = (unsigned)d_code[i] << 6;

j = d_len[i];

/* input lower 6 bits directly */

j -= 2;

while (j--) {

i = (i << 1) + GetBit();

}

return c | i & 0x3f;

}

void Encode(void)

{

int i, c, len, r, s, last_match_length;

fseek(infile, 0L, 2);

textsize = ftell(infile);

if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)

Error("Unable to write"); /* write size of original text */

if (textsize == 0)

return;

rewind(infile);

textsize = 0; /* rewind and rescan */

StartHuff();

InitTree();

s = 0;

r = N - F;

for (i = s; i < r; i++)

text_buf[i] = ' ';

for (len = 0; len < F && (c = getc(infile)) != EOF; len++)

text_buf[r + len] = c;

textsize = len;

for (i = 1; i <= F; i++)

InsertNode(r - i);

InsertNode(r);

do {

if (match_length > len)

match_length = len;

if (match_length <= THRESHOLD) {

match_length = 1;

EncodeChar(text_buf[r]);

} else {

EncodeChar(255 - THRESHOLD + match_length);

EncodePosition(match_position);

}

last_match_length = match_length;

for (i = 0; i < last_match_length &&

(c = getc(infile)) != EOF; i++) {

DeleteNode(s);

text_buf[s] = c;

if (s < F - 1)

text_buf[s + N] = c;

s = (s + 1) & (N - 1);

r = (r + 1) & (N - 1);

InsertNode(r);

}

if ((textsize += i) > printcount) {

printf("%12ld\r", textsize);

printcount += 1024;

}

while (i++ < last_match_length) {

DeleteNode(s);

s = (s + 1) & (N - 1);

r = (r + 1) & (N - 1);

if (--len) InsertNode(r);

}

} while (len > 0);

EncodeEnd();

printf("input: %ld bytes\n", textsize);

printf("output: %ld bytes\n", codesize);

printf("output/input: %.3f\n", (double)codesize / textsize);

}

void Decode(void)

{

int i, j, k, r, c;

unsigned long int count;

if (fread(&textsize, sizeof textsize, 1, infile) < 1)

Error("Unable to read"); /* read size of original text */

if (textsize == 0)

return;

StartHuff();

for (i = 0; i < N - F; i++)

text_buf[i] = ' ';

r = N - F;

for (count = 0; count < textsize; ) {

c = DecodeChar();

if (c < 256) {

putc(c, outfile);

text_buf[r++] = c;

r &= (N - 1);

count++;

} else {

i = (r - DecodePosition() - 1) & (N - 1);

j = c - 255 + THRESHOLD;

for (k = 0; k < j; k++) {

c = text_buf[(i + k) & (N - 1)];

putc(c, outfile);

text_buf[r++] = c;

r &= (N - 1);

count++;

}

}

if (count > printcount) {

printf("%12ld\r", count);

printcount += 1024;

}

}

printf("%12ld\n", count);

}

Fonte originale: www.fauser.edu