Uma das ferramentas mais utilizadas por grande parte do usuários de computador é o compactador de arquivos. Essa ferramenta ajuda na economia de espaço e na organização de arquivos, sendo considerada de grande importância. Temos diversos compactadores de arquivos: Winrar, 7zip, winzip e etc… . Poderíamos explicar o aqui o funcionamento de algum dos softwares citados anteriormente, mas nós gostamos de desafios! Dessa forma decidimos construir nosso próprio compactador! O que acha? Quem sabe construir o próximo Winrar!?
Índice
- 1 Versão 0: Compactador de Arquivos utilizando Run-Length e Código de Huffman
- 1.1 Run-length
- 1.2 Código de Huffman
- 1.3 Construção do compactador
- 1.3.1 Compactação
- 1.3.2 Descompactação
- 1.4 Persistência em Arquivo
- 1.5 Referências
Versão 0: Compactador de Arquivos utilizando Run-Length e Código de Huffman
Para construir nosso compactador de arquivos, utilizaremos duas técnicas de compressão de cadeias:
Run-length
A ideia do método é simplificar a representação de cadeias de um único caractere. Por exemplo:
AAAAA
Com a representação pela técnica de compressão temos:
onde, A é o caractere que se repete, @ indica inicio da repetição e 4 sendo a quantidade de vezes que ele repete.
Para implementarmos essa ideia devemos levar em consideração o seguinte:
- O número de caracteres repetidos deve ser maior ou igual a três, caso contrário não se justifica a utilização do método.
Esse método não é tão eficiente na compressão de textos uma vez que no português, e na maioria das línguas, não temos repetições de tamanho maior que três. Por isso esse método será utilizado juntamente com código de Huffman.
Código de Huffman
A codificação de Huffman é um método de compressão que usa as probabilidades de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo. De uma forma mais simples, ele funciona com o uso de “apelidos” para sequência de caracteres mais frequentes. Adotaremos a ideia mais simples para que fique o mais fácil o possível de se compreender.
Basicamente vamos apelidar pequenas sequências de caracteres. Por exemplo:
Assim como no exemplo deveremos tomar pequenas sequências e símbolos que as substituam.
Construção do compactador
Agora que sabemos como funcionam os métodos que serão utilizados, podemos iniciar a construção do programa. O desenvolvimento do programa será dividido em duas partes: Compactação e Descompactação.
Compactação
Os dois processos de compactação citados anteriormente serão utilizados na criação da nossa função “comprime” . O protótipo da função será:
- void comprime(char *vet, int tam)
A primeira técnica a ser implementada será o run-length. Nessa técnica devemos percorrer a nossa string verificando se existe igualdade de no mínimo três caracteres:
for(i=0;i<tam;i++){
if(texto[i]==texto[i+1]&&texto[i]==texto[i+2]){
Veja que tam é o tamanho do texto e que a cada interação do laço estou verificando três posições: i, i+1 e i+2.
Caso a verificação falhe o processo de compactação continua, indo para parte do algoritmo de huffman; Se o processo não falhar, devemos em seguida, verificar se mais de três caracteres são iguais, percorrendo o resto do texto com um segundo laço.
...
int j,q,t;
j=i+2;
repeti1=2;
repeti2=0;
texto[i+1]='¬';
while(texto[i]==texto[j]&&t!=10){
texto[j]='¬';
j++;
if(repeti1<10)
{
repeti1++;
}
if(repeti1>=10&&repeti2<10)
{
repeti2++;
}
}
...
A medida que percorremos o nosso texto, devemos contar quantas vezes o caracteres se repetem. Para isso utilizaremos a variável repeti1, que ira registrar a quantidade de repetições enquanto for menor que dez, e repeti2 ira registrar as de maior valor. Utilizaremos o simbolo de marcação @ para marcar cadeias menores que dez, e para cadeias maiores utilizaremos æ.
OBS: A variável repeti1 começa com valor dois, uma vez que, considera as duas primeiras repetições do caractere. Lembrando: para que o algoritmo chegue nessa etapa, a cadeia deve ter pelo menos os três primeiros caracteres iguais, assim o terceiro caractere será contado em repeti1 na primeira interação do laço.
O próximo passo é substituir as repetições pela notação. Podemos escrever da seguinte forma:
...
if(repeti1<10){
if(repeti1==3){
vet[i+1]='@';
vet[i+2]=repeti1+48;
}
...
if(repeti1==9){
vet[i+1]='@';
vet[i+2]=repeti1+48;
}
}
else if(repeti1>=10&&repeti1<100){
vet[i+1]='æ';
vet[i+2]=repeti2+47;
}
A figura abaixo demonstra o funcionamento desse trecho de código:
OBS: O trecho de código iniciado pelo “else if” possui um funcionamento semelhante, entretanto a soma acontece a partir do caractere “/” que precede o caractere “0”.
Terminada essa parte, vamos iniciar a parte que cabe ao código de Huffman. Como foi dito antes, por simplicidade, iremos implementar a ideia básica desse método de codificação. Basicamente devemos criar “apelidos”, selecionando conjunto de caracteres de tamanho maior ou igual a dois. Essa parte pode ser implementada como no exemplo abaixo:
- Funciona basicamente substituindo o o conjunto de caracteres pelo “apelido”.
else if(texto[i]=='a'&&texto[i+1]=='s'){//as
texto[i]='¦';
texto[i+1]='¬';
}
else if(texto[i]=='e'&&texto[i+1]=='s'){//es
texto[i]='¨';
texto[i+1]='¬';
}
Seguindo esse exemplo você deve criar mais apelidos, para que a compactação se torne mais eficiente.
Descompactação
Após desenvolvermos o processo de compactação torna-se simples realizar a descompactação, uma vez que, consiste apenas do processo inverso. O protótipo da função descompactar será:
- void descompactar(char *texto,char *resultado)
onde texto é o texto compactado e resultado é a string que receberá o texto descompactado.
No run-length iremos substituir toda cadeia que conter os caracteres especias:
- @ para cadeias menores que 10
- æ para cadeias maiores que 10
A substituição dessas cadeias deve considerar o número que precede o símbolo, pois esse número indica quantas vezes o caractere irá repetir.
Na codificação de Huffman o processo é basicamente o mesmo, só que ao invés de símbolo especial e número nós fazemos uso do apelido. Então basta substituir o apelido pelo conjunto de carácteres correspondente(que foi definido anteriormente).
Persistência em Arquivo
Neste tutorial consideramos que você tenha conhecimento básico sobre arquivos. Caso não tenha, acesse o site Descomplicada. Lá você ira encontrar informação necessário sobre como persistir os dados trabalhados em arquivos.
Prossiga Programando; 