Otro usuario quiere escribir un nuevo dato en el disco duro, pero no tiene suficiente espacio libre para hacerlo. Tampoco quiero borrar nada, ya que “todo es muy importante y necesario”. ¿Y qué debemos hacer con él?
Nadie tiene este problema. Hay terabytes de información en nuestros discos duros y esta cantidad no tiende a disminuir. ¿Pero qué tan único es? Al final, todos los archivos son sólo conjuntos de bits de cierta longitud y, muy probablemente, el nuevo no difiere mucho del que ya está almacenado.
Está claro que buscar información ya almacenada en un disco duro es, si no un fracaso, al menos no una tarea eficaz. En cambio, si la diferencia es pequeña, entonces puedes ajustarla un poco...
TL;DR: el segundo intento de hablar sobre un extraño método de optimización de datos utilizando archivos JPEG, ahora en una forma más comprensible.
Sobre bits y diferencias
Si se toman dos datos completamente aleatorios, en promedio la mitad de los bits que contienen coinciden. De hecho, entre los posibles diseños para cada par ('00, 01, 10, 11′), exactamente la mitad tienen los mismos valores, aquí todo es sencillo.
Pero claro, si simplemente tomamos dos archivos y ajustamos uno al segundo, perderemos uno de ellos. Si guardamos los cambios, simplemente nos reinventaremos , que existe perfectamente sin nosotros, aunque no suele utilizarse para los mismos fines. Podemos intentar incrustar una secuencia más pequeña en una más grande, pero aun así corremos el riesgo de perder segmentos críticos de datos si los usamos imprudentemente con todo.
¿Entre qué y qué entonces se puede eliminar la diferencia? Bueno, es decir, un archivo nuevo escrito por el usuario es solo una secuencia de bits, con la que por sí solo no podemos hacer nada. Luego sólo necesita encontrar en el disco duro los bits que puedan cambiarse sin tener que almacenar la diferencia, de modo que pueda sobrevivir a su pérdida sin consecuencias graves. Y tiene sentido cambiar no sólo el archivo en el propio FS, sino también cierta información menos confidencial que contiene. ¿Pero cuál y cómo?
Métodos de ajuste
Los archivos comprimidos con pérdida vienen al rescate. Todos estos archivos JPEG, MP3 y otros, aunque están comprimidos con pérdida, contienen un montón de bits que se pueden cambiar de forma segura. Es posible utilizar técnicas avanzadas que modifican imperceptiblemente sus componentes en varias etapas de codificación. Esperar. Técnicas avanzadas... modificación imperceptible... un poco dentro de otro... es casi como !
De hecho, integrar una información en otra recuerda sus métodos como ninguna otra cosa. También me impresiona la imperceptibilidad de los cambios realizados en los sentidos humanos. Donde los caminos divergen es en el secreto: nuestra tarea se reduce a que el usuario introduzca información adicional en su disco duro; esto sólo le perjudicará. Lo olvidará otra vez.
Por tanto, aunque podemos utilizarlos, es necesario realizar algunas modificaciones. Y luego les contaré y mostraré usando el ejemplo de uno de los métodos existentes y un formato de archivo común.
Acerca de los chacales
Si realmente lo aprietas, es la cosa más comprimible del mundo. Por supuesto, estamos hablando de archivos JPEG. No sólo existen toneladas de herramientas y métodos existentes para incorporar datos en ellos, sino que es el formato de gráficos más popular en este planeta.
Sin embargo, para no dedicarse a la cría de perros, es necesario limitar su campo de actividad en archivos de este formato. A nadie le gustan los cuadrados monocromáticos que aparecen por una compresión excesiva, por lo que debes limitarte a trabajar con un archivo ya comprimido. evitando la recodificación. Más concretamente, con los coeficientes enteros que quedan después de las operaciones responsables de la pérdida de datos: DCT y cuantificación, que se muestra perfectamente en el esquema de codificación (gracias a la wiki de la Biblioteca Nacional Bauman):
Existen muchos métodos posibles para optimizar archivos jpeg. Hay optimización sin pérdidas (jpegtran), hay optimización "“, que en realidad aportan algo más, pero no nos importan. Después de todo, si el usuario está dispuesto a incrustar una información en otra para aumentar el espacio libre en el disco, entonces o optimizó sus imágenes hace mucho tiempo o no quiere hacerlo en absoluto por temor a perder calidad.
F5
Toda una familia de algoritmos se ajusta a estas condiciones, con los que usted puede familiarizarse . El más avanzado de ellos es el algoritmo. de Andreas Westfeld, trabajando con los coeficientes del componente de brillo, ya que el ojo humano es el menos sensible a sus cambios. Además, utiliza una técnica de incrustación basada en codificación matricial, que permite realizar menos cambios al incrustar la misma cantidad de información cuanto mayor sea el tamaño del contenedor utilizado.
Los cambios en sí se reducen a reducir el valor absoluto de los coeficientes en uno bajo ciertas condiciones (es decir, no siempre), lo que le permite usar F5 para optimizar el almacenamiento de datos en su disco duro. El punto es que el coeficiente después de tal cambio probablemente ocupará menos bits después de la codificación de Huffman debido a la distribución estadística de valores en JPEG, y los nuevos ceros darán una ganancia al codificarlos usando RLE.
Las modificaciones necesarias se reducen a eliminar la parte responsable del secreto (reorganización de contraseñas), lo que ahorra recursos y tiempo de ejecución, y añadir un mecanismo para trabajar con muchos archivos en lugar de uno a la vez. Es poco probable que el lector esté interesado en el proceso de cambio con más detalle, así que pasemos a una descripción de la implementación.
Altas tecnologías
Para demostrar cómo funciona este enfoque, implementé el método en C puro y realicé una serie de optimizaciones tanto en términos de velocidad de ejecución como de memoria (no puedes imaginar cuánto pesan estas imágenes sin compresión, incluso antes de DCT). Multiplataforma lograda mediante una combinación de bibliotecas. , и , por lo que les agradecemos. Todo esto se reúne mediante 'make', por lo que los usuarios de Windows desean instalar Cygwin por sí mismos para su evaluación o manejar Visual Studio y las bibliotecas por su cuenta.
La implementación está disponible en forma de biblioteca y utilidad de consola. Los interesados pueden obtener más información sobre el uso de este último en el archivo Léame del repositorio en Github, cuyo enlace adjuntaré al final del post.
Modo de empleo?
Con cuidado. Las imágenes utilizadas para el empaquetado se seleccionan mediante una búsqueda mediante una expresión regular en el directorio raíz determinado. Al finalizar, los archivos se pueden mover, cambiar de nombre y copiar a voluntad dentro de sus límites, cambiar archivos y sistemas operativos, etc. Sin embargo, debe tener mucho cuidado y no cambiar el contenido inmediato de ninguna manera. Perder el valor de incluso un bit puede hacer imposible recuperar información.
Al finalizar, la utilidad deja un archivo especial que contiene toda la información necesaria para descomprimir, incluidos datos sobre las imágenes utilizadas. Por sí solo pesa alrededor de un par de kilobytes y no tiene ningún impacto significativo en el espacio ocupado en disco.
Puede analizar la posible capacidad utilizando el indicador '-a': './f5ar -a [carpeta de búsqueda] [expresión regular compatible con Perl]'. El empaquetado se realiza con el comando './f5ar -p [carpeta de búsqueda] [expresión regular compatible con Perl] [archivo empaquetado] [nombre del archivo comprimido]' y el descomprimido con './f5ar -u [archivo comprimido] [nombre del archivo recuperado ]'.
Demostración de trabajo
Para mostrar la efectividad del método, subí una colección de 225 fotografías de perros del servicio absolutamente gratuitas. y encontré en los documentos un gran pdf de 45 metros del segundo volumen Knuta.
La secuencia es bastante simple:
$ 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 fans
El archivo descomprimido aún puede y debe leerse:
Como puede ver, de los 633 + 36 == 669 megabytes de datos originales en el disco duro, llegamos a 551 más agradables. Una diferencia tan radical se explica por la disminución en los valores de los coeficientes, lo que afecta su posterior compresión sin pérdidas: reducir uno por uno puede “cortar fácilmente un par de bytes del archivo final”. Sin embargo, esto sigue siendo una pérdida de datos, aunque sea extremadamente pequeña, que tendrás que soportar.
Afortunadamente, son absolutamente invisibles a la vista. Debajo del spoiler (ya que habrastorage no puede manejar archivos grandes), el lector puede evaluar la diferencia tanto a simple vista como su intensidad, obtenida restando los valores del componente modificado del original: , , (cuanto más apagado sea el color, menor será la diferencia en el bloque).
En lugar de una conclusión
Teniendo en cuenta todas estas dificultades, comprar un disco duro o subirlo todo a la nube puede parecer una solución mucho más sencilla al problema. Pero aunque ahora vivimos en una época tan maravillosa, no hay garantías de que mañana todavía sea posible conectarse y cargar todos sus datos adicionales en algún lugar. O ve a la tienda y cómprate otro disco duro de mil terabytes. Pero siempre puedes utilizar casas existentes.
->
Fuente: habr.com