Teoria: algoritmo de compressão que torna alguns arquivos menores, mas nenhum maior?

Question

Eu me deparei com essa pergunta;

"Um algoritmo de compactação sem perdas reivindica a garantia de tornar alguns arquivos menores e sem arquivos maiores.
É isto;

a) impossível

b) possível, mas pode ser executado por um período indeterminado,

c) possível para o fator de compressão 2 ou menos,

d) possível para algum fator de compressão? "

Estou inclinado para (a), mas não poderia dar uma explicação sólida sobre o porquê. (Vou listar os pensamentos que um amigo e eu tive como uma possível resposta)

Answer 1

Pelo princípio do orifício do pombo, dada uma corda de 10 bits, você tem 1024 entradas possíveis e precisa mapear para 9 bits ou menos, portanto, existem <1024 saídas.

Isso garante que o algoritmo tenha colisões (compressão com perdas) ou, em algum momento, escolherem devolver a entrada não modificada como saída.

Neste último caso, você não pode determinar como descomprimir uma sequência arbitrária de bits. (Pode ser uma entrada não modificada ou uma saída compactada de uma sequência de bits maior).

-> Impossível.

Answer 2

Apenas um pequeno esclarecimento da postagem de RJFalConer ...

Você só tem que ter algum Os arquivos ficando menores, portanto, a alegação de que uma sequência de 10 bits precisa mapear para 9 bits ou menos não está certa. Em particular, se alguém propôs um mecanismo de compressão, ele poderia Mapeie todas as cordas de 10 bits ou menos para exatamente a mesma saída (ou seja, uma transformação de identidade).

No entanto, somos informados de que existe pelo menos um arquivo que se torna menor. Sem perda de generalidade, considere isso começar com x bits e acabar como y bits, onde y é estritamente menor que x.

Agora considere o domínio de "arquivos com y bits ou menos", que tem 2^y+1-1 strings de bits (incluindo a vazia). Para que nenhum deles resulte em um arquivo maior, cada um precisa mapear um pouco para um pouco no mesmo domínio, ou seja, 2^y+1-1 arquivos compactados. No entanto, já sabemos que a sequência inicial de comprimento x bits se comprime para um desses valores - deixando apenas 2^y+1-2 Valores possíveis.

No isto aponte o princípio do buraco do pombo - você claramente não pode mapear 2^y+1-1 entradas para 2^y+1-2 Saídas sem repetir uma saída, que viola a reversibilidade da compressão.

Answer 3

a) impossível

Se você possui um arquivo que não pode ser compactado ainda mais, ainda precisará adicionar as informações, seja ele compactado ou não; portanto, nesse caso, o arquivo teria que crescer.

Answer 4

Eu sei que estou meio tarde, mas achei isso via Google e outra pessoa poderia fazer o mesmo, então vou postar minha resposta: a solução óbvia é a) impossible, também apontado por Jon Skeet (e btw há muitas provas em toda a Internet). Não estou questionando a impossibilidade de comprimir dados aleatórios, apenas para ficar claro desde o início; Entendi a teoria que fica por trás disso, e se você me perguntar - eu confio na matemática. : D

Mas, se tivermos permissão para Pense lateralmente, Definitivamente, poderíamos aproveitar o fato de que a questão não está bem definida, o que significa que ela não fornece uma definição estrita de "algoritmo de compressão" e das propriedades que deveria ter (mas para reduzir algum arquivos sem expandir ninguém).

Além disso, não coloca toda a condição nos arquivos a serem compactados, a única coisa em que está interessada é "Para tornar alguns arquivos menores e sem arquivos maiores".

Dito isto, agora temos pelo menos duas maneiras de mostrar que, de fato, ele existe um algoritmo desse tipo:

1. Podemos explorar o nome do arquivo para armazenar algumas das informações do arquivo (ou mesmo o arquivo inteiro, se o sistema de arquivos permitir, reduzindo assim cada arquivo para 0 bit). Trivialmente, poderíamos simplesmente decidir deixar deixar de tocar cada arquivo, exceto um, reduzindo -o a 0 bits e renomeando -o com um nome predefinido. Concordo que isso pode ser considerado trapaça, mas, novamente, não há restrições na pergunta inicial e esse algoritmo alcançaria efetivamente o objetivo (desde que ninguém renomeie o arquivo, é por isso que essa seria uma escolha de design muito ruim além de sendo inútil).

2. Podemos limitar o número de arquivos a serem compactados, digamos, aos pelo menos X bits de comprimento. Mais uma vez, uma solução trivial seria deixar todos os arquivos intocados, mas um, que podemos reduzir, tornando -o correspondente a um arquivo menor do que X bits. Agora nós fazemos Tenha um algoritmo que, citando literalmente, torna alguns arquivos menores e sem arquivos maiores; No entanto, ele executa uma restrição a todas as suas entradas possíveis (ou seja, não pode processar todos os arquivos).

Para aqueles que argumentam que isso não teria nenhum uso prático, digo que concordo com você ... mas ei, isso é teoria, e essa foi apenas uma dissertação teórica. ;)

Obviamente, se eu fizesse um teste e enfrentasse essa pergunta, eu colocaria um x em negrito no a), e então continue sem pensar muito sobre isso.

No entanto, é perfeitamente possível mostrar que, como a linguagem natural é intrinsecamente ambígua e a pergunta não é formalmente expressa, cada uma das outras respostas possíveis não é necessariamente errada: colocar as condições certas e, eventualmente, especificar mais claramente o que se entende por certos conceitos , podemos legalmente cumprir o objetivo de qualquer uma das outras opções listadas, fazendo algum tipo de truque e forçando o programa a alcançar o comportamento desejado.

Answer 5

e) possível

... com algumas restrições.

Recentemente me deparei Shoco, uma biblioteca de compressão de cordas para pequenas cordas. Lembrei -me dessa pergunta ao ler esta afirmação:

... A propriedade mais notável do shoco é que o tamanho compactado nunca excederá o tamanho da sua sequência de entrada, desde que seja ASCII simples.

Se você tem certeza de que os dados de entrada são simples ASCII, seu buffer de saída só precisa ser tão grande quanto a string de entrada

http://ed-von-schleck.github.io/shoco/#how-itworks

Answer 6

possível

to make some files smaller and no files larger

Se o algoritmo de compactação aumenta o arquivo, basta retornar o arquivo original.