bzip2 (Português)

Bzip2 usa várias camadas de técnicas de compressão empilhadas umas sobre as outras, que ocorrem na seguinte ordem durante a compressão e na ordem inversa durante a descompressão:

1. Codificação de comprimento de execução (RLE) de dados iniciais.
2. Transformação de Burrows-Wheeler (BWT) ou classificação de bloco.
3. Transformação de mover para a frente (MTF).
4. Codificação de comprimento de execução (RLE) do resultado MTF.
5. Codificação de Huffman.
6. Seleção entre várias tabelas de Huffman.
7. Codificação unária de base 1 da seleção da tabela de Huffman.
8. Codificação delta (Δ) de comprimentos de bits do código de Huffman.
9. Matriz de bits esparsa mostrando quais símbolos são usados.

CodificaçãoEdição de comprimento de execução inicial

Qualquer sequência de 4 a 255 símbolos duplicados consecutivos é substituída pelos primeiros 4 símbolos e um comprimento de repetição entre 0 e 251. Assim, a sequência AAAAAAABBBBCCCD é substituído por AAAA\3BBBB\0CCCD, onde \3 e \0 representam os valores de byte 3 e 0, respectivamente. Execuções de símbolos são sempre transformadas após 4 símbolos consecutivos, mesmo se o comprimento de execução for definido como zero, para manter a transformação reversível.

No pior caso, pode causar uma expansão de 1,25, e em no melhor caso, uma redução para < 0,02. Embora a especificação teoricamente permita que execuções de comprimento 256-259 sejam codificadas, o codificador de referência não produzirá tal saída.

O autor de bzip2 afirmou que a etapa RLE foi um erro histórico e foi apenas intencional para proteger a implementação original do BWT de casos patológicos.

Burrows – Wheeler transformEdit

Este é o tipo de bloco reversível que está no cerne do bzip2. O bloco é totalmente autocontido, com buffers de entrada e saída permanecendo do mesmo tamanho – em bzip2, o limite operacional para este estágio é 900 kB. Para a ordenação em bloco, uma matriz (nocional) é criada, na qual a linha i contém todo o buffer, girada para começar a partir do i-ésimo símbolo. Após a rotação, as linhas da matriz são classificadas em ordem alfabética (numérica). Um ponteiro de 24 bits é armazenado marcando a posição inicial para quando o bloco não for transformado. Na prática, não é necessário construir a matriz completa; em vez disso, a classificação é realizada usando ponteiros para cada posição no buffer. O buffer de saída é a última coluna da matriz; ele contém todo o buffer, mas reordenado para que provavelmente contenha grandes séries de símbolos idênticos.

Transformar Mover para a frenteEditar

Novamente, essa transformação não altera o tamanho do bloco processado. Cada um dos símbolos em uso no documento é colocado em uma matriz. Quando um símbolo é processado, ele é substituído por sua localização (índice) na matriz e esse símbolo é embaralhado para a frente da matriz. O efeito é que os símbolos imediatamente recorrentes são substituídos por símbolos zero (séries longas de qualquer símbolo arbitrário tornam-se séries de símbolos zero), enquanto outros símbolos são remapeados de acordo com sua frequência local.

Muitos dados “naturais” contém símbolos idênticos que se repetem dentro de um intervalo limitado (o texto é um bom exemplo). Como a transformação MTF atribui valores baixos a símbolos que reaparecem com frequência, isso resulta em um fluxo de dados contendo muitos símbolos na faixa de número inteiro baixo, muitos deles sendo idênticos (diferentes símbolos de entrada recorrentes podem, na verdade, mapear para o mesmo símbolo de saída). Esses dados podem ser codificados de forma muito eficiente por qualquer método de compactação legado.

Codificação de duração de MTF resultEdit

Longas sequências de zeros na saída da transformação de mover para a frente ( que vêm de símbolos repetidos na saída do BWT) são substituídos por uma sequência de dois códigos especiais, RUNA e RUNB, que representam o comprimento de execução como um número binário. Os zeros reais nunca são codificados na saída; um zero solitário se torna RUNA. (Esta etapa, na verdade, é realizada ao mesmo tempo que o MTF; sempre que o MTF produzir zero, ele aumenta um contador para então codificar com RUNA e RUNB.)

A sequência 0, 0, 0, 0, 0, 1 seria representado como RUNA, RUNB, 1; RUNA, RUNB representa o valor 5 conforme descrito abaixo. O código de comprimento de execução é encerrado ao atingir outro símbolo normal. Este processo RLE é mais flexível do que a etapa RLE inicial, pois é capaz de codificar inteiros arbitrariamente longos (na prática, isso geralmente é limitado pelo tamanho do bloco, de forma que esta etapa não codifica uma execução de mais de 900000 bytes). O comprimento de execução é codificado desta maneira: atribuindo valores de casas de 1 ao primeiro bit, 2 ao segundo, 4 ao terceiro, etc. na sequência, multiplique cada valor de casas em um ponto RUNB por 2 e adicione todos os valores locais resultantes (para valores RUNA e RUNB semelhantes) juntos. Isso é semelhante à numeração bijetiva de base 2.Assim, a sequência RUNA, RUNB resulta no valor (1 + 2 × 2) = 5. Como um exemplo mais complicado:

RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49

Huffman codingEdit

Este processo substitui os símbolos de comprimento fixo no intervalo de 0 a 258 por códigos de comprimento variável com base na frequência de uso. Códigos usados com mais frequência acabam mais curtos (2–3 bits), enquanto códigos raros podem ser alocados em até 20 bits. Os códigos são selecionados cuidadosamente para que nenhuma sequência de bits possa ser confundida com um código diferente.

O código de fim de fluxo é particularmente interessante. Se houver n bytes (símbolos) diferentes usados nos dados não compactados, o código de Huffman consistirá em dois códigos RLE (RUNA e RUNB), n – 1 códigos de símbolo e um código de fim de fluxo. Por causa do resultado combinado das codificações MTF e RLE nas duas etapas anteriores, nunca há necessidade de referenciar explicitamente o primeiro símbolo na tabela MTF (seria zero no MTF comum), salvando assim um símbolo para o final marcador de fluxo (e explicando por que apenas n – 1 símbolos são codificados na árvore de Huffman). No caso extremo em que apenas um símbolo é usado nos dados descompactados, não haverá nenhum código de símbolo na árvore de Huffman e todo o bloco consistirá em RUNA e RUNB (repetindo implicitamente o byte único) e um fim de – marcador de fluxo com valor 2.

0: RUNA, 1: RUNB, 2–257: valores de byte 0–255, 258: fim do fluxo, processamento final (pode ser tão baixo quanto 2).

Editor de tabelas de Huffman múltiplo

Várias tabelas de Huffman de tamanho idêntico podem ser usadas com um bloco se o ganho de usá-las for maior do que o custo de incluir a tabela extra. Podem estar presentes pelo menos 2 e até 6 tabelas, com a tabela mais apropriada sendo selecionada novamente antes de cada 50 símbolos processados. Isso tem a vantagem de ter uma dinâmica de Huffman muito responsiva sem ter que fornecer continuamente novas tabelas, como seria exigido no DEFLATE. A codificação de comprimento de execução na etapa anterior foi projetada para cuidar de códigos que têm uma probabilidade inversa de uso maior do que o código Huffman de código mais curto em uso.

Codificação unária da seleção de tabela de Huffman

Se várias tabelas de Huffman estiverem em uso, a seleção de cada tabela (numerada de 0 a 5) é feita a partir de uma lista por um bit terminado em zero executado entre 1 e 6 bits de comprimento. A seleção está em uma lista MTF das tabelas. O uso desse recurso resulta em uma expansão máxima de cerca de 1,015, mas geralmente menos. É provável que essa expansão seja bastante obscurecida pela vantagem de selecionar tabelas Huffman mais apropriadas, e o caso comum de continuar a usar a mesma tabela Huffman é representado como um único bit. Em vez de codificação unária, efetivamente esta é uma forma extrema de uma árvore de Huffman, onde cada código tem metade da probabilidade do código anterior.

Delta encodingEdit

Os comprimentos de bits do código de Huffman são necessário para reconstruir cada uma das tabelas canônicas de Huffman usadas. Cada comprimento de bit é armazenado como uma diferença codificada em relação ao comprimento de bit do código anterior. Um bit zero (0) significa que o comprimento do bit anterior deve ser duplicado para o código atual, enquanto um bit (1) significa que um bit adicional deve ser lido e o comprimento do bit deve ser aumentado ou diminuído com base nesse valor.

No caso comum, um único bit é usado por símbolo por tabela e o pior caso – indo do comprimento 1 ao comprimento 20 – exigiria aproximadamente 37 bits. Como resultado da codificação MTF anterior, os comprimentos de código começariam com 2–3 bits (códigos usados com frequência) e aumentariam gradualmente, o que significa que o formato delta é bastante eficiente, exigindo cerca de 300 bits (38 bytes) por tabela Huffman completa .

Editar array de bits esparsos

Um bitmap é usado para mostrar quais símbolos são usados dentro do bloco e devem ser incluídos nas árvores de Huffman. Os dados binários provavelmente usarão todos os 256 símbolos representáveis por um byte, ao passo que os dados textuais podem usar apenas um pequeno subconjunto de valores disponíveis, talvez cobrindo a faixa ASCII entre 32 e 126. Armazenar 256 bits zero seria ineficiente se eles estivessem quase todos sem uso. Um método esparso é usado: os 256 símbolos são divididos em 16 intervalos e apenas se os símbolos são usados dentro desse bloco é uma matriz de 16 bits incluída. A presença de cada um desses 16 intervalos é indicada por uma matriz adicional de 16 bits na frente.

O bitmap total usa entre 32 e 272 bits de armazenamento (4 a 34 bytes). Por contraste, o algoritmo DEFLATE mostraria a ausência de símbolos codificando os símbolos como tendo um comprimento de bit zero com codificação de comprimento de execução e codificação de Huffman adicional.