Outro usuario quere escribir unha nova peza de datos no disco duro, pero non ten espazo libre suficiente para facelo. Tampouco quero eliminar nada, xa que "todo é moi importante e necesario". E que debemos facer con el?
Ninguén ten este problema. Hai terabytes de información nos nosos discos duros, e esta cantidade non tende a diminuír. Pero o único que é? Ao final, todos os ficheiros son só conxuntos de bits de certa lonxitude e, moi probablemente, o novo non é moi diferente do que xa está almacenado.
Está claro que buscar pezas de información xa almacenadas nun disco duro é, se non un fallo, polo menos non é unha tarefa eficaz. Por outra banda, se a diferenza é pequena, podes axustala un pouco...
TL;DR - o segundo intento de falar dun método estraño para optimizar datos usando ficheiros JPEG, agora nunha forma máis comprensible.
Sobre anacos e diferenzas
Se tomas dous datos completamente aleatorios, de media a metade dos bits que conteñen coinciden. De feito, entre os deseños posibles para cada par ('00, 01, 10, 11′), exactamente a metade teñen os mesmos valores, aquí todo é sinxelo.
Pero claro, se só tomamos dous ficheiros e encaixamos un ao segundo, perderemos un deles. Se gardamos os cambios, simplemente reinventarémonos , que existe perfectamente sen nós, aínda que non se adoita empregar para os mesmos fins. Podemos tentar incrustar unha secuencia máis pequena nunha máis grande, pero aínda así corremos o risco de perder segmentos críticos de datos se o utilizamos de forma imprudente con todo.
Entre que e que entón se pode eliminar a diferenza? Ben, é dicir, un novo ficheiro escrito polo usuario é só unha secuencia de bits, co que non podemos facer nada por si só. Entón só precisa atopar no disco duro tales bits que se poden cambiar sen ter que almacenar a diferenza, para que poida sobrevivir á súa perda sen consecuencias graves. E ten sentido cambiar non só o ficheiro do propio FS, senón tamén algunha información menos sensible no seu interior. Pero cal e como?
Métodos de axuste
Os ficheiros comprimidos con perdas veñen ao rescate. Todos estes jpegs, mp3 e outros, aínda que compresión con perdas, conteñen unha morea de bits que se poden cambiar con seguridade. É posible utilizar técnicas avanzadas que modifican imperceptiblemente os seus compoñentes en varias fases da codificación. Agarda. Técnicas avanzadas... modificación imperceptible... un pouco noutro... é case como !
De feito, incorporar unha información noutra lembra os seus métodos como nada máis. Tamén me impresiona a imperceptibilidade dos cambios realizados nos sentidos humanos. Onde os camiños diverxen é no segredo: a nosa tarefa consiste en que o usuario introduza información adicional no seu disco duro; só lle fará dano. Esquecerá de novo.
Polo tanto, aínda que podemos utilizalos, necesitamos facer algunhas modificacións. E entón contarei e mostrarinos usando o exemplo dun dos métodos existentes e un formato de ficheiro común.
Sobre os chacales
Se realmente o apertas, é a cousa máis comprimible do mundo. Estamos, por suposto, a falar de ficheiros JPEG. Non só hai toneladas de ferramentas e métodos existentes para incorporar datos nel, senón que é o formato gráfico máis popular deste planeta.
Non obstante, para non dedicarse á cría de cans, cómpre limitar o seu campo de actividade en ficheiros deste formato. A ninguén lle gustan os cadrados monocromos que aparecen debido a unha compresión excesiva, polo que tes que limitarte a traballar cun ficheiro xa comprimido. evitando a recodificación. Máis concretamente, con coeficientes enteiros, que permanecen despois das operacións responsables da perda de datos - DCT e cuantización, que se mostra perfectamente no esquema de codificación (grazas á wiki da Biblioteca Nacional Bauman):
Hai moitos métodos posibles para optimizar ficheiros jpeg. Hai optimización sen perdas (jpegtran), hai optimización "“, que en realidade aportan outra cousa, pero non nos importan. Despois de todo, se o usuario está preparado para incorporar unha información noutra para aumentar o espazo libre no disco, ou optimizou as súas imaxes hai moito tempo ou non quere facelo en absoluto por medo á perda de calidade.
F5
Toda unha familia de algoritmos encaixa nestas condicións, coas que podes familiarizarte . O máis avanzado deles é o algoritmo de Andreas Westfeld, traballando cos coeficientes da compoñente de brillo, xa que o ollo humano é o menos sensible aos seus cambios. Ademais, utiliza unha técnica de incrustación baseada na codificación matricial, que permite realizar menos cambios ao incorporar a mesma cantidade de información, canto maior sexa o tamaño do contedor empregado.
Os propios cambios redúcense a reducir o valor absoluto dos coeficientes nun un baixo determinadas condicións (é dicir, non sempre), o que che permite usar F5 para optimizar o almacenamento de datos no teu disco duro. A cuestión é que o coeficiente despois de tal cambio probablemente ocupe menos bits despois da codificación de Huffman debido á distribución estatística de valores en JPEG, e os novos ceros darán unha ganancia ao codificalos usando RLE.
As modificacións necesarias redúcense en eliminar a parte responsable do segredo (reordenación do contrasinal), que permite aforrar recursos e tempo de execución, e engadir un mecanismo para traballar con moitos ficheiros en lugar de un a un. É improbable que o lector estea interesado no proceso de cambio con máis detalle, así que pasemos a unha descrición da implementación.
Alta tecnoloxía
Para demostrar como funciona este enfoque, implementei o método en C puro e realicei unha serie de optimizacións tanto en termos de velocidade de execución como de memoria (non podes imaxinar o que pesan estas imaxes sen compresión, mesmo antes do DCT). Multiplataforma conseguida mediante unha combinación de bibliotecas , и , polo que lles agradecemos. Todo isto está reunido por 'make', polo que os usuarios de Windows queren instalar algún Cygwin por si mesmos para a súa avaliación ou xestionar Visual Studio e as bibliotecas por si mesmos.
A implementación está dispoñible en forma de utilidade de consola e biblioteca. Os interesados poden saber máis sobre o uso deste último no readme do repositorio de Github, a ligazón á que adxuntarei ao final da publicación.
Como usar?
Con coidado. As imaxes utilizadas para empaquetar son seleccionadas mediante a busca mediante unha expresión regular no directorio raíz indicado. Ao rematar, os ficheiros pódense mover, renomear e copiar a vontade dentro dos seus límites, cambiar ficheiros e sistemas operativos, etc. Non obstante, debes ter moito coidado e non cambiar o contido inmediato de ningún xeito. Perder o valor dun bit pode facer imposible recuperar a información.
Ao finalizar, a utilidade deixa un ficheiro de arquivo especial que contén toda a información necesaria para desempaquetar, incluíndo datos sobre as imaxes utilizadas. Por si só, pesa un par de kilobytes e non ten ningún impacto significativo no espazo de disco ocupado.
Podes analizar a posible capacidade usando a marca '-a': './f5ar -a [cartafol de busca] [Expresión regular compatible con Perl]'. O empaquetado realízase co comando './f5ar -p [cartafol de busca] [expresión regular compatible con Perl] [ficheiro empaquetado] [nome do arquivo]', e descomprimilo con './f5ar -u [ficheiro do arquivo] [nome do ficheiro recuperado ]' .
Demostración de traballo
Para mostrar a eficacia do método, carguei unha colección de 225 fotos absolutamente gratuítas de cans do servizo e atopou nos documentos un gran pdf de 45 metros do segundo volume Knuta.
A secuencia é bastante sinxela:
$ 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 pantalla para os fans
O ficheiro desempaquetado pode e aínda debe lerse:
Como podes ver, a partir dos orixinais 633 + 36 == 669 megabytes de datos no disco duro, chegamos a 551 máis agradables. Unha diferenza tan radical explícase pola diminución dos valores dos coeficientes, o que afecta aos seus posterior compresión sen perdas: reducindo un a un pode facilmente "cortar un par de bytes do ficheiro final. Non obstante, esta aínda é unha perda de datos, aínda que moi pequena, que terás que soportar.
Afortunadamente, son absolutamente invisibles para os ollos. Baixo o spoiler (xa que habrastorage non pode xestionar ficheiros grandes), o lector pode avaliar a diferenza tanto a vista como a súa intensidade, obtida restando os valores do compoñente modificado do orixinal: , , (canto máis apagada sexa a cor, menor será a diferenza no bloque).
En vez de unha conclusión
Tendo en conta todas estas dificultades, comprar un disco duro ou cargar todo á nube pode parecer unha solución moito máis sinxela ao problema. Pero aínda que agora vivimos nunha época tan marabillosa, non hai garantías de que mañá aínda sexa posible conectarse e cargar todos os seus datos adicionais nalgún lugar. Ou vai á tenda e cómpre outro disco duro de mil terabytes. Pero sempre podes usar as casas existentes.
->
Fonte: www.habr.com