sábado, 19 de setembro de 2009

Projeto: Extreme File Compression

Esse projeto permite comprimir arquivos de qualquer tamanho para arquivos de menos de 1KiB.
Impossível? É claro que não, mas também não espere que a decompressão demore menos de uns 10 milênios...

Como?
Acredito que você saiba o que é um algoritimo de file hashing, simplificado é algo como tirar um resumo (hash) de um arquivo X, aquele arquivo X só pode ter aquele resumo W, mas um resumo W pode ser o resumo de vários arquivos X Y Z.
Então, podemos dizer que é possível reconstruir um arquivo X, simplesmente sabendo seu hash W.
É claro que esse processo pode demorar muito tempo, pois temos que rodar por brute-force (força bruta), todas as combinações possíveis, e corremos o risco de achar diversos falsos positivos.
Também armazenamos no arquivo comprimido, o tamanho do arquivo X, assim evitamos correr por todos os tamanhos possíveis de arquivos até chegar ao destino.
Como resolver então?
Tenho duas idéias de como resolver esse problema:
A - Executar o Hashing de todos os arquivos possíveis desde 0 até chegarmos ao arquivo desejado, contando quantas vezes o hash do arquivo foi repetido, a descompressão se daria da mesma forma, até encontrar o arquivo desejado. - O tempo da compressão neste caso é igual ao tempo da descompressão, muitos anos mesmo.
B - Usar vários algoritmos de hasing diferentes sobre o arquivo desejado, a fim de evitar a ocorrência de falsos positivos, assim, somente o arquivo X, teria os hashs A, B, C, D, E, F, G, H, I, J, K, L, M e assim por diante. - Neste caso o tempo de compressão pode demorar apenas 1 hora, dependendo da quantidade de hashs usados... Há apenas um pequeno risco de haverem falsos positivos, mas nesse caso depende da matemática pura e simples....
Exemplo
Aqui um exemplo do que é brute-force, vamos exemplificar que nosso arquivo em 5 digitos, e por serem digitos ele é composto apenas de número, vamos procurar o CRC32 a3bff1c0, então vamos:
  1. 00000 - 4adc54f5
  2. 00001 - 3ddb6463
  3. 00002 - a4d235d9
  4. 00003 - d3d5054f
  5. 00004 - 4db190ec
  6. 00005 - 3ab6a07a
  7. 00006 - a3bff1c0 - achamos o arquivo contém 00006
Viva!!! Descomprimimos o arquivo, sorte a nossa que ele era o 7º da fila....
Mas no mundo real pode ser na trilionésima tentativa, ou um número que nem sei escrever por extenso.
No exemplo acima o arquivo comprimido poderia ter esse conteúdo:
EFC-#-5-CRC32-a3bff1c0-1
Não parece muito eficiente né, mas imagine um DVD de 4.7GB, no arquivo a seguir:

EFC-bin-4700000000-CRC32-d113d346-7872298821547701824
53 bytes contra 4700000000 bytes, um arquivo de 88.679.245 de vezes menor.
Quem sabe um HD de 2TiB:

EFC-bin-2199023255552-CRC32-1afd250-27819858736306.....296621735144842438121298
Mesma coisa, cortei o último item que é o repetições senão o blog não ia exibir, mas faz de conta que o file ficou com 1KiB, um arquivo 2.147.483.648 de vezes menor!!!!

Conclusão
O meu algoritmo de compressão é extremamente eficiente, mas não é eficaz, pois o tempo necessário para a descompressão é exageradamente grande, talvez com a computação quantica ele se torne viável.
Uma última vantagem dele, é que ele pode ser rodado em paralelo sem qualquer perda de eficiência, cada CPU pode rodar um range de arquivos...

Nenhum comentário: