Os PRNGs podem ser usados ​​para compactar magicamente coisas?

Esta ideia me ocorreu quando criança aprendendo a programar e encontrando PRNG pela primeira vez. Ainda não sei o quão realista é, mas agora há troca de pilhas.

Aqui está o esquema de uma criança de 14 anos para um incrível algoritmo de compactação:

Pegue um PRNG e faça o seed com seed spara obter uma longa sequência de bytes pseudo-aleatórios. Para transmitir essa sequência para outra parte, você só precisa comunicar uma descrição do PRNG, a semente apropriada e o tamanho da mensagem. Por uma sequência suficientemente longa, essa descrição seria muito mais curta que a própria sequência.

Agora, suponha que eu possa inverter o processo. Com tempo e recursos computacionais suficientes, eu poderia fazer uma busca por força bruta e encontrar uma semente (e PRNG, ou seja, um programa) que produz a sequência desejada (digamos, uma foto divertida de gatos sendo travessos).

Os PRNGs se repetem após a geração de um número suficientemente grande de bits, mas, comparada aos ciclos "típicos", minha mensagem é bastante curta e, portanto, isso não parece ser um problema.

Voila, uma maneira eficaz (se bem que rube-Goldbergiana) de compactar dados.

Então, assumindo:

• A sequência que desejo compactar é finita e conhecida antecipadamente.
• Não tenho pouco dinheiro ou tempo (desde que seja necessária uma quantidade finita de ambos)

Eu gostaria de saber:

• Existe uma falha fundamental no raciocínio por trás do esquema?
• Qual é a maneira padrão de analisar esse tipo de experimento mental?

Sumário

Frequentemente, boas respostas deixam claro não apenas a resposta, mas o que realmente estava perguntando. Obrigado pela paciência de todos e respostas detalhadas.

Aqui está a minha enésima tentativa de resumo das respostas:

• O ângulo PRNG / semente não contribui com nada, não passa de um programa que produz a sequência desejada como saída.
• O princípio do pigeonhole: existem muito mais mensagens de comprimento> k do que programas (geradores de mensagens) de comprimento <= k. Portanto, algumas seqüências simplesmente não podem ser a saída de um programa menor que a mensagem.
• Vale ressaltar que o intérprete do programa (mensagem) é necessariamente corrigido previamente. E seu design determina o subconjunto (pequeno) de mensagens que podem ser geradas quando uma mensagem de comprimento k é recebida.

Nesse ponto, a idéia original do PRNG já está morta, mas há pelo menos uma última pergunta a ser resolvida:

• P: Posso ter sorte e descobrir que minha mensagem longa (mas finita) é apenas a saída de um programa de comprimento <k bits?

Estritamente falando, não é uma questão de sorte, pois o significado de toda mensagem possível (programa) deve ser conhecido com antecedência. Ou é o significado de alguma mensagem de <k bits ou não é .

Se eu escolher uma mensagem aleatória de> = k bits aleatoriamente (por que eu faria isso?), Em qualquer caso, eu teria uma probabilidade de desaparecer de poder enviá-la usando menos de k bits e uma quase certeza de não ser capaz de enviar usando menos de k bits.

OTOH, se eu escolher uma mensagem específica de> = k bits dentre aquelas que são a saída de um programa com menos de k bits (supondo que exista essa mensagem), então, de fato, estou aproveitando os bits já transmitidos ao receptor (o design do intérprete), que conta como parte da mensagem transferida.

Finalmente:

• P: O que é todo esse negócio de complexidade de entropia / kolmogorov ?

Por fim, ambos nos dizem a mesma coisa que o princípio (mais simples) do buraco de pombo nos diz sobre o quanto podemos comprimir: talvez nem um pouco, talvez alguns, mas certamente não tanto quanto imaginamos (a menos que trapacemos).

Você tem um novo e brilhante esquema de compactação, não é? Está bem então...

♫ Vamos todos jogar, o jogo de entropia ♫

Apenas para ser simples, assumirei que você deseja compactar mensagens de exatamente bits, para alguns n fixos . No entanto, você deseja usá-lo para mensagens mais longas; portanto, é necessário diferenciar sua primeira mensagem da segunda (não pode ser ambíguo o que você compactou).$n$$n$

Portanto, seu esquema é determinar alguma família de PRNG / sementes, de modo que, se você deseja compactar, digamos, , basta escrever um número k , que identifica algum combo semente / PRNG pré-computado (e compartilhado) que gera esses bits após n consultas. Bem. Quantas cadeias de bits diferentes de comprimento n existem? 2 n (você tem n opções entre dois itens; 0 e 1 ). Isso significa que você terá que calcular 2 n desses combos. Sem problemas. No entanto, você precisa escrever k em binário para eu ler. Como grande pode k começar? Bem, pode ser tão grande quanto $01000111001$$k$$n$$n$$2^n$$0$$1$$2^n$$k$$k$ . Quantos bits eu preciso escrever 2 n ? log 2 n = n .$2^n$$2^n$$\log{2^n} = n$

Opa! Seu esquema de compactação precisa de mensagens desde que você esteja compactando!

"Haha!", Você diz, "mas esse é o pior caso! Uma das minhas mensagens será mapeada para , que precisa de apenas 1 bit para representar! Vitória!"$0$$1$

Sim, mas suas mensagens devem ser inequívocas! Como posso distinguir seguido por 0 de 10 ? Como algumas de suas chaves têm o comprimento n , todas devem estar, ou não sei por onde você começou e parou.$1$$0$$10$$n$

$n$$\log{n}$$0$$\log{n}$

$\log{n}$$1$

$2^n$$2^n$$n$

$2^n$

$a=0000000011010$$b=111111110101000$$a\rightarrow 0$$b\rightarrow 1$$n=1$

"Haha!", Você diz, "mas eu posso simplesmente determinar que essas mensagens estúpidas são raras! Tornarei as raras grandes e as comuns pequenas! Então, em média, eu ganho!"

$n$$i$$p_i$$H = \sum_{i=1}^np_i\log(1/p_i)$$a=000111010101$$a\rightarrow0$$x\rightarrow1x$$1$$H$$H$

Qualquer coisa que afirme vencer a entropia provavelmente não está fornecendo informações suficientes para recuperar a mensagem compactada de forma inequívoca ou está errada. A entropia é um conceito tão poderoso que podemos limitar o tempo de execução de alguns algoritmos (porque às vezes até o limite superior ), porque se eles rodam muito rápido (ou muito devagar), devem estar fazendo algo que viola a entropia .

$2^N-1$$N$$2^N$$N$

Na vida real, geralmente sabemos algo sobre a sequência que estamos comprimindo, digamos que seja uma voz ou uma imagem. No caso de compressão sem perdas, o teorema da codificação de fontes de Shannon mostra que a taxa de compressão ideal é igual à entropia da fonte. Para codificação com perdas, existem outros teoremas na teoria da informação (teoria da distorção da taxa). Portanto, mesmo neste caso, há um limite para o quanto você pode compactar dados.

$s$$k$$2^k$$n$$2^n$$n$$s$

(Como outra resposta observada, isso acontecerá para qualquer função de compactação que você escolher.)

Além de outros pontos já respondidos, só quero adicionar este link: https://www.schneier.com:443/blog/archives/2009/09/the_doghouse_cr.html

Agora, a produção anual de energia solar é de cerca de 1,21 × 10 ^ 41 ergs. Isso é suficiente para alimentar cerca de 2,7 × 10 ^ 56 alterações de bit único em nosso computador ideal; mudanças de estado suficientes para colocar um contador de 187 bits em todos os seus valores. Se construíssemos uma esfera de Dyson ao redor do sol e capturássemos toda sua energia por 32 anos, sem nenhuma perda, poderíamos alimentar um computador para contar até 2 ^ 192. Obviamente, não teria energia sobrando para realizar cálculos úteis com esse contador.

Portanto, apenas a iteração (sem comparação ...) para encontrar uma constelação válida de 187 bits dos dados desejados levaria sob condições ideais (não atingíveis) mais energia do que o sol emite durante um ano.

Uma prova muito rápida de que um compressor universal não pode existir. Vamos supor que você faça um e comprima uma entrada. Agora, iterativamente comprima a saída do seu programa. Se você sempre puder reduzir o tamanho, ele ficará cada vez menor a cada passo, até reduzir para 1 bit.

Você poderia argumentar que, talvez, a saída do seu algoritmo tenha uma estrutura que não possa ser mais compactada, mas então você poderia aplicar um embaralhamento determinístico * antes de recomprimir.

Nota de rodapé: Alguns embaralhamento determinístico realmente ajudam em alguns esquemas de compactação: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim

O uso de um PRNG para "compactação" é basicamente útil em uma situação: quando é necessário usar um conjunto de dados "aleatórios" e registrar compactamente quais dados foram usados. A maioria dos geradores pseudo-aleatórios pode gerar apenas uma fração minúscula de sequências possíveis, mas se for necessário apenas um número pequeno a moderado de sequências "aleatórias", a fração de sequências possíveis que um PRNG pode gerar geralmente será mais do que adequada.

Se a sequência de dados que se deseja armazenar ocorrer coincidentemente para coincidir com o que um determinado PRNG geraria com a semente correta, o armazenamento da semente pode ser uma alternativa compacta para armazenar os dados. A menos que a fonte de dados seja tal que essas correspondências provavelmente ocorram, elas serão tão raras que a procura por elas não valerá a pena.

Algo a considerar a acrescentar à cacofonia de respostas que afirmam por que existem algumas strings que não podem ser compactadas devido à natureza injetiva da descompressão, por definição, e ao universo limitado de strings compactadas das quais selecionar para representar mensagens é: a maioria das cordas não pode ser comprimida porque há muito mais entropia alta, cordas desordenadas do que as entrópicas mais baixas e estruturadas, dando origem à condição que vemos na prática que: a compressão é na maioria das vezes útil, uma vez que as mensagens que na maioria das vezes, deseja comprimir são os que mais frequentemente possuem alguma alíquota de ordem e estrutura e, por esse motivo, fazem parte do universo muito menor de objetos de baixa entropia. Isso significa que é possível que, escolhendo um comprimento de saída adequado, podemos comprimir tudo no universo menor e estruturado. O termo estruturado, entropia e ordenado aqui é deliberadamente impreciso, para refletir as definições subjetivas da semântica e utilidade das mensagens que desejamos compactar.

E em resposta direta à solicitação do interlocutor: * sim, é claro que você pode ter sorte e descobrir que a saída do seu PRNG é a mensagem exata que você deseja compactar, apenas que muitas vezes não encontrará esse caso, porque a própria propriedade que caracteriza um PRNG, a saber, sua capacidade de produzir uma variedade (quase) interminável de cadeias diferentes, torna concomitantemente improvável produzir a sua.

É claro que você pode atenuar essa improbabilidade usando um PRNG para percorrer um "gráfico de domínio" de transições palavra a palavra, e aumenta muito a probabilidade da aparição de sua mensagem e também descobre que deve agora adicionar o gráfico de domínio à mensagem compactada comprimento.