Compactação - Parte 4

Neste post vamos examinar um pouco o que o programa do post anterior faz. Para isto vamos acrescentar à rotina de descompactação uma tabela para contar quantas vezes cada código é usado:

view plaincopy to clipboardprint?

1. typedef struct  
2. {  
3. int   cod;    /**< código de compactação */  
4. int   contUso;   /**< número de vezes que foi usado */  
5. } ESTAT;  
6.   
7. static ESTAT TabEstat [ULT_CODE+1]; /**< Estatística do uso dos códigos */  

typedef struct
{
int   cod;    /**< código de compactação */
int   contUso;   /**< número de vezes que foi usado */
} ESTAT;

static ESTAT TabEstat [ULT_CODE+1]; /**< Estatística do uso dos códigos */

No começo da rotina Expande vamos iniciar esta tabela:

view plaincopy to clipboardprint?

1.  for (prox = 0; prox <= ULT_CODE; prox++)  
2. {  
3. TabEstat [prox].cod = prox;  
4. TabEstat [prox].contUso = 0;  
5. }  

 for (prox = 0; prox <= ULT_CODE; prox++)
{
TabEstat [prox].cod = prox;
TabEstat [prox].contUso = 0;
}

E no final da Expande vamos chamar a rotina SalvaEstat(), que salva uma listagem das estatísticas em um arquivo:

view plaincopy to clipboardprint?

1. static void SalvaEstat (void)  
2. {  
3. int topo;  
4. FILE *fp;  
5. int i, w;  
6. uchar c;  
7.   
8. fp = fopen ("Estatistica.txt", "wt");  
9. for (i = 0; i < ULT_CODE+1; i++)  
10. {  
11. fprintf (fp, "Código 0x%03X, Usos: %d\n", TabEstat[i].cod, TabEstat[i].contUso);  
12. topo = 0;  
13. w = TabEstat[i].cod;  
14. while (w >= 256)  
15. {  
16.    if (topo >= sizeof(pilha))  
17.    {  
18.     printf ("Pilha insuficiente!\n");  
19.     exit (1);  
20.    }  
21.    pilha[topo++] = TabExp[w].car;  
22.    w = TabExp[w].prefixo;  
23. }  
24. pilha[topo++] = (uchar) w;  
25. while (topo > 0)  
26. {  
27.    c = pilha[--topo];  
28.    if ((c < 0x20) || (c > 0x7E))  
29.     fprintf (fp, "\\x%02X", c);  
30.    else if (c == 0x20)  
31.     fprintf (fp, ".");  
32.    else  
33.     fprintf (fp, "%c", c);  
34. }  
35. fprintf (fp, "\n\n");  
36. }  
37. }  

static void SalvaEstat (void)
{
int topo;
FILE *fp;
int i, w;
uchar c;

fp = fopen ("Estatistica.txt", "wt");
for (i = 0; i < ULT_CODE+1; i++)
{
fprintf (fp, "Código 0x%03X, Usos: %d\n", TabEstat[i].cod, TabEstat[i].contUso);
topo = 0;
w = TabEstat[i].cod;
while (w >= 256)
{
   if (topo >= sizeof(pilha))
   {
    printf ("Pilha insuficiente!\n");
    exit (1);
   }
   pilha[topo++] = TabExp[w].car;
   w = TabExp[w].prefixo;
}
pilha[topo++] = (uchar) w;
while (topo > 0)
{
   c = pilha[--topo];
   if ((c < 0x20) || (c > 0x7E))
    fprintf (fp, "\\x%02X", c);
   else if (c == 0x20)
    fprintf (fp, ".");
   else
    fprintf (fp, "%c", c);
}
fprintf (fp, "\n\n");
}
}

Se olharmos os códigos 0x100 a 0x107 podemos ver o algorítimo em funcionamento com o início do meu texto de teste:

Programação Assembler no PC-IBM e compatíveis

Código 0x100, Usos: 5
Pr

Código 0x101, Usos: 52
ro

Código 0x102, Usos: 1
og

Código 0x103, Usos: 5
gr

Código 0x104, Usos: 60
ra

Código 0x105, Usos: 17
am

Código 0x106, Usos: 30
ma

É interessante notar como uma lógica simples (ir guardando o que for vendo na entrada) fez com fossem registrados alguns pares de letras bastante comuns, como 'ro', 'ra' e 'ma'.

Podemos alterar um pouco mais o programa para ver quais os códigos mais usados. Basta incluir no início de SalvaEstat uma chamada à rotina qsort e definir uma rotina de comparação:

view plaincopy to clipboardprint?

1. qsort (TabEstat, ULT_CODE+1, sizeof(ESTAT), Compara);  
2.   
3. static int Compara (const ESTAT* elem1, const ESTAT* elem2)  
4. {  
5. return elem2->contUso - elem1->contUso;  
6. }  

qsort (TabEstat, ULT_CODE+1, sizeof(ESTAT), Compara);

static int Compara (const ESTAT* elem1, const ESTAT* elem2)
{
return elem2->contUso - elem1->contUso;
}

Os dez códigos mais usados são:

Código 0x158, Usos: 1365
====

Código 0xB9F, Usos: 574
\x0D\x0A..........

Código 0x046, Usos: 538
F

Código 0x041, Usos: 489
A

Código 0x020, Usos: 463
.

Código 0x228, Usos: 389
....

Código 0xFDF, Usos: 388
\x0D\x0A...............

Código 0xFCD, Usos: 346
\x0D\x0A\x0D\x0A........

Código 0xB30, Usos: 332
11

Código 0x02C, Usos: 325
,

No próximo post vamos fazer algumas mexidas para melhorar a taxa de compactação. Até lá!