Outro usuário deseja gravar novos dados no disco rígido, mas não tem espaço livre suficiente para fazer isso. Também não quero apagar nada, pois “tudo é muito importante e necessário”. E o que devemos fazer com isso?
Ninguém tem esse problema. Existem terabytes de informações em nossos discos rígidos e essa quantidade não tende a diminuir. Mas quão único é isso? No final das contas, todos os arquivos são apenas conjuntos de bits de determinado comprimento e, muito provavelmente, o novo não é muito diferente daquele que já está armazenado.
É claro que a busca por informações já armazenadas em um disco rígido é, se não um fracasso, pelo menos não é uma tarefa eficaz. Por outro lado, se a diferença for pequena, então você pode ajustar um pouco...
TL;DR - a segunda tentativa de falar sobre um estranho método de otimização de dados usando arquivos JPEG, agora de uma forma mais compreensível.
Sobre bits e diferença
Se você pegar dois dados completamente aleatórios, então, em média, metade dos bits que eles contêm coincidem. Na verdade, entre os layouts possíveis para cada par ('00, 01, 10, 11′), exatamente metade tem os mesmos valores, tudo é simples aqui.
Mas é claro, se pegarmos apenas dois arquivos e encaixarmos um no segundo, perderemos um deles. Se salvarmos as alterações, simplesmente reinventaremos , que existe perfeitamente sem nós, embora geralmente não seja usado para os mesmos fins. Podemos tentar incorporar uma sequência menor em uma sequência maior, mas mesmo assim corremos o risco de perder segmentos críticos de dados se os usarmos de forma imprudente em tudo.
Entre o que e o que então a diferença pode ser eliminada? Bem, isto é, um novo arquivo escrito pelo usuário é apenas uma sequência de bits, com a qual não podemos fazer nada por si só. Então você só precisa encontrar bits no disco rígido que possam ser alterados sem a necessidade de armazenar a diferença, para que você possa sobreviver à perda sem consequências graves. E faz sentido alterar não apenas o arquivo no próprio FS, mas algumas informações menos confidenciais dentro dele. Mas qual e como?
Métodos de ajuste
Arquivos compactados com perdas vêm em socorro. Todos esses jpegs, mp3s e outros, embora compactados com perdas, contêm vários bits que podem ser alterados com segurança. É possível utilizar técnicas avançadas que modificam imperceptivelmente seus componentes em vários estágios de codificação. Espere. Técnicas avançadas... modificação imperceptível... um pedaço no outro... é quase como !
Na verdade, incorporar uma informação em outra lembra seus métodos como nada mais. Também me impressiona a imperceptibilidade das alterações operadas nos sentidos humanos. Onde os caminhos divergem é no sigilo: nossa tarefa se resume ao usuário inserir informações adicionais em seu disco rígido; isso só irá prejudicá-lo. Ele vai esquecer novamente.
Portanto, embora possamos utilizá-los, precisamos fazer algumas modificações. E então vou contar e mostrá-los usando um dos métodos existentes e um formato de arquivo comum como exemplo.
Sobre chacais
Se você realmente apertar, será a coisa mais compressível do mundo. Estamos, é claro, falando de arquivos JPEG. Não só existem inúmeras ferramentas e métodos para incorporar dados nele, mas também é o formato gráfico mais popular do planeta.
Porém, para não se dedicar à criação de cães, é necessário limitar seu ramo de atuação em arquivos deste formato. Ninguém gosta de quadrados monocromáticos que aparecem devido à compactação excessiva, então você precisa se limitar a trabalhar com um arquivo já compactado, evitando a recodificação. Mais especificamente, com coeficientes inteiros, que permanecem após as operações responsáveis pela perda de dados - DCT e quantização, que são perfeitamente exibidos no esquema de codificação (graças ao wiki da Biblioteca Nacional Bauman):
Existem muitos métodos possíveis para otimizar arquivos JPEG. Existe otimização sem perdas (jpegtran), existe otimização "“, que na verdade contribuem com outra coisa, mas não nos importamos com eles. Afinal, se o usuário está pronto para incorporar uma informação em outra para aumentar o espaço livre em disco, então ou ele otimizou suas imagens há muito tempo ou não quer fazer isso por medo de perder qualidade.
F5
Toda uma família de algoritmos se enquadra nessas condições, com as quais você pode se familiarizar . O mais avançado deles é o algoritmo de Andreas Westfeld, trabalhando com os coeficientes da componente de brilho, já que o olho humano é o menos sensível às suas alterações. Além disso, utiliza uma técnica de incorporação baseada na codificação matricial, o que permite fazer menos alterações ao incorporar a mesma quantidade de informações, quanto maior o tamanho do contêiner utilizado.
As próprias mudanças se resumem a reduzir o valor absoluto dos coeficientes em um sob certas condições (ou seja, nem sempre), o que permite usar F5 para otimizar o armazenamento de dados no disco rígido. A questão é que o coeficiente após tal alteração provavelmente ocupará menos bits após a codificação Huffman devido à distribuição estatística dos valores em JPEG, e os novos zeros darão um ganho ao codificá-los usando RLE.
As modificações necessárias se resumem em eliminar a parte responsável pelo sigilo (reorganização de senhas), que economiza recursos e tempo de execução, e adicionar um mecanismo para trabalhar com muitos arquivos em vez de um por vez. É improvável que o leitor esteja interessado no processo de mudança com mais detalhes, então vamos passar para uma descrição da implementação.
Alta tecnologia
Para demonstrar como funciona essa abordagem, implementei o método em C puro e fiz uma série de otimizações tanto em termos de velocidade de execução quanto de memória (vocês não imaginam quanto pesam essas imagens sem compressão, antes mesmo do DCT). Plataforma cruzada obtida usando uma combinação de bibliotecas , и , pelo que lhes agradecemos. Tudo isso é montado por 'make', então os usuários do Windows desejam instalar algum Cygwin para avaliação ou lidar com o Visual Studio e as bibliotecas por conta própria.
A implementação está disponível na forma de um utilitário de console e uma biblioteca. Os interessados podem saber mais sobre a utilização deste último no leia-me do repositório do Github, link que anexarei no final do post.
Como usar?
Com cuidado. As imagens usadas para empacotamento são selecionadas pesquisando usando uma expressão regular no diretório raiz fornecido. Após a conclusão, os arquivos podem ser movidos, renomeados e copiados à vontade dentro de seus limites, alterar arquivos e sistemas operacionais, etc. No entanto, você deve ser extremamente cuidadoso e não alterar o conteúdo imediato de forma alguma. Perder o valor de um bit pode impossibilitar a recuperação de informações.
Após a conclusão, o utilitário deixa um arquivo especial contendo todas as informações necessárias para a descompactação, incluindo dados sobre as imagens utilizadas. Por si só, pesa cerca de alguns kilobytes e não tem nenhum impacto significativo no espaço ocupado em disco.
Você pode analisar a capacidade possível usando o sinalizador '-a': './f5ar -a [pasta de pesquisa] [expressão regular compatível com Perl]'. A compactação é feita com o comando './f5ar -p [pasta de pesquisa] [expressão regular compatível com Perl] [arquivo compactado] [nome do arquivo]' e a descompactação com './f5ar -u [arquivo compactado] [nome do arquivo recuperado ]' .
Demonstração de trabalho
Para mostrar a eficácia do método, carreguei uma coleção de 225 fotos totalmente gratuitas de cães do serviço e encontrei nos documentos um grande pdf de 45 metros do segundo volume Knuta.
A sequência é bastante simples:
$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/
$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 17.0s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 39.4s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.4s
Decompressing... done in 21.0s
Writing extracted data... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs/
551M dogs/Capturas de tela para fãs
O arquivo descompactado pode e ainda deve ser lido:
Como você pode ver, dos 633 + 36 == 669 megabytes originais de dados no disco rígido, chegamos ao mais agradável 551. Essa diferença radical é explicada pela diminuição dos valores dos coeficientes, o que afeta seus compactação sem perdas subsequente: reduzir um por apenas um pode facilmente “cortar alguns bytes do arquivo final. No entanto, esta ainda é uma perda de dados, embora extremamente pequena, que você terá que suportar.
Felizmente, eles são absolutamente invisíveis aos olhos. Sob o spoiler (já que o habrastorage não suporta arquivos grandes), o leitor pode avaliar a diferença tanto a olho nu quanto sua intensidade, obtida subtraindo os valores do componente alterado do original: , , (quanto mais opaca for a cor, menor será a diferença no bloco).
Em vez de uma conclusão
Considerando todas essas dificuldades, comprar um disco rígido ou enviar tudo para a nuvem pode parecer uma solução muito mais simples para o problema. Mas mesmo que vivamos numa época tão maravilhosa agora, não há garantias de que amanhã ainda será possível ficar online e carregar todos os seus dados extras em algum lugar. Ou vá até a loja e compre outro disco rígido de mil terabytes. Mas você sempre pode usar as casas existentes.
->
Fonte: habr.com