Un autre utilisateur souhaite écrire une nouvelle donnée sur le disque dur, mais il ne dispose pas de suffisamment d'espace libre pour ce faire. Je ne veux rien supprimer non plus, car « tout est très important et nécessaire ». Et que devrions-nous en faire ?
Personne n'a ce problème. Il y a des téraoctets d'informations sur nos disques durs, et cette quantité n'a pas tendance à diminuer. Mais à quel point est-il unique ? En fin de compte, tous les fichiers ne sont que des ensembles de bits d'une certaine longueur et, très probablement, le nouveau n'est pas très différent de celui déjà stocké.
Il est clair que la recherche d’informations déjà stockées sur un disque dur est, sinon un échec, du moins une tâche peu efficace. En revanche, si la différence est faible, alors vous pouvez l'ajuster un peu...
TL;DR - la deuxième tentative pour parler d'une étrange méthode d'optimisation des données à l'aide de fichiers JPEG, maintenant sous une forme plus compréhensible.
À propos des bits et de la différence
Si vous prenez deux données complètement aléatoires, alors en moyenne la moitié des bits qu'elles contiennent coïncident. En effet, parmi les dispositions possibles pour chaque paire ('00, 01, 10, 11′), exactement la moitié ont les mêmes valeurs, tout est simple ici.
Mais bien sûr, si nous prenons simplement deux fichiers et en adaptons un au second, nous en perdrons un. Si nous enregistrons les modifications, nous réinventerons simplement , qui existe parfaitement sans nous, même s’il n’est généralement pas utilisé aux mêmes fins. Nous pouvons essayer d’intégrer une séquence plus petite dans une séquence plus grande, mais nous risquons néanmoins de perdre des segments de données critiques si nous l’utilisons de manière imprudente avec tout.
Entre quoi et quoi alors la différence peut-elle être éliminée ? Eh bien, c'est-à-dire qu'un nouveau fichier écrit par l'utilisateur n'est qu'une séquence de bits avec laquelle nous ne pouvons rien faire par lui-même. Ensuite, il vous suffit de trouver sur le disque dur des éléments tels qu'ils puissent être modifiés sans avoir à stocker la différence, afin que vous puissiez survivre à leur perte sans conséquences graves. Et il est logique de modifier non seulement le fichier sur le FS lui-même, mais également certaines informations moins sensibles qu'il contient. Mais lequel et comment ?
Méthodes d'ajustement
Les fichiers compressés avec perte viennent à la rescousse. Tous ces jpeg, mp3 et autres, bien que compressés avec perte, contiennent un tas de bits qui peuvent être modifiés en toute sécurité. Il est possible d'utiliser des techniques avancées qui modifient imperceptiblement leurs composants à différentes étapes de l'encodage. Attendez. Techniques avancées... modification imperceptible... un morceau dans un autre... c'est presque comme !
En effet, intégrer une information dans une autre rappelle comme rien d’autre ses méthodes. Je suis également impressionné par l'imperceptibilité des changements apportés aux sens humains. Là où les chemins divergent, c'est dans le secret : notre tâche se résume à ce que l'utilisateur entre des informations supplémentaires sur son disque dur ; cela ne fera que lui nuire. Il oubliera encore.
Par conséquent, même si nous pouvons les utiliser, nous devons apporter quelques modifications. Et puis je vais les raconter et les montrer en utilisant l'exemple de l'une des méthodes existantes et d'un format de fichier commun.
À propos des chacals
Si vous le pressez vraiment, c’est la chose la plus compressible au monde. Nous parlons bien sûr de fichiers JPEG. Non seulement il existe des tonnes d’outils et de méthodes existantes pour y intégrer des données, mais il s’agit également du format graphique le plus populaire sur cette planète.
Cependant, afin de ne pas vous lancer dans l'élevage de chiens, vous devez limiter votre domaine d'activité aux fichiers de ce format. Personne n'aime les carrés monochromes qui apparaissent en raison d'une compression excessive, vous devez donc vous limiter à travailler avec un fichier déjà compressé, éviter le recodage. Plus précisément, avec des coefficients entiers, qui restent après les opérations responsables de la perte de données - DCT et quantification, qui s'affichent parfaitement dans le schéma de codage (grâce au wiki de la Bibliothèque nationale Bauman) :
Il existe de nombreuses méthodes possibles pour optimiser les fichiers JPEG. Il y a une optimisation sans perte (jpegtran), il y a une optimisation"», qui en fait apportent autre chose, mais nous ne nous en soucions pas. Après tout, si l'utilisateur est prêt à intégrer une information dans une autre afin d'augmenter l'espace disque libre, soit il a optimisé ses images il y a longtemps, soit il ne veut pas du tout le faire par crainte de perte de qualité.
F5
Toute une famille d'algorithmes répond à ces conditions, avec lesquelles vous pouvez vous familiariser . Le plus avancé d'entre eux est l'algorithme par Andreas Westfeld, travaillant avec les coefficients de la composante luminosité, puisque l'œil humain est le moins sensible à ses changements. De plus, il utilise une technique d'embarquement basée sur un codage matriciel, qui permet d'effectuer moins de modifications lors de l'embarquement de la même quantité d'informations, plus la taille du conteneur utilisé est grande.
Les modifications elles-mêmes se résument à réduire la valeur absolue des coefficients d'un sous certaines conditions (c'est-à-dire pas toujours), ce qui permet d'utiliser F5 pour optimiser le stockage des données sur votre disque dur. Le fait est que le coefficient après un tel changement occupera très probablement moins de bits après le codage de Huffman en raison de la distribution statistique des valeurs en JPEG, et les nouveaux zéros donneront un gain lors de leur codage à l'aide de RLE.
Les modifications nécessaires se résument à l'élimination de la partie responsable du secret (réarrangement des mots de passe), ce qui permet d'économiser des ressources et du temps d'exécution, et à l'ajout d'un mécanisme permettant de travailler avec plusieurs fichiers au lieu d'un à la fois. Il est peu probable que le lecteur soit intéressé par le processus de changement plus en détail, passons donc à une description de la mise en œuvre.
Hautes technologies
Pour démontrer le fonctionnement de cette approche, j'ai implémenté la méthode en C pur et effectué un certain nombre d'optimisations tant en termes de vitesse d'exécution que de mémoire (vous n'imaginez pas combien pèsent ces images sans compression, même avant DCT). Multiplateforme réalisé en utilisant une combinaison de bibliothèques , и , pour lequel nous les remercions. Tout cela est rassemblé par « make », de sorte que les utilisateurs de Windows souhaitent installer Cygwin pour eux-mêmes à des fins d'évaluation, ou gérer eux-mêmes Visual Studio et les bibliothèques.
L'implémentation est disponible sous la forme d'un utilitaire de console et d'une bibliothèque. Les personnes intéressées peuvent en savoir plus sur l'utilisation de ce dernier dans le fichier readme du référentiel sur Github, le lien auquel je joindrai à la fin de l'article.
Comment l'utiliser?
Soigneusement. Les images utilisées pour l'empaquetage sont sélectionnées en recherchant à l'aide d'une expression régulière dans le répertoire racine donné. Une fois terminés, les fichiers peuvent être déplacés, renommés et copiés à volonté dans leurs limites, modifier les fichiers et les systèmes d'exploitation, etc. Cependant, vous devez être extrêmement prudent et ne modifier en aucun cas le contenu immédiat. La perte de la valeur d'un seul bit peut rendre impossible la récupération des informations.
Une fois terminé, l'utilitaire laisse un fichier d'archive spécial contenant toutes les informations nécessaires au déballage, y compris les données sur les images utilisées. À lui seul, il pèse environ quelques kilo-octets et n'a pas d'impact significatif sur l'espace disque occupé.
Vous pouvez analyser la capacité possible en utilisant l'indicateur '-a' : './f5ar -a [dossier de recherche] [expression régulière compatible Perl]'. L'emballage se fait avec la commande './f5ar -p [dossier de recherche] [expression régulière compatible Perl] [fichier compressé] [nom de l'archive]', et le déballage avec './f5ar -u [fichier d'archive] [nom du fichier récupéré ]' .
Démonstration de travail
Pour montrer l'efficacité de la méthode, j'ai téléchargé une collection de 225 photos de chiens absolument gratuites du service et trouvé dans les documents un grand pdf de 45 mètres du deuxième volume Knuta.
La séquence est assez 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/Captures d'écran pour les fans
Le fichier décompressé peut et doit toujours être lu :
Comme vous pouvez le constater, à partir des 633 + 36 == 669 mégaoctets de données d'origine sur le disque dur, nous sommes arrivés à 551 plus agréables. Une différence aussi radicale s'explique par la diminution des valeurs des coefficients, qui affecte leur compression ultérieure sans perte : réduire un par un peut facilement « couper quelques octets du fichier final ». Cependant, il s’agit toujours d’une perte de données, même si elle est extrêmement minime, que vous devrez supporter.
Heureusement, ils sont absolument invisibles à l’œil nu. Sous le spoiler (puisque habrastorage ne peut pas gérer de gros fichiers), le lecteur peut évaluer la différence à la fois à l'œil nu et à leur intensité, obtenue en soustrayant les valeurs du composant modifié de l'original : , , (plus la couleur est terne, plus la différence dans le bloc est faible).
Au lieu d'une conclusion
Compte tenu de toutes ces difficultés, acheter un disque dur ou tout télécharger sur le cloud peut sembler une solution beaucoup plus simple au problème. Mais même si nous vivons actuellement une époque si merveilleuse, rien ne garantit que demain, il sera encore possible d'aller en ligne et de télécharger toutes vos données supplémentaires quelque part. Ou allez au magasin et achetez-vous un autre disque dur de mille téraoctets. Mais vous pouvez toujours utiliser des maisons existantes.
->
Source: habr.com