Lição
A teoria — Codificação run-length (RLE)
A codificação por comprimento de sequências substitui cada sequência maximal de símbolos iguais por um único par (símbolo, contagem). À leitura não chega o texto, mas dois números: N caracteres e R sequências. Todos os outros valores da página são o quociente desses dois.
O que significa cada símbolo
N- o número de caracteres à entrada — o comprimento do que escreveste, nada mais.
R- o número de sequências, isto é, blocos maximais de um mesmo símbolo repetido. R sobe uma unidade onde dois vizinhos diferem: conta fronteiras, não caracteres.
L̄N/R, o comprimento médio das sequências. É a única grandeza que decide o resultado.ratioN/2R, ou sejaL̄/2. Acima de 1 a saída é menor do que a entrada.
De onde vem a fórmula
- Conta sequências, não caracteres. Em
0010111100001111os vizinhos diferem em cinco pontos, portanto há seis sequências e a linha mostraR=6. - O tamanho codificado é
2Re mais nada. Aquilo de que as sequências são feitas nunca entra na conta — seis sequências custam doze unidades, sejam píxeis, letras ou algarismos. - Divide:
ratio = N/2R = L̄/2. O equilíbrio fica assim emL̄ = 2, e é exatamente atingível — escreveAABBe as barras marcam 4 bytes à entrada e 4 à saída. - Os dois sentidos não são simétricos. Para cima não há limite: uma única sequência de um milhão de caracteres codifica-se num par. Para baixo o piso está em
0.50×e não pode ser batido, porque o pior que uma entrada consegue fazer é dar a cada caractere a sua própria sequência.
Como ler o que vê
Os quatro exemplos têm exatamente dezasseis caracteres, o que compensa lê-los como conjunto. Linha de imagem tem três sequências e dá 6 bytes. Sequências clássicas tem quatro e dá 8. Máscara de bits tem seis e dá 12. Pior caso tem dezasseis e dá 32. O mesmo comprimento à entrada e sai entre 6 e 32 bytes — um fator de cinco, decidido inteiramente por R. Escreve depois hello world: onze caracteres, dez sequências, 20 bytes. A prosa comum fica na parte baixa desse intervalo, e é essa toda a razão por que este método é uma peça dentro de compressores e não um compressor por si.
- Pressupõe
- Que um par custa exatamente 2 unidades, que um símbolo e uma contagem ocupam o mesmo, e que uma contagem pode ter qualquer tamanho. Os codificadores reais dão à contagem uma largura fixa — um byte, ou seja 255 — e têm de partir uma sequência mais longa em vários pares, o que empurra o equilíbrio um pouco acima de 2. O pressuposto de largura igual falha precisamente onde este método é melhor: num fax de 1 bit o símbolo ocupa um bit e a contagem não.
- Falha quando
- O piso de
0.50×não é um defeito à espera de solução. Um codificador sem perdas tem de ser reversível, de modo que entradas distintas deem saídas distintas; e há menos cadeias curtas do que longas para onde as enviar. Qualquer esquema que encurte sequer uma entrada alonga forçosamente outra. É um facto de contagem, não uma propriedade deste método. O PackBits, na terceira ideia acima, baixa o seu pior caso para um byte de controlo por cada 128 — menos de 1% — e mais longe ninguém vai, porque o piso pode descer sem limite mas nunca ser alcançado. O que este método faz é carregar esse custo por fora, numa leitura que se vê mexer.
Problema resolvido na íntegra
-
Codificação run-length de AAAAAABBBCCDDDDD em quatro pares 5 passos
A codificação por comprimento de corrida transforma AAAAAABBBCCDDDDD em quatro pares. Calcule a compressão e, em seguida, a condição exata sob a qual este esquema torna um ficheiro maior.
-
A codificação é a mais óbvia: substituir cada sequência pelo caráter e pelo seu comprimento. Dezasseis carateres reduzem-se a quatro pares.
-
Dois números descrevem qualquer entrada deste esquema — o seu comprimento e o seu número de sequências — e a sua razão é o comprimento médio das sequências. Aqui é 4.
-
Agora conte honestamente. Cada par custa dois símbolos, um caráter e uma contagem, pelo que a saída é 2R contra uma entrada de N. Mais nada sobre os dados importa.
-
Assim, o esquema ganha exatamente quando 2R < N, o que se rearranja num comprimento médio de sequência superior a 2. Aqui são 8 contra 16 — uma redução exata para metade — e a linha de veredito no painel diz a mesma coisa num único símbolo.
-
Abaixo desse limiar perde, e com um comprimento médio de sequência de 1 perde ao máximo: cada caráter torna-se um par, duplicando o ficheiro.
Resposta
A ferramenta apresenta N = 16 e R = 4, uma sequência média de 4 e uma poupança de 2×. A condição é o aspeto a reter: o RLE comprime se e só se as sequências tiverem em média mais de dois elementos, e é um dos poucos esquemas de compressão cujo ponto de equilíbrio é um único número que pode verificar a olho nu. Digite ABCD na caixa e veja-o expandir para o dobro do tamanho. Isso não é uma falha — é a razão pela qual o RLE sobrevive apenas onde as sequências são garantidas por construção: linhas de varrimento de fax, mapas de bits esparsos e as regiões uniformes de um JPEG após a quantização, nunca em texto geral.
-
Percurso de aprendizagem
Compressão manual
Referências (3)
- Insight block 3 — PackBits, and the control byte that bounds its worst case: Adobe Systems, TIFF Revision 6.0, section 9 (PackBits Compression), 1992 — the format where Apple's variant became a standard compression mode.
- The run lengths themselves as the thing to be coded: S. W. Golomb, "Run-length encodings (Corresp.)." IEEE Transactions on Information Theory 12(3), 399–401, 1966.
- And the earlier paper that measured how long runs in real pictures actually are: J. Capon, "A probabilistic model for run-length coding of pictures." IRE Transactions on Information Theory 5(4), 157–163, 1959.