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:

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:

 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:

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:

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á!