Compactação eficiente de dados binários simples

27

Eu tenho um arquivo que contém números binários ordenados de a :2 n - 102n1

0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

7z não compactou esse arquivo com muita eficiência (para n = 20, 22 MB foram compactados para 300 kB).

Existem algoritmos que podem reconhecer uma estrutura muito simples de dados e compactar arquivos em vários bytes? Também quero saber qual área de CS ou teoria da informação estuda tais algoritmos inteligentes. A "IA" seria muito ampla. Sugira palavras-chave mais concretas.
A noção de simetria deve desempenhar um papel fundamental na compactação de dados, mas as consultas de pesquisa "simetria na compactação de dados" e "teoria dos grupos na compactação de dados" surpreendentemente retornam quase nada relevante.

DSblizzard
fonte
11
Confira a complexidade de Kolmogorov, que é, de certo modo, a compressão ideal (até uma constante aditiva). Infelizmente, Kolmogorov complexidade não é computável ...
Yuval Filmus
12
Por que você precisa compactar esses dados? Você não pode simplesmente regenerá-lo sempre que precisar? (O que está intimamente relacionado à abordagem da complexidade Kolmogorov mencionada por @YuvalFilmus: a complexidade Kolmogorov é essencialmente a duração do programa mais curto que gera a saída).
precisa saber é o seguinte
7
Eu escrevi esse algoritmo no ensino médio, há 20 anos. Dada a sua entrada, ele teria sido compactado para "alguns bytes" (aproximadamente 3.500.000: 1 em um cenário ideal). No entanto, os dados raramente se parecem com isso, portanto, não é prático ter um algoritmo como esse. Algoritmos de compactação gerais precisam lidar com padrões complexos, não simples. Qualquer um pode escrever um algoritmo para armazenar dados lineares, mas armazenar dados interessantes é o desafio.
Phyrfox
3
Como n = 20 oferece 22 MB? Recebo 4.2 MB se estiver usando 4 bytes inteiros
njzk2
3
@JiK oh, ok. bem, isso seria uma primeira noção de compactação, não usando 8 bits para representar um único bit.
Njzk2

Respostas:

27

Esse parece ser um caso de uso claro para a compactação delta . Se for conhecido a priori, isso é trivial: armazene o primeiro número literalmente e, para cada próximo número, armazene apenas a diferença em relação ao anterior. No seu caso, isso darán

0
1
1
1
1
...

Com a codificação simples de duração da execução, isso pode ser armazenado no espaço , pois existem apenas grupos (ou seja, dois) de deltas diferentes.O ( 1 )O(n)O(1)

Se não for conhecido, a coisa mais simples seria uma pesquisa de força bruta pelo tamanho da palavra para o qual essa representação delta / comprimento de execução fica mais curta. Talvez faça apenas essa busca por pedaços do tamanho escolhidos aleatoriamente , para amortizar a sobrecarga de encontrar , mantendo uma boa confiabilidade.n nNn

Diferentemente da proposta “tudo ou nada” da DW, a compactação delta com codificação de duração da execução pode realmente fornecer taxas de compactação sensatas para alguns tipos simples de conteúdo do mundo real, como áudio de baixa resolução. (Portanto, é adequado para compactação de áudio de baixa qualidade, latência muito baixa e baixa potência.)

leftaroundabout
fonte
44

Claro, claro que existem algoritmos. Aqui está o meu algoritmo:

  1. Primeiro, verifique se o arquivo contém números binários ordenados de a 2 n - 1 , para alguns n . Nesse caso, escreva um bit 0 seguido de n um bit seguido por um bit 0.02n1nn

  2. Caso contrário, escreva um bit e, em seguida, escreva a compactação 7z do arquivo.

Isso é extremamente eficiente para arquivos dessa estrutura específica.

O ponto é: não há almoço grátis na compactação de dados. Você poderá criar um algoritmo de compactação que comprima bem um tipo de arquivo, com o custo de compactar outros piores. Mas, se você sabe a priori algo sobre a natureza dos arquivos que estará compactando, poderá otimizar seu algoritmo para esse tipo específico de arquivo.

A área é "compactação de dados". Veja nossa tag de e leia os livros sobre compactação de dados.

DW
fonte
5
O trabalho de um compressor é reconhecer padrões comuns e explorá-los. Não é como se esse padrão fosse incomum ou obscuro. Portanto, é uma pergunta natural perguntar por que não é explorada. Dizendo a ele que existe uma troca ou dando a ele um algoritmo que falha em tudo, exceto que o padrão é um total desvio.
Mehrdad
17
Claro parece incomum para mim. Isso surgiria raramente nos dados da vida real, em comparação com os tipos de padrões que os bons compressores procuram.
Amalloy # 8/17
17
@ Mehrdad Não é uma brincadeira sarcástica: é o ponto principal . Para qualquer padrão X que é simplesmente gerado e verificado, existe um algoritmo de compressão que procura esse padrão e lida com ele. Portanto, esta é a resposta para qualquer pergunta na linha de "Existe um algoritmo de compactação que lida com esse X?" Claro, sempre existe um algoritmo que procura padrões um pouco mais complexos. E há um que procura padrões um pouco mais complexos do que aquele também ad infinitum . Sua objeção é infundada.
David Richerby
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Gilles 'SO- stop be evil'
Uma aplicação extrema desse princípio são os links magnéticos bittorrent, nos quais qualquer arquivo ou coleção de arquivos de qualquer tamanho é simplesmente representada (compactada) em 160 bits de dados fixos. É claro que existe o risco de colisão de hash poder ocorrer.
Slebetman
17

Qualquer coisa usando um BWT (transformação Burrows – Wheeler) deve ser capaz de compactar isso muito bem.

Meu teste rápido do Python:

>>> import gzip
>>> import lzma
>>> import zlib
>>> import bz2
>>> import time
>>> dLen = 16
>>> inputData = '\n'.join('{:0{}b}'.format(x, dLen) for x in range(2**dLen))
>>> inputData[:100]
'0000000000000000\n0000000000000001\n0000000000000010\n0000000000000011\n0000000000000100\n000000000000010'
>>> inputData[-100:]
'111111111111010\n1111111111111011\n1111111111111100\n1111111111111101\n1111111111111110\n1111111111111111'
>>> def bwt(text):
    N = len(text)
    text2 = text * 2
    class K:
        def __init__(self, i):
            self.i = i
        def __lt__(a, b):
            i, j = a.i, b.i
            for k in range(N): # use `range()` in Python 3
                if text2[i+k] < text2[j+k]:
                    return True
                elif text2[i+k] > text2[j+k]:
                    return False
            return False # they're equal

    inorder = sorted(range(N), key=K)
    return "".join(text2[i+N-1] for i in inorder)

>>> class nothing:
    def compress(x):
        return x

>>> class bwt_c:
    def compress(x):
        return bwt(x.decode('latin_1')).encode('latin_1')

>>> for first in ('bwt_c', 'nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
    fTime = -time.process_time()
    fOut = eval(first).compress(inputData)
    fTime += time.process_time()
    print(first, fTime)
    for second in ('nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
        print(first, second, end=' ')
        sTime = -time.process_time()
        sOut = eval(second).compress(fOut)
        sTime += time.process_time()
        print(fTime + sTime, len(sOut))

bwt_c 53.76768319200005
bwt_c nothing 53.767727423000224 1114111
bwt_c lzma 53.83853460699993 2344
bwt_c zlib 53.7767307470001 5930
bwt_c gzip 53.782549449000044 4024
bwt_c bz2 54.15730512699997 237
nothing 6.357100005516259e-05
nothing nothing 0.0001084830000763759 1114111
nothing lzma 0.6671195740000258 27264
nothing zlib 0.05987233699988792 118206
nothing gzip 2.307255977000068 147743
nothing bz2 0.07741139000017938 187906
lzma 0.6767229399999906
lzma nothing 0.6767684639999061 27264
lzma lzma 0.6843232409999018 27324
lzma zlib 0.6774435929999072 27280
lzma gzip 0.6774431810001715 27292
lzma bz2 0.6821310499999527 27741
zlib 0.05984937799985346
zlib nothing 0.05989508399989063 118206
zlib lzma 0.09543156799986718 22800
zlib zlib 0.06264000899977873 24854
zlib gzip 0.0639041649999399 24611
zlib bz2 0.07275534999985211 21283
gzip 2.303239570000187
gzip nothing 2.303286251000145 147743
gzip lzma 2.309592880000082 1312
gzip zlib 2.3042639900002087 2088
gzip gzip 2.304663197000309 1996
gzip bz2 2.344431411000187 1670
bz2 0.07537686600016968
bz2 nothing 0.07542737000017041 187906
bz2 lzma 0.11371452700018381 22940
bz2 zlib 0.0785322910001014 24719
bz2 gzip 0.07945505000020603 24605
bz2 bz2 0.09332576600013454 27138

(Os números aqui são 'first_compressor second_compressor time_taken bytes_out')

(BWT retirado daqui )

Isso ainda é 'não apenas alguns bytes', mas ainda assim é muito melhor do que apenas o gzip. BWT + bz2 reduz para 237 bytes de 1114111 para uma entrada de 16 bits, por exemplo.

Infelizmente, os BWTs são muito lentos e precisam de memória para muitos aplicativos. Especialmente considerando que essa é uma implementação ingênua em Python - na minha máquina, fico sem memória RAM antes de 2 ** 20.

Com o Pypy, eu fui capaz de executar a entrada 2 ** 20 completa e a compactou para 2611 bytes com um BWT seguido por bz2. Mas demorando mais de 3 minutos e atingindo mais de 4 GB de RAM usado ...

Infelizmente, essa abordagem ainda é um espaço de saída O (2 ^ n), ao que parece - pelo menos a partir do ajuste de curva 1..20.

TLW
fonte
Você pode se livrar evalfazendo: for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):e fOut = first.compress(inputData).
Kasperd
@ kasperd - como eu imprimiria os nomes nesse caso? Pessoalmente, é mais simples (e menos propenso a erros) fazer uma avaliação do que tentar manter os nomes + referências sincronizados.
TLW
5
Primeiro o bwt e depois o bz2 comprime isso muito bem. Esse é um comportamento extremamente estranho e provavelmente devido a esse padrão exato. Observe que você está executando o bwt duas vezes (o bz2 é baseado no BWT), o que geralmente resulta em pior compactação. Observe também que o bwt hoje geralmente roda na 4 times block sizememória (por exemplo, ~ 4 MB para isso) e em velocidades de >10 MB/s(eu sou o autor de um algoritmo de compactação / biblioteca do bwt), que é bastante utilizável para muitas aplicações. Note que mesmo o gzip produz resultados compressíveis muito bons. Obrigado por compartilhar. Não conheço nenhuma pesquisa sobre o uso do bwt duas vezes.
Christoph
3
@Christoph - Eu sei que o bz2 é baseado no BWT ... Na verdade, eu comecei a escrever uma resposta para o efeito de 'apenas usar o bz2', mas descobri que ele não se compactava tão bem quanto eu esperava, foi 'hein 'e decidi ver se meu próprio BWT seria melhor. Só eu precisava de um compressor para a saída e fui 'pode tentar diferentes compressores para ver o que acontece'.
TLW
11
@Christoph - dei outra olhada. Dois bwts desses dados geram algo extremamente acessível à codificação RLE. Como, se você contar o número de pares RLE necessários para 0, 1, 2, ... BWTs aninhadas em uma entrada de 16 bits, você tem 622.591 1.081.343 83 ...
TLW
10

A codificação PNG faz exatamente o que você deseja. Também funciona com dados da vida real, não apenas com dados extremamente organizados.

Em PNG, cada linha é codificada com um filtro, dos quais 4 são especificados. Uma delas é "codificar esse pixel como a diferença entre seu valor e o valor do pixel acima dele". Após a filtragem, os dados são compactados usando DEFLATE.

Essa filtragem é um exemplo específico da codificação delta mencionada por leftaroundabout em sua resposta, exceto que, em vez de segui-la com a codificação de comprimento de execução, você segue com o algoritmo DEFLATE mais poderoso. Ele atinge o mesmo objetivo, apenas o DEFLATE manipulará uma variedade maior de entradas, enquanto ainda fornece as taxas de compactação desejáveis.

Outra ferramenta que é frequentemente usada em dados científicos em que o filtro simples + DEFLATE não é tão eficaz é a codificação RICE. No RICE, você pega um bloco de valores e gera todos os bits mais significativos primeiro e depois os segundos bits mais significativos, até os bits menos significativos. Você então comprime o resultado. Para seus dados que não serão tão eficazes quanto a filtragem no estilo PNG (porque seus dados são perfeitos para a filtragem PNG), mas para muitos dados científicos, eles tendem a levar a bons resultados. Em muitos dados científicos, vemos que o bit mais significativo tende a mudar lentamente, enquanto o menos significativo é quase aleatório. Isso separa os dados altamente previsíveis dos dados altamente entrópicos.

0000000000       00000  most significant bits
0000000001       00000
0000000010  =>   00000
0000000011       00000
0000000100       00000
                 00000
                 00000
                 00001
                 00110
                 01010 least significant bits
Cort Ammon - Restabelecer Monica
fonte
5

Qualquer algoritmo prático que procure estruturas específicas seria limitado apenas às estruturas codificadas nele. Você poderia corrigir o 7z para reconhecer essa sequência específica, mas com que frequência essa estrutura específica ocorrerá na vida real? Não é suficiente o suficiente para garantir o tempo necessário para verificar as entradas dessa entrada.

Praticamente à parte, pode-se conceber o compressor perfeito como um algoritmo que tenta construir o programa mais curto que produz uma determinada saída. Escusado será dizer que não há maneiras práticas de fazer isso. Mesmo que você tenha tentado uma enumeração de força bruta de todos os programas possíveis e verificado se eles produziram a saída desejada ( não é uma ideia totalmente insana ), você encontrará o problema da parada , o que significa que terá que abortar as execuções de teste após um certo número das etapas de execução, antes que você saiba se esse programa definitivamente não pode produzir a saída desejada.

A árvore de pesquisa para uma abordagem de força bruta cresce exponencialmente com a duração do programa e não é prática para todos, exceto para os programas mais simples (algo como 5 a 7 instruções).

Roman Starkov
fonte
n
11
nnn+1n1
Bem, ferramentas como o Mathematica encontrar funções para muitas seqüências ...
Raphael
3

As taxas de compressão dependem inteiramente do descompressor alvo. Se o descompactador não puder decodificar números sequenciais de 4 bytes de forma mais compacta que 4 bytes por número, você será o SOL.

Existem várias coisas que permitiriam a codificação de números seqüenciais. Por exemplo, uma codificação diferencial. Você pega n bytes de cada vez e, em seguida, pega a diferença ou o xor dos bits e compacta o resultado. Isso adiciona quatro opções aqui para tentar para cada contagem de bytes: identidade a'[i] = a[i]; diferença a'[i] = a[i-1]-a[i]; diferença inversa a'[i] = a[i]-a[i-1]; e o xor a'[i] = a[i]^a[i-1]. Isso significa adicionar 2 bits para selecionar os métodos e uma contagem de bytes para 3 de 4 opções.

No entanto, nem todos os dados são uma sequência dos registros de comprimento fixo. A codificação diferencial não faz sentido para isso (a menos que o compressor possa empiricamente provar que funciona para um pouco de dados).

catraca arrepiante
fonte