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.

PLANETCALC, Compressão de texto LZW

Compressão de texto LZW

Texto para contar palavras
Um caractere para substituir o símbolo invisível.
Um símbolo que é utilizado para indicar a posição do byte ausente de um caractere multibyte incompleto.
Número de bits no texto original
 
Número de bits na mensagem comprimida
 
Zero bits adicionados
 
Mensagem comprimida em formato binário
 
Arquivo
 
Dicionário inicial
 
Dicionário
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

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).

PLANETCALC, Descompressão LZW

Descompressão LZW

Uma mensagem codificada. Se um arquivo for fornecido, então os dados de entrada serão obtidos do arquivo.
Arquivo
  • Arraste para cá os arquivos
Um caractere para substituir o símbolo invisível.
Um símbolo que é utilizado para indicar a posição do byte ausente de um caractere multibyte incompleto.
Texto
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

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

  1. Crie o dicionário inicial contendo todos os caracteres possíveis.
  2. Coloque o primeiro caractere na frase de entrada W.
  3. Leia o próximo caractere K.
  4. 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:

  1. Crie o dicionário inicial contendo todos os caracteres possíveis.
  2. Coloque o primeiro código na frase de entrada W.
  3. Leia o próximo código K.
  4. 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.

URL copiado para a área de transferência
PLANETCALC, LZW

Comentários