Introdução
O LZMA é o principal (assim como está definido por defeito) algoritmo usado no popular software de compressão7z (ou 7-ZIP). Ambos 7z e o LZMA são criações de Igor Pavlov. O software corre em Windows e é grátis. Foram desenvolvidos com o principal objectivo de alta compressão, uma rápida descompressão e requer muita pouca memória para descomprimir. A principal característica é a sua arquitectura ser aberta. O software neste momento consegue comprimir dados usando 1 de qualquer dos 6 algoritmos, e consegue, em princípio comprimir com novos métodos.
Os 6 algoritmos são os seguintes:
- LZMA. Uma extensão sofisticada do LZ77
- PPMD. Uma variante do PPMdH de Dmitry Shkarin
- BCJ. Um conversor para 32-bits dos executáveis x86
- BCJ2. Um conversor similar ao anterior
- BZip2. Uma implementação do método de Burrows-Wheeler
- Deflate. Um algoritmo baseado no LZ77
O 7z é um novo formato de arquivo compactado, que proporciona alta taxa de compressão.
Justificação
O 7-Zip utiliza vários algoritmos de compactação. De momento estão implementados os seguintes: LZMA, PPMD, BCJ, BCJ2, BZip2 e o Deflate. O 7-Zip comprime para o formato 7z, que resulta num rácio de compressão que é 30 a 70% maior do que o que se obtém com o formato Zip, dependendo do tipo de dados que se está a comprimir. Para além disso, o 7-Zip consegue ainda criar ficheiros comprimidos no formato Zip que são 2 a 10% mais pequenos do que os que são criados por qualquer outro programa compatível com o formato zip
Áreas de aplicação
O LZMA faz parte do 7z (ou 7-ZIP). Este software consegue comprimir e descomprimir dados que estejam no formato ZIP, GZIP e BZIP2, consegue compactar e descompactar o formato TAR, e descomprimir dados originalmente comprimidos por RAR, CAB, ARJ, LZH, CHM, Z, CPIO, RPM e DEB.
O algoritmo de compressão LZMA
LZMA é o método por defeito e geral de compressão do formato 7z. As principais características do método LZMA são:
- Alta taxa de compressão
- Tamanho variável do dicionário (até 4 GB)
- Velocidade de compactação: cerca de 1 MB/s num CPU de 2 GHz
- Velocidade de descompactação: cerca de 10-20 MB/s num CPU de 2 GHz
- Baixos requisitos de memória para descompactação (depende do tamanho do dicionário)
- Tamanho pequeno de código para descompactação: cerca de 5 KB
- Suporte a multi-threading e hyper-threading do P4
Princípios de funcionamento do algoritmo LZMA
O principio para a compressão do LZMA é similar ao Deflate, mas usa range encoding em vez da codificação de Huffman. Isso complica o encoder, mas o resultado é uma melhor compressão (range encoding baseia-se na codificação aritmética e consegue comprimir muito perto da entropia), reduzindo substancialmente o número de normalizações necessárias. O range encoding é implementado em binário e evita a operação de divisão de inteiros que é demasiado lenta.
O LZ77 procura no buffer de pesquisa a maior string que seja coincidente com o look-ahead buffer, escrevendo-a depois no ficheiro comprimido na forma de triplet ( distância, comprimento, próximo símbolo). A distância é a distância da string no look-ahead buffer com o correspondente no buffer de pesquisa. Os 3 tipos de dados escritos no ficheiro são 3, o próximo símbolo (normalmente o seu código ASCII), comprimento (tamanho da string) e a distância (varia dependendo do tamanho do buffer de pesquisa).
O LZMA também escreve estes 3 tipos de dados. Se não existir no look-ahead buffer a string correspondente, é inserido no ficheiro um número no intervalo de [0,255]. Se existir um correspondente então escreve um par de valores (distância e comprimento), depois de serem codificados no range encoder. Devido ao tamanho grande do buffer de pesquisa, o encoder guarda as 4 entradas de distâncias mais comuns que foram determinadas e guarda-as num array (historial de distâncias). Se alguma dessas distâncias estiver no array, substitui o par por comprimento e pelo índex de 2-bit, para o array historial de distâncias.
A localização dos matchs no buffer de pesquisa é feito pelo hashing de 2 bytes, o byte onde se encontra e o byte imediatamente á sua direita. O output da função Hash é o índex do array. O tamanho do array é escolhido em potências de 2que se aproxime o mais possivél a metade do tamanho do dicionário (o output da função Hash depende do tamanho do dicionário).
Se o tamanho do dicionário for 256Mb, então o tamanho da função Hash será 126Mb. O grande tamanho do array minimiza as colisões no função Hash.
O encoder do LZMA consegue fazer hashing com2, 3 ou 4 bytes e o número de bytes no hash-array é escolhido pelo encoder dependendo do tamanho do dicionário.
Exemplo: dicionário->1 Gb (2^30 bytes)
Hash-Array -> 512Mb (2^29 items)
Item -> Inteiro 32 bit
Para conseguir tirar proveito do tamanho grande do Hash-Array, o encoder Hashes 4 bytes. Esses 4 bytes constituem 32 bits, o que proporciona 2^32 inputs diferentes. A função Hash converte cada input num índex de 29-bits.
O output da função Hash é usado como índex para o Hash-Array e o utilizador pode escolher entre 2 métodos: Hash-Chain( o mais rápido) e o Binary Tree (o mais eficiente).
Conclusão
Devido à grande quantidade de bibliotecas e funções necessárias para o funcionamento deste método de compressão e descompressão, tornou complicado a descrição do seu funcionamento. Como o método consiste numa reunião de várias funções e rotinas, torna muito difícil definir a parte principal do mesmo. O seu funcionamento foi no entanto estudado, e descrito minimamente, assim como exemplificado através de um caso em concreto. A sua implementação foi feita em C, C++ e C#. A comparação do LZMA com os seus principais concorrentes foi feita, embora muito brevemente e sem muito aprofundamento. Para tal ser feito era necessário um estudo aprofundado de tua a família de algoritmos Lempel-Ziv.
Como se pode verificar, até á data este é sem dúvida uma boa escolha como software: comprime e descomprime, vários formatos, inclusive consegue descomprimir ficheiros previamente comprimidos para formatos que ele próprio não consegue.
Além de todas estas características, a fundamental hoje em dia é ser grátis e dar liberdade ao utilizador para tentar melhorar o seu código.
Trabalho desenvolvido no âmbito da disciplina de Multimédia II da Licenciatura em Engenharia Informática, lecionada pelo Prof. Doutor Nuno Magalhães Ribeiro da Faculdade de Ciência e Tecnologia da UFP.
Texto da autoria de Bruno Oliveira (13879) e revisto por Nuno Magalhães Ribeiro.
Site planeado, desenhado, desenvolvido e programado por Daniel Dias Lima Mendes, Diogo Emanuel Lamas e Silva, Nelson José Santos Almeida no âmbito do Projeto de final de Licenciatura realizado na Unidade Curricular de Laboratório de Projeto Integrado sob a orientação técnica do Prof. Doutor Nuno Magalhães Ribeiro.