Compressão para um fluxo único de dados

https://stackoverflow.com/questions/274196

07-07-2019
|

Pergunta

Eu tenho um grande número de arrays de inteiros. Cada um tem alguns milhares de números inteiros na mesma, e cada número inteiro é geralmente o mesmo que o anterior ou é diferente de apenas um único bit ou dois. Eu gostaria de diminuir cada matriz para baixo tão pequeno quanto possível para reduzir meu disco IO.

Zlib encolhe-lo para cerca de 25% do seu tamanho original. Isso é bom, mas eu não acho que seu algoritmo é particularmente adequado para o problema. Alguém sabe uma biblioteca de compressão ou algoritmo simples que pode executar melhor para este tipo de informação?

Update: zlib depois convertê-lo para uma série de XOR deltas encolhe-lo para cerca de 20% do tamanho original.

Solução

Se a maioria dos inteiros são realmente o mesmo que o anterior, e a diferença inter-símbolo geralmente pode ser expressa como um flip bit único, isso soa como um trabalho para XOR.

Tome um fluxo de entrada como:

e saída:

um pouco de código pseudo

compressed[0] = uncompressed[0]
loop
  compressed[i] = uncompressed[i-1] ^ uncompressed[i]

Temos agora reduzido a maior parte da produção para 0, mesmo quando um alto bit é alterado. A compressão RLE em qualquer outra ferramenta que você usa terá um dia de campo com este. Ele vai trabalhar ainda melhor em inteiros de 32 bits, e ainda pode codificar um inteiro radicalmente diferente aparecendo na corrente. Você está salvo o incômodo de lidar com bit-packing-se, como tudo permanece uma quantidade de tamanho int-.

Quando você quer para descomprimir:

uncompressed[0] = compressed[0]
loop
  uncompressed[i] = uncompressed[i-1] ^ compressed[i]

Isto também tem a vantagem de ser um algoritmo simples que vai correr muito, muito rápido, uma vez que é apenas XOR.

Outras dicas

Você considerou Run-length encoding ?

Ou tente o seguinte: Em vez de armazenar-se os números, você armazenar as diferenças entre os números. 1 1 2 2 2 3 5 torna-se 1 0 1 0 0 1 2. Agora, a maioria dos números que você tem que codificar são muito pequenas. Para armazenar um número inteiro pequeno, use um número inteiro em vez de um 32-bit você codificar na maioria das plataformas de 8 bits. Isso é um fator de 4 bem ali. Se você precisa fazer para estar preparado para lacunas maior do que isso, designar o alto-bit do inteiro de 8 bits para dizer "este número requer os próximos 8 bits bem".

Você pode combinar isso com codificação de comprimento de execução para ainda melhores taxas de compressão, dependendo de seus dados.

Nenhuma destas opções é particularmente difícil de implementar, e todos eles correm muito rápido e com muito pouca memória (ao contrário de, digamos, bzip).

Você quer pré-processar seus dados - reversível transformá-lo em alguma forma que é melhor adequado ao seu método de compressão de dados back-end, em primeiro lugar. Os detalhes dependerá tanto o método de compressão de back-end, e (mais criticamente) sobre as propriedades que você espera de dados que você está comprimindo.

No seu caso, zlib é um método de compressão de byte-wise, mas seus dados vem em (? 32-bit) inteiros. Você não precisa reimplementar zlib mesmo, mas você precisa ler sobre como ele funciona, então você pode descobrir como apresentá-lo com dados facilmente compressíveis, ou se é apropriado para seus propósitos em tudo.

Zlib implementa uma forma de Lempel-Ziv codificação. JPG e muitos outros usam codificação Huffman por seu backend. codificação de comprimento de execução é popular para muitos usos ad hoc. Etc, etc ...

Talvez a resposta é a pré-filtro das matrizes de uma maneira análoga à Filtering usadas para criar pequenas imagens PNG . Aqui estão algumas idéias para a direita fora do topo da minha cabeça. Eu não tentei essas abordagens, mas se você sentir vontade de jogar, que poderia ser interessante.

