LZW
Esta calculadora comprime/descomprime um string utilizando o algoritmo Lempel-Ziv-Welch (LZW).
As calculadoras neste artigo são utilizadas para comprimir e descomprimir uma string usando o algoritmo LZW. O método LZW é simples e confiável, e não requer armazenar um dicionário - o dicionário é gerado dinamicamente durante a compressão e descompressão.
Para estudar a lógica do algoritmo, cheque o ícone "Mostrar detalhes" - as calculadoras exibirão o registro de trabalho e os dicionários de frases gerados.
Compressão de texto LZW
O dump binário ou arquivo binário gerado pela calculadora anterior pode ser passado para a calculadora seguinte, que irá restaurar a string original. É necessário definir o método de formação do dicionário de fonte da mesma forma que é definido para a calculadora de compressão. (Escolha a mesma codificação ou especifique o mesmo dicionário de maneira explícita).
Descompressão LZW
- Arraste para cá os arquivos
Algoritimo Lempel-Ziv-Welch
O algoritmo de compressão sem perdas LZ78 foi publicado em 1978 por Abraham Lempel e Jacob Ziv, e depois modificado por Terry Welch em 1984. Após a publicação de Welch, o algoritmo foi nomeado LZW devido aos sobrenomes dos autores (Lempel, Ziv, Welch). O algoritmo foi patenteado, mas todas as patentes já expiraram, o que nos dá uma grande oportunidade de publicar nossa implementação aqui.
Descrição do algoritmo LZW
- Crie o dicionário inicial contendo todos os caracteres possíveis.
- Coloque o primeiro caractere na frase de entrada W.
- Leia o próximo caractere K.
- Se EOF retornar W, então:
Se a frase WK já estiver no dicionário, W ⟵ WK, vá para 3,
Caso contrário, retorne o código de W, adicione WK ao dicionário, W ⟵ K. Vá para 3.
Para decodificar os dados gerados desta forma, você não precisa armazenar o dicionário. É recriado por si mesmo no processo de descompressão:
- Crie o dicionário inicial contendo todos os caracteres possíveis.
- Coloque o primeiro código na frase de entrada W.
- Leia o próximo código K.
- Se EOF, retorna o caractere com o código W, caso contrário:
Se a frase com o código WK não estiver no dicionário, retorne a frase com o código W e adicione a frase com o código WK ao dicionário.
Caso contrário, atribua o código WK à frase de entrada e vá para 3.
O artigo original de Welch pretendia codificar uma frase em um dicionário com um tamanho fixo de código de 12 bits. Mesmo assim, essa abordagem pode até aumentar o comprimento da mensagem codificada para mensagens pequenas em comparação com o texto original. Portanto, é bastante comum usar o comprimento de código dinâmico, pois ele muda toda vez que o limite do dicionário é alcançado.
Lidando com o crescimento do tamanho do dicionário
No algoritmo de compressão descrito acima, o tamanho do dicionário não é limitado. Na prática, isso pode levar a restrições de recursos ao carregar grandes quantidades de dados.
Existem modificações conhecidas no algoritmo que tentam solucionar este problema:
- LZC - a implementação do algoritmo no utilitário de compressão limita o tamanho máximo do dicionário a 16 bits. Quando o tamanho máximo é alcançado, o dicionário para de mudar. O algoritmo monitora a taxa de compressão e, se degradar significativamente, ele redefine o dicionário e o forma novamente.
- LZT - em overflow, ele remove do dicionário uma frase que não é usada há muito tempo
Nossos recursos de implementação
Dicionário inicial
Nossas calculadoras implementam um vocabulário em crescimento interminável, o que pode ser muito caro para dados grandes. O tamanho dos códigos de frase se inicia em 8 bits para o dicionário inicial especificado pela codificação padrão, ou menos para um dicionário inserido manualmente. No último caso, o tamanho dos códigos de frase é o número mínimo de bits necessários para expressar o número de caracteres no dicionário. Comprimento de bits.
Codificações de multibyte
Algumas codificações podem necessitar de mais de 1 byte por caractere, por exemplo, em UTF-8 a codificação contém caracteres de comprimento variável de 1 a 4 bytes. Em qualquer caso, o dicionário inicial terá 256 itens com códigos de 0 a 255 para qualquer codificação que você escolher.
Para codificações de multibyte, um dicionário gerado dinamicamente parecerá bastante exótico - suas frases serão inevitavelmente compostas de diferentes partes de caracteres adjacentes. Nesse caso, para ter clareza nas tabelas de saída, usamos um marcador de byte ausente (por padrão, esse é o caractere '~'). Por exemplo, ao comprimir a frase "9 €", representada na codificação UTF-8 o dicionário dinâmico pode ser preenchido com combinações dos caracteres a seguir:
9 - nove,
' ' - espaço,
€~~ - primeiro byte do símbolo do euro,
~€~ - segundo byte do símbolo do euro,
~~€ - terceiro byte do símbolo do euro,
€~ - os primeiros dois bytes do símbolo do euro,
~€ - os últimos dois bytes do símbolo do euro,
€ - todos os três bytes do símbolo do euro.
Introduzimos esta descrição de caractere apenas por conveniência. Uma vez que as partes constituintes de muitos caracteres multibyte são apenas bytes de 8 bits, elas podem ser iguais para diferentes caracteres.
por exemplo:
€ ~~ - o primeiro byte do símbolo do euro, seu código em utf-8 = 226
₽ ~~ - o primeiro byte do símbolo do rublo, seu código em utf-8 = 226.
Zeros à direita
O algoritmo de compressão pode produzir um arranjo de bits com um tamanho que não é múltiplo de 8. Nesse caso, a calculadora de compressão preenche o final com zero bits. Uma vez que nossa implementação usa um tamanho variável do código de frase, esta abordagem pode causar problemas se o dicionário inicial definido manualmente for muito pequeno.
Neste exemplo a mensagem final será que apenas 18 bits e 6 bits deverão ser preenchidos com zeros para armazenar a mensagem inteira em um arquivo binário.
Uma vez que com os parâmetros especificados, o tamanho do código da frase é apenas 4 bits, a palavra extra será lida durante a descompactação, e se criássemos o dicionário original com o código do primeiro caractere = 0, então o caractere extra seria descompactado.
Resolvemos esse problema adicionando um caractere nulo ao início do dicionário, que é comumente interpretado como o final de uma string.
Ao usar a codificação como o dicionário inicial, este problema nunca irá surgir, uma vez que o tamanho do código da frase é sempre de no mínimo 8 bits.
Comentários