LZW
Origem: Wikipédia, a enciclopédia livre.
O LZW (Lempel-Ziv-Welch) é um algoritmo de compressão de dados baseado na localização e no registro das padronagens de uma estrutura. É geralmente utilizado em imagens em que não se pode perder a definição original. Nas imagens, o algoritmo lê os valores de pixels de uma imagem bitmap e elabora uma tabela de códigos onde se representam as padronagens repetidas dos pixels encontrados.
O codificador LZW reduz, pela compressão, os arquivos de imagens gráficas a 1/3 ou 1/4 de seu tamanho original.
Imagens com padronagem bem definidas — com grandes blocos de cor contínua ou repetidas de cores — podem reduzir para 1/10 o tamanho original do arquivo.
Índice |
[editar] Formatos que utilizam a LZW
[editar] Pseudo-Código Compactação String
1. No início o dicionário contém todas as raízes possíveis e P é vazio;
2. C <= próximo caractere da sequência de entrada;
3. A string P+C existe no dicionário?
a. se sim,
i. P <= P+C;
b. se não,
i. coloque a palavra código correspondente a P na sequência codificada;
ii. adicione a string P+C ao dicionário;
iii. P <= C;
4. Existem mais caracteres na sequência de entrada ?
a. se sim,
i. volte ao passo 2;
b. se não,
ii. coloque a palavra código correspondente a P na sequência codificada;
iii. FIM.
[editar] Pseudo-Código descompactação String
1. No início o dicionário contém todas as raízes possíveis;
2. cW <= primeira palavra código na sequência codificada (sempre é uma raiz);
3. Coloque a string(cW) na sequência de saída;
4. pW <= cW;
5. cW <= próxima palavra código da sequência codificada;
6. A string(cW) existe no dicionário ?
a. se sim,
i. coloque a string(cW) na sequência de saída;
ii. P <= string(pW);
iii. C <= primeiro caracter da string(cW);
iv. adicione a string P+C ao dicionário;
b. se não,
i. P <= string(pW);
ii. C <= primeiro caracter da string(pW);
iii. coloque a string P+C na sequência de saída e adicione-a ao dicionário;
7. Existem mais palavras código na sequência codificada ?
a. se sim,
i. volte ao passo 4;
b. se não,
i. FIM.
[editar] Algoritmo em Java
/*
* Compacta uma string usando o algoritmo LZW
* @param x parte da string que esta sendo pesquisada no dicionario
*/
public static void comprimelzw(String x) {
String p = x;
if (k < original.length()) {
if (dic.indexOf(p)!= -1){
// coloca em pos o valor da posição da string no dicionario
pos = dic.indexOf(p);
// palavra que será pesquisada no proximo laço
ant = original.substring(k,k+1);
p += ant;
//chama a função novamente
k++;
comprimelzw(p);
} else {
// adiciona a ultima posição a string
dic.add(p);
//adiciona a string compactada a chave do dicionario
compactada += pos+" ";
//chama a função novamente
comprimelzw(ant);
}
} else {
// contem duas coisas X e Y se p for maior do que 2 entao pega a ultima letra e o resto
// adiciona a compactada o endereco do resto mais a ultima letra
if (p.length() == 1) {
pos = dic.indexOf(p);
compactada += pos;
} else {
int n = p.length();
// pega sem o espaço final
pos = dic.indexOf(p.substring(0,n-1));
compactada += pos+" ";
}
}
}