Quebre seus ints acima de cada em 4 bytes, então i ₀, i ₁, i ₂, ..., i _n torna-se b _0,0, b _0,1, b _0,2, b _0,3, b _1,0, b _1,1, b _1,2, b _{1, 3}, ..., b _{n, 0}, b _{n, 1}, b _{n, 2}, b _{N, 3}. Em seguida, escreva para fora todo o b _{i, 0} S, seguido pela b _{i, 1} s, b _{i, 2} s, e b < sub> i, 3 ?? s. Se a maior parte do tempo seus números diferem apenas por um bit ou dois, você deve obter corridas longas agradáveis ??de bytes repetidos, que devem comprimir muito bem usando algo como Run-Length Encoding ou zlib. Este é o meu favorito dos métodos I presentes.
Se os inteiros em cada matriz são relacionadas com a estreita colaboração com o anterior, talvez você possa armazenar o inteiro original, seguido por diffs contra a entrada anterior - isso deve dar um conjunto menor de valores para retirar, o que resulta tipicamente numa forma mais compactada.
Se você tiver vários pedaços diferentes, você ainda pode ter diferenças muito largo, mas se você é mais propensos a ter grandes diferenças numéricas que correspondem a (geralmente) um ou dois bits diferentes, você pode ser melhor fora com um esquema onde criar ahebyte matriz - usar os primeiros 4 bytes para codificar o primeiro número inteiro, e, em seguida, para cada entrada subsequente, o uso 0 ou mais bytes para indicar que os bits devem ser invertidos - armazenamento de 0, 1, 2, ..., ou 31 no byte, com uma sentinela (digamos 32) para indicar quando você está feito. Isto poderia resultar o número de bytes em bruto necessários para representar o número inteiro e a algo próximo de 2, em média, o que mais bytes proveniente de um conjunto limitado (0-32). Executar esse fluxo através zlib, e talvez você vai ser agradavelmente surpreendido.

Você tentou bzip2 para isso? http://bzip.org/

É sempre funcionou melhor do que zlib para mim.

Uma vez que a sua preocupação é reduzir IO de disco, você vai querer comprimir cada array de inteiros de forma independente, sem fazer referência a outros arrays de inteiros.

Uma técnica comum para o seu cenário é armazenar as diferenças, uma vez que um pequeno número de diferenças podem ser codificados com codewords curtas. Parece que você precisa vir para cima com seu próprio esquema de codificação para as diferenças, uma vez que são diferenças multi-bit, talvez usando um byte algo 8 bit assim como um ponto de partida:

1 bit para indicar que um novo inteiro completa segue, ou que este byte codifica uma diferença a partir do último número inteiro,
1 bit para indicar que existem mais bytes seguinte, registrando diferenças pouco mais simples para o mesmo número inteiro.
6 bits para registrar o número de bits para chave de seu inteiro anterior.

Se houver mais de 4 bits diferente, em seguida, armazenar o número inteiro.

Este regime não pode ser apropriado se você também tem um monte de códigos completamente diferentes, uma vez que vai demorar 5 bytes cada agora em vez de 4.

"Zlib encolhe-lo por um fator de cerca de 4x." significa que um arquivo de 100K agora ocupa negativo 300K; que é bastante impressionante por qualquer definição :-). Eu suponho que você quer dizer que encolhe-lo em 75%, ou seja, a 1/4 do seu tamanho original.

Uma possibilidade para uma compressão optimizado é como se segue (que assume um número inteiro de 32-bit e, no máximo, 3 bits mudança de elemento a elemento).

Output o primeiro inteiro (32 bits).
de saída o número de alterações de bits (n = 0-3, 2 bits).
de saída n bit especificadores (0-31, 5 bits cada).

O pior caso para esta compressão é de 3 mudanças de bits em cada inteiro (2 + 5 + 5 + 5 bits), que tenderão a 17/32 de tamanho original (46,875% de compressão).

Eu digo "tende para" desde o primeiro número inteiro é sempre de 32 bits, mas, para qualquer matriz de tamanho decente, que primeiro inteiro seria insignificante.

Melhor caso é um arquivo de inteiros iguais (sem alterações bits para cada inteiro, apenas os 2 bits zero) -. Este tenderá para 2/32 do tamanho original (93,75% de compressão)

Onde você média 2 bits diferente por inteiro consecutivo (como você diz é o seu caso comum), você vai ter 2 + 5 + 5 bits por inteiro que tenderá para compressão de 12/32 ou 62,5%.

O seu ponto de equilíbrio (zlib se dá a compressão de 75%) é de 8 bits por número inteiro que seriam

de um único bit mudanças (2 + 5 = 7 bits):. 80% das transições
de bit duplo mudanças (2 + 5 + 5 = 12 bits.): 20% das transições

Isto significa que sua média teria que ser de 1,2 bit mudanças por inteiro para fazer isso vale a pena.

Uma coisa que eu gostaria de sugerir olhando é 7zip -. Isso tem uma licença muito liberal e você pode vinculá-lo com o seu código (eu acho que a fonte está disponível também)

Eu aviso (para as minhas coisas de qualquer maneira) ele executa muito melhor do WinZip em uma plataforma Windows para que ele também pode zlib outperform.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow