Recentemente, deparei com o seguinte artigo interessante, que afirma compactar com eficiência conjuntos de dados aleatórios sempre em mais de 50%, independentemente do tipo e formato dos dados.
Basicamente, ele usa números primos para construir exclusivamente uma representação de blocos de dados de 4 bytes que são fáceis de descompactar, pois cada número é um produto exclusivo de números primos. Para associar essas seqüências aos primos, utiliza um dicionário.
Minha pergunta é:
- Isso é realmente viável, como sugerem os autores? Segundo o artigo, seus resultados são muito eficientes e sempre compactam dados em um tamanho menor. O tamanho do dicionário não será enorme?
- Não foi possível usar isso para comprimir iterativamente os dados compactados usando o mesmo algoritmo? É óbvio, e foi demonstrado, que tais técnicas (onde os dados compactados são compactados novamente tantas vezes quanto possível, reduzindo drasticamente o tamanho do arquivo) são impossíveis; de fato, não haveria bijeção entre o conjunto de todos os dados aleatórios e os dados compactados. Então, por que isso parece possível?
- Mesmo que a técnica ainda não esteja perfeita, ela pode obviamente ser otimizada e fortemente aprimorada. Por que isso não é mais conhecido / estudado? Se essas afirmações e resultados experimentais são verdadeiros, isso não revolucionaria a computação?
Respostas:
Isso é impossível. Você não pode compactar dados aleatórios , precisa de alguma estrutura para aproveitar. A compactação deve ser reversível; portanto, você não pode comprimir tudo em 50% porque há muito menos cadeias de comprimento do que as de comprimento n .n / 2 n
Existem alguns problemas importantes com o documento:
Eles usam 10 arquivos de teste sem qualquer indicação de seu conteúdo. Os dados são realmente aleatórios? Como eles foram gerados?
Eles afirmam atingir taxas de compactação de pelo menos 50%, enquanto seus dados de teste mostram que atingem no máximo 50%.
O que? Números primos são números primos, independentemente da base.
Problema nº 1 com descompressão: a fatoração primária é um problema difícil, como eles fazem isso com eficiência?
Problema # 2 com descompressão ( este é o kicker ): eles multiplicam os números primos juntos, mas, assim, você perde qualquer informação sobre a ordem, pois . Eu não acho que é possível descomprimir usando a técnica deles.2 ⋅ 5 = 10 = 5 ⋅ 2
Não acho que este artigo seja muito bom.
fonte
Vou adiar Tom van der Zanden, que parece ter lido o jornal e descoberto uma fraqueza no método. Embora eu não tenha lido o artigo em detalhes, partindo do resumo e da tabela de resultados, parece uma reivindicação amplamente crível.
O que eles afirmam é uma taxa de compactação consistente de 50% em arquivos de texto (não "todos os arquivos"), que eles observam ser quase o mesmo que LZW e cerca de 10% pior que a codificação Huffman (presumivelmente de ordem zero). Não é difícil conseguir compactar arquivos de texto em 50% usando métodos razoavelmente simples; é um trabalho de graduação em muitos cursos de ciência da computação.
Concordo que o artigo não seja muito bom como pesquisa publicada e não acho que seja bom para os revisores que isso foi aceito. Além dos óbvios detalhes ausentes que impossibilitam a reprodução dos resultados (por exemplo, quais eram os arquivos de texto) e nenhuma tentativa de vinculá-lo ao campo de compressão, não há sentido de que eles realmente entendam o que seu algoritmo está fazendo.
O site da conferência reivindica uma taxa de aceitação de 1: 4, o que faz você se perguntar o que eles rejeitaram.
fonte
Você pergunta:
Sim, claro. Mesmo para o exemplo escolhido a dedo ("A RAPOSA PRATA RÁPIDA SALTA SOBRE O CÃO PREGUIÇOSO"), eles não obtêm compactação, porque o dicionário contém todas as subseqüências de 4 bytes do texto (menos 4 bytes para a repetição de " THE ") ... e a versão" compactada "do texto devem incluir todo o dicionário mais toda essa porcaria de números primos.
Novamente, você parece ter uma boa compreensão intuitiva da situação. Você percebeu intuitivamente que nenhum esquema de compactação pode ser eficaz em todas as entradas, porque, se fosse, poderíamos aplicá-lo repetidamente para compactar qualquer entrada em um único bit - e depois no nada!
Em outras palavras: depois de compactar todos os seus arquivos .wav para .mp3, você não obterá nenhuma melhoria no tamanho do arquivo compactando-os. Se o seu compressor de MP3 tiver feito seu trabalho, não haverá mais padrões para o compressor ZIP explorar.
(O mesmo se aplica à criptografia: se eu pegar um arquivo com zeros e criptografá-lo de acordo com meu algoritmo de criptografia preferido, é melhor que o arquivo resultante não seja compressível , ou então meu algoritmo de criptografia está vazando "padrão" em sua saída!)
Essas alegações e resultados experimentais não são verdadeiros.
Como Tom van der Zanden já observado, o "algoritmo de compressão" de Chakraborty, Kar, e Guchait é falho na medida em que não só ele não alcançar qualquer taxa de compressão, é também irreversível (em mathspeak, "não bijective"): existem uma infinidade de textos "compactados" para a mesma imagem, porque o algoritmo deles é basicamente multiplicação e a multiplicação é comutativa.
Você deve se sentir bem ao saber que sua compreensão intuitiva desses conceitos levou à conclusão certa instantaneamente. E, se você puder poupar tempo, deve sentir pena dos autores do artigo, que claramente passaram muito tempo pensando sobre o assunto sem entendê-lo.
O diretório de arquivos um nível acima da URL que você postou contém 139 "artigos" dessa mesma qualidade, todos aparentemente aceitos nas "Anais da Conferência Internacional sobre Pesquisa Emergente em Computação, Informação, Comunicação e Aplicações". Parece ser uma conferência falsa do tipo usual. O objetivo de tais conferências é permitir que acadêmicos fraudulentos reivindiquem "publicação em um periódico", além de permitir que organizadores sem escrúpulos ganhem muito dinheiro. (Para mais informações sobre conferências falsas, consulte este tópico do reddit ou várias postagens do StackExchange sobre o assunto .) Conferências falsas existem em todos os campos. Apenas aprenda a confiar em seus instintos e não acredite em tudo que lê em um "processo de conferência", e você se sairá bem.
fonte
A entropia limita efetivamente o desempenho da compressão sem perdas mais forte possível. Portanto, não existe algoritmo que possa comprimir conjuntos de dados aleatórios sempre acima de 50%.
fonte
Os métodos de compressão, que são restauráveis, geralmente encontram um padrão e o reexpressam de maneira simplista. Alguns são muito inteligentes, outros muito simples. Em algum momento, não há padrão. O (s) processo (s) 'juntou' os dados ao seu padrão único mais simples. Qualquer tentativa de compactação desse ponto em diante resulta em um conjunto de dados maior ou dilui a exclusividade. Nos esquemas de compressão de números mágicos, sempre há uma falha, uma mão leve ou perda. desconfie de qualquer processo que pretenda executar o WinZip ou o RAR mais recente.
fonte