LZ77 e LZ78 - LZ77 and LZ78

LZ77 e LZ78 são os dois algoritmos de compressão de dados sem perdas publicados em artigos de Abraham Lempel e Jacob Ziv em 1977 e 1978. Eles também são conhecidos como LZ1 e LZ2, respectivamente. Esses dois algoritmos formam a base para muitas variações, incluindo LZW , LZSS , LZMA e outros. Além de sua influência acadêmica, esses algoritmos formaram a base de vários esquemas de compressão ubíquos, incluindo GIF e o algoritmo DEFLATE usado em PNG e ZIP .

Ambos são codificadores teoricamente de dicionário . LZ77 mantém uma janela deslizante durante a compressão. Posteriormente, foi demonstrado que isso era equivalente ao dicionário explícito construído por LZ78 - no entanto, eles só são equivalentes quando todos os dados devem ser descompactados.

Como o LZ77 codifica e decodifica de uma janela deslizante sobre caracteres vistos anteriormente, a descompressão deve sempre começar no início da entrada. Conceitualmente, a descompressão LZ78 poderia permitir acesso aleatório à entrada se todo o dicionário fosse conhecido com antecedência. No entanto, na prática, o dicionário é criado durante a codificação e decodificação, criando uma nova frase sempre que um token é gerado.

Os algoritmos foram nomeados como IEEE Milestone em 2004. Em 2021 Jacob Ziv foi premiado com a Medalha de Honra IEEE por seu envolvimento em seu desenvolvimento.

Eficiência teórica

No segundo dos dois artigos que introduziram esses algoritmos, eles são analisados ​​como codificadores definidos por máquinas de estado finito. Uma medida análoga à entropia da informação é desenvolvida para sequências individuais (em oposição a conjuntos probabilísticos). Essa medida fornece um limite na taxa de compactação de dados que pode ser alcançada. É então mostrado que existem codificadores finitos sem perdas para cada sequência que atinge esse limite conforme o comprimento da sequência cresce até o infinito. Nesse sentido, um algoritmo baseado neste esquema produz codificações assintoticamente ótimas. Este resultado pode ser comprovado de forma mais direta, como por exemplo nas notas de Peter Shor .

LZ77

Os algoritmos LZ77 alcançam a compactação substituindo ocorrências repetidas de dados por referências a uma única cópia dos dados existentes anteriormente no fluxo de dados descompactados. Uma correspondência é codificada por um par de números chamado par comprimento-distância , que é equivalente à afirmação "cada um dos próximos caracteres de comprimento é igual aos caracteres de distância exata atrás dele no fluxo não compactado". (A distância às vezes é chamada de deslocamento .)

Para detectar correspondências, o codificador deve manter o controle de alguma quantidade dos dados mais recentes, como os últimos 2 kB , 4 kB ou 32 kB. A estrutura na qual esses dados são mantidos é chamada de janela deslizante , motivo pelo qual LZ77 às vezes é chamado de compactação de janela deslizante . O codificador precisa manter esses dados para procurar correspondências e o decodificador precisa manter esses dados para interpretar as correspondências às quais o codificador se refere. Quanto maior for a janela deslizante, mais longe o codificador poderá pesquisar para criar referências.

Não é apenas aceitável, mas freqüentemente útil, permitir que pares comprimento-distância especifiquem um comprimento que realmente exceda a distância. Como um comando de cópia, isso é intrigante: "Volte quatro caracteres e copie dez caracteres daquela posição para a posição atual". Como dez caracteres podem ser copiados quando apenas quatro deles estão realmente no buffer? Lidando com um byte de cada vez, não há problema em atender a essa solicitação, porque conforme um byte é copiado, ele pode ser alimentado novamente como entrada para o comando de cópia. Quando a posição de cópia chega à posição de destino inicial, são, conseqüentemente, alimentados com dados que foram colados desde o início da posição de cópia. A operação é, portanto, equivalente à instrução "copie os dados que você recebeu e cole-os repetidamente até que se encaixem". Como esse tipo de par repete uma única cópia de dados várias vezes, ele pode ser usado para incorporar uma forma flexível e fácil de codificação de comprimento de execução .

Outra maneira de ver as coisas é a seguinte: Durante a codificação, para o ponteiro de pesquisa continuar encontrando pares combinados após o final da janela de pesquisa, todos os caracteres da primeira correspondência no deslocamento D e adiante até o final da janela de pesquisa devem ter correspondido de entrada, e estas são as anteriormente (vi) caracteres que compreendem uma única unidade de execução de comprimento L R , que deve ser igual a D . Então, à medida que o ponteiro de pesquisa passa pela janela de pesquisa e avança, na medida em que o padrão de execução se repete na entrada, os ponteiros de pesquisa e entrada estarão em sincronia e corresponderão aos caracteres até que o padrão de execução seja interrompido. Então L caracteres foram combinados no total, L > D , e o código é [ D , L , c ].

Após a descodificação de [ D , G , c ], mais uma vez, D = G R . Quando os primeiros caracteres L R são lidos na saída, isso corresponde a uma unidade de execução única anexada ao buffer de saída. Neste ponto, o ponteiro de leitura pode ser pensado como apenas precisando retornar int ( L / L R ) + (1 se L mod L R ≠ 0) vezes para o início dessa unidade de execução com buffer único, ler caracteres L R ( ou talvez menos no último retorno) e repita até que um total de L caracteres sejam lidos. Mas espelhando o processo de codificação, uma vez que o padrão é repetitivo, o ponteiro de leitura precisa apenas seguir em sincronia com o ponteiro de gravação por uma distância fixa igual ao comprimento de execução L R até que L caracteres tenham sido copiados para a saída no total.

Considerando o acima, especialmente se a compressão de corridas de dados deve predominar, a pesquisa de janela deve começar no final da janela e prosseguir para trás, uma vez que os padrões de execução, se existirem, serão encontrados primeiro e permitirão que a pesquisa termine, absolutamente se o comprimento máximo atual da sequência correspondente for atingido, ou judiciosamente, se um comprimento suficiente for encontrado e, finalmente, pela simples possibilidade de que os dados sejam mais recentes e possam se correlacionar melhor com a próxima entrada.

Pseudo-código

O pseudocódigo é uma reprodução da janela deslizante do algoritmo de compressão LZ77. 

while input is not empty do
    prefix := longest prefix of input that begins in window
    
    if prefix exists then
        d := distance to start of prefix
        l := length of prefix
        c := char following prefix in input
    else
        d := 0
        l := 0
        c := first char of input
    end if
    
    output (d, l, c)
    
    discard l + 1 chars from front of window
    s := pop l + 1 chars from front of input
    append s to back of window
repeat

Implementações

Mesmo que todos os algoritmos LZ77 funcionem por definição no mesmo princípio básico, eles podem variar amplamente na forma como codificam seus dados compactados para variar os intervalos numéricos de um par comprimento-distância, alterar o número de bits consumidos por um par comprimento-distância, e distinguir seus pares comprimento-distância de literais (dados brutos codificados como eles próprios, em vez de como parte de um par comprimento-distância). Alguns exemplos:

  • O algoritmo ilustrado no artigo original de Lempel e Ziv de 1977 produz todos os seus dados com três valores por vez: o comprimento e a distância da correspondência mais longa encontrada no buffer e o literal que se seguiu a essa correspondência. Se dois caracteres sucessivos no fluxo de entrada pudessem ser codificados apenas como literais, o comprimento do par comprimento-distância seria 0.
  • O LZSS melhora o LZ77 usando um sinalizador de 1 bit para indicar se o próximo bloco de dados é um literal ou um par comprimento-distância, e usando literais se um par comprimento-distância for maior.
  • No formato PalmDoc , um par comprimento-distância é sempre codificado por uma sequência de dois bytes. Dos 16 bits que compõem esses dois bytes, 11 bits vão para a codificação da distância, 3 vão para a codificação do comprimento e os dois restantes são usados ​​para garantir que o decodificador possa identificar o primeiro byte como o início de um sequência de bytes.
  • Na implementação usada para muitos jogos pela Electronic Arts , o tamanho em bytes de um par comprimento-distância pode ser especificado dentro do primeiro byte do próprio par comprimento-distância; dependendo se o primeiro byte começa com 0, 10, 110 ou 111 (quando lido na orientação do bit big-endian ), o comprimento de todo o par comprimento-distância pode ser de 1 a 4 bytes.
  • Em 2008, o método de compressão baseado em LZ77 mais popular é DEFLATE ; combina LZSS com codificação Huffman . Literais, comprimentos e um símbolo para indicar o final do bloco atual de dados são todos colocados juntos em um alfabeto. As distâncias podem ser colocadas com segurança em um alfabeto separado; como a distância ocorre apenas após um comprimento, ela não pode ser confundida com outro tipo de símbolo ou vice-versa.

LZ78

Os algoritmos LZ78 alcançam a compactação substituindo ocorrências repetidas de dados por referências a um dicionário que é construído com base no fluxo de dados de entrada. Cada entrada de dicionário tem o formato dictionary[...] = {index, character}, onde índice é o índice de uma entrada de dicionário anterior e o caractere é anexado à string representada por dictionary[index]. Por exemplo, "abc" seria armazenado (em ordem reversa) da seguinte maneira:, dictionary[k] = {j, 'c'}, dictionary[j] = {i, 'b'}, dictionary[i] = {0, 'a'}onde um índice de 0 especifica o primeiro caractere de uma string. O algoritmo inicializa o último índice correspondente = 0 e o próximo índice disponível = 1. Para cada caractere do fluxo de entrada, é pesquisado no dicionário uma correspondência: {último índice correspondente, caractere}. Se uma correspondência for encontrada, o último índice correspondente será definido como o índice da entrada correspondente e nada será gerado. Se uma correspondência não for encontrada, uma nova entrada de dicionário é criada: dicionário [próximo índice disponível] = {último índice correspondente, caractere}, e o algoritmo gera o último índice correspondente , seguido por caractere , em seguida, redefine o último índice correspondente = 0 e incrementos no próximo índice disponível . Quando o dicionário estiver cheio, nenhuma outra entrada será adicionada. Quando o final do fluxo de entrada é alcançado, o algoritmo gera o último índice correspondente . Observe que as strings são armazenadas no dicionário em ordem reversa, com a qual um decodificador LZ78 terá que lidar.

LZW é um algoritmo baseado em LZ78 que usa um dicionário pré-inicializado com todos os caracteres possíveis (símbolos) ou emulação de um dicionário pré-inicializado. A principal melhoria do LZW é que quando uma correspondência não é encontrada, o caractere do fluxo de entrada atual é considerado o primeiro caractere de uma string existente no dicionário (uma vez que o dicionário é inicializado com todos os caracteres possíveis), então apenas a última correspondência índice é a saída (que pode ser o índice de dicionário pré-inicializado correspondente ao caractere de entrada anterior (ou inicial)). Consulte o artigo LZW para detalhes de implementação.

BTLZ é um algoritmo baseado em LZ78 que foi desenvolvido para uso em sistemas de comunicação em tempo real (originalmente modems) e padronizado pelo CCITT / ITU como V.42bis . Quando o dicionário estruturado em três está cheio, um algoritmo simples de reutilização / recuperação é usado para garantir que o dicionário possa continuar se adaptando aos dados variáveis. Um contador percorre o dicionário. Quando uma nova entrada é necessária, o contador percorre o dicionário até que um nó folha seja encontrado (um nó sem dependentes). Isso é excluído e o espaço reutilizado para a nova entrada. É mais simples de implementar do que LRU ou LFU e atinge um desempenho equivalente.

Veja também

Referências

links externos

  • "O algoritmo LZ78" . Centro de Referência de Compactação de Dados: grupo de trabalho RASIP . Faculdade de Engenharia Elétrica e Computação da Universidade de Zagreb. 1997. Arquivado do original em 7 de janeiro de 2013 . Página visitada em 22 de junho de 2012 .
  • "O algoritmo LZW" . Centro de Referência de Compactação de Dados: grupo de trabalho RASIP . Faculdade de Engenharia Elétrica e Computação da Universidade de Zagreb. 1997. Arquivado do original em 7 de janeiro de 2013 . Página visitada em 22 de junho de 2012 .