LZW
Esta calculadora comprime/descomprime um string utilizando o algoritmo Lempel-Ziv-Welch (LZW).
Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.
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