Ένας άλλος χρήστης θέλει να γράψει ένα νέο κομμάτι δεδομένων στον σκληρό δίσκο, αλλά δεν έχει αρκετό ελεύθερο χώρο για να το κάνει. Επίσης, δεν θέλω να διαγράψω τίποτα, καθώς «όλα είναι πολύ σημαντικά και απαραίτητα». Και τι να το κάνουμε;
Κανείς δεν έχει αυτό το πρόβλημα. Υπάρχουν terabyte πληροφοριών στους σκληρούς μας δίσκους και αυτή η ποσότητα δεν τείνει να μειώνεται. Πόσο μοναδικό όμως είναι; Τελικά, όλα τα αρχεία είναι απλώς σύνολα bit συγκεκριμένου μήκους και, πιθανότατα, το νέο δεν διαφέρει πολύ από αυτό που είναι ήδη αποθηκευμένο.
Είναι σαφές ότι η αναζήτηση τμημάτων πληροφοριών που είναι ήδη αποθηκευμένες σε έναν σκληρό δίσκο είναι, αν όχι αποτυχία, τουλάχιστον όχι αποτελεσματική εργασία. Από την άλλη, αν η διαφορά είναι μικρή, τότε μπορείς να την προσαρμόσεις λίγο...
TL;DR - η δεύτερη προσπάθεια να μιλήσουμε για μια περίεργη μέθοδο βελτιστοποίησης δεδομένων χρησιμοποιώντας αρχεία JPEG, τώρα σε πιο κατανοητή μορφή.
Σχετικά με τα κομμάτια και τη διαφορά
Εάν πάρετε δύο εντελώς τυχαία κομμάτια δεδομένων, τότε κατά μέσο όρο τα μισά από τα bit που περιέχουν συμπίπτουν. Πράγματι, από τις πιθανές διατάξεις για κάθε ζευγάρι ('00, 01, 10, 11′), ακριβώς οι μισές έχουν τις ίδιες τιμές, όλα είναι απλά εδώ.
Αλλά φυσικά, αν πάρουμε μόνο δύο αρχεία και χωρέσουμε το ένα στο δεύτερο, τότε θα χάσουμε ένα από αυτά. Εάν αποθηκεύσουμε τις αλλαγές, απλώς θα επανεφεύρουμε , που υπάρχει τέλεια χωρίς εμάς, αν και συνήθως δεν χρησιμοποιείται για τους ίδιους σκοπούς. Μπορούμε να προσπαθήσουμε να ενσωματώσουμε μια μικρότερη ακολουθία σε μια μεγαλύτερη, αλλά ακόμα κι έτσι κινδυνεύουμε να χάσουμε κρίσιμα τμήματα δεδομένων εάν τη χρησιμοποιούμε αλόγιστα με τα πάντα.
Ανάμεσα σε τι και τι μπορεί να εξαλειφθεί η διαφορά; Λοιπόν, δηλαδή, ένα νέο αρχείο γραμμένο από τον χρήστη είναι απλώς μια ακολουθία bit, με τα οποία δεν μπορούμε να κάνουμε τίποτα από μόνο του. Στη συνέχεια, πρέπει απλώς να βρείτε τέτοια κομμάτια στον σκληρό δίσκο που να μπορούν να αλλάξουν χωρίς να χρειάζεται να αποθηκεύσετε τη διαφορά, ώστε να μπορέσετε να επιβιώσετε από την απώλεια τους χωρίς σοβαρές συνέπειες. Και είναι λογικό να αλλάξετε όχι μόνο το αρχείο στο ίδιο το FS, αλλά κάποιες λιγότερο ευαίσθητες πληροφορίες μέσα σε αυτό. Ποιο όμως και πώς;
Μέθοδοι τοποθέτησης
Απώλεια συμπιεσμένα αρχεία έρχονται στη διάσωση. Όλα αυτά τα jpeg, mp3 και άλλα, αν και συμπίεση με απώλειες, περιέχουν ένα σωρό bit που μπορούν να αλλάξουν με ασφάλεια. Είναι δυνατή η χρήση προηγμένων τεχνικών που τροποποιούν ανεπαίσθητα τα στοιχεία τους σε διάφορα στάδια κωδικοποίησης. Περίμενε. Προηγμένες τεχνικές... ανεπαίσθητη τροποποίηση... το ένα κομμάτι στο άλλο... είναι σχεδόν σαν !
Πράγματι, η ενσωμάτωση μιας πληροφορίας σε μια άλλη θυμίζει τις μεθόδους της όσο τίποτα άλλο. Μου κάνει επίσης εντύπωση το ανεπαίσθητο των αλλαγών που γίνονται στις ανθρώπινες αισθήσεις. Όπου οι διαδρομές αποκλίνουν είναι το απόρρητο: το καθήκον μας έγκειται στο να εισάγει ο χρήστης πρόσθετες πληροφορίες στον σκληρό του δίσκο· αυτό μόνο θα τον βλάψει. Θα ξεχάσει ξανά.
Επομένως, αν και μπορούμε να τα χρησιμοποιήσουμε, πρέπει να κάνουμε κάποιες τροποποιήσεις. Και μετά θα τους πω και θα τους δείξω χρησιμοποιώντας το παράδειγμα μιας από τις υπάρχουσες μεθόδους και μια κοινή μορφή αρχείου.
Σχετικά με τα τσακάλια
Αν το πιέσετε πραγματικά, είναι το πιο συμπιεστό πράγμα στον κόσμο. Μιλάμε φυσικά για αρχεία JPEG. Όχι μόνο υπάρχουν πολλά εργαλεία και υπάρχουσες μέθοδοι για την ενσωμάτωση δεδομένων σε αυτό, αλλά είναι η πιο δημοφιλής μορφή γραφικών σε αυτόν τον πλανήτη.
Ωστόσο, για να μην ασχοληθείτε με την εκτροφή σκύλων, πρέπει να περιορίσετε το πεδίο δραστηριότητάς σας σε αρχεία αυτής της μορφής. Σε κανέναν δεν αρέσουν τα μονόχρωμα τετράγωνα που εμφανίζονται λόγω υπερβολικής συμπίεσης, επομένως πρέπει να περιοριστείτε στην εργασία με ένα ήδη συμπιεσμένο αρχείο, αποφεύγοντας την επανακωδικοποίηση. Πιο συγκεκριμένα, με ακέραιους συντελεστές, που παραμένουν μετά από λειτουργίες που είναι υπεύθυνες για απώλεια δεδομένων - DCT και κβαντοποίηση, που εμφανίζεται τέλεια στο σχήμα κωδικοποίησης (χάρη στο wiki της Εθνικής Βιβλιοθήκης Bauman):
Υπάρχουν πολλές πιθανές μέθοδοι για τη βελτιστοποίηση των αρχείων jpeg. Υπάρχει βελτιστοποίηση χωρίς απώλειες (jpegtran), υπάρχει βελτιστοποίηση "», που στην πραγματικότητα συνεισφέρουν κάτι άλλο, αλλά δεν μας ενδιαφέρει. Εξάλλου, εάν ο χρήστης είναι έτοιμος να ενσωματώσει μια πληροφορία σε μια άλλη για να αυξήσει τον ελεύθερο χώρο στο δίσκο, τότε είτε βελτιστοποίησε τις εικόνες του εδώ και πολύ καιρό είτε δεν θέλει να το κάνει καθόλου από φόβο απώλειας ποιότητας.
F5
Μια ολόκληρη οικογένεια αλγορίθμων ταιριάζει σε αυτές τις συνθήκες, με τις οποίες μπορείτε να εξοικειωθείτε . Το πιο προηγμένο από αυτά είναι ο αλγόριθμος από τον Andreas Westfeld, δουλεύοντας με τους συντελεστές της συνιστώσας φωτεινότητας, αφού το ανθρώπινο μάτι είναι το λιγότερο ευαίσθητο στις αλλαγές του. Επιπλέον, χρησιμοποιεί μια τεχνική ενσωμάτωσης που βασίζεται στην κωδικοποίηση matrix, η οποία καθιστά δυνατή την πραγματοποίηση λιγότερων αλλαγών κατά την ενσωμάτωση του ίδιου όγκου πληροφοριών, όσο μεγαλύτερο είναι το μέγεθος του δοχείου που χρησιμοποιείται.
Οι ίδιες οι αλλαγές καταλήγουν στη μείωση της απόλυτης τιμής των συντελεστών κατά ένα υπό ορισμένες συνθήκες (δηλαδή, όχι πάντα), κάτι που σας επιτρέπει να χρησιμοποιήσετε το F5 για να βελτιστοποιήσετε την αποθήκευση δεδομένων στον σκληρό σας δίσκο. Το θέμα είναι ότι ο συντελεστής μετά από μια τέτοια αλλαγή πιθανότατα θα καταλαμβάνει λιγότερα bit μετά την κωδικοποίηση Huffman λόγω της στατιστικής κατανομής των τιμών σε JPEG και τα νέα μηδενικά θα δώσουν κέρδος κατά την κωδικοποίησή τους χρησιμοποιώντας RLE.
Οι απαραίτητες τροποποιήσεις συνοψίζονται στην εξάλειψη του τμήματος που είναι υπεύθυνο για το απόρρητο (αναδιάταξη κωδικού πρόσβασης), το οποίο εξοικονομεί πόρους και χρόνο εκτέλεσης και προσθέτει έναν μηχανισμό για εργασία με πολλά αρχεία αντί για ένα κάθε φορά. Ο αναγνώστης είναι απίθανο να ενδιαφέρεται για τη διαδικασία αλλαγής με περισσότερες λεπτομέρειες, οπότε ας προχωρήσουμε σε μια περιγραφή της υλοποίησης.
Υψηλής τεχνολογίας
Για να δείξω πώς λειτουργεί αυτή η προσέγγιση, εφάρμοσα τη μέθοδο σε καθαρό C και πραγματοποίησα μια σειρά βελτιστοποιήσεων τόσο όσον αφορά την ταχύτητα εκτέλεσης όσο και τη μνήμη (δεν μπορείτε να φανταστείτε πόσο ζυγίζουν αυτές οι εικόνες χωρίς συμπίεση, ακόμη και πριν από το DCT). Cross-platform επιτυγχάνεται με χρήση συνδυασμού βιβλιοθηκών , и , για το οποίο τους ευχαριστούμε. Όλα αυτά συνδυάζονται από το «make», επομένως οι χρήστες των Windows θέλουν να εγκαταστήσουν κάποιο Cygwin για τον εαυτό τους για αξιολόγηση ή να ασχοληθούν μόνοι τους με το Visual Studio και τις βιβλιοθήκες.
Η υλοποίηση είναι διαθέσιμη με τη μορφή βοηθητικού προγράμματος κονσόλας και βιβλιοθήκης. Οι ενδιαφερόμενοι μπορούν να μάθουν περισσότερα για τη χρήση του τελευταίου στο readme στο αποθετήριο στο Github, τον σύνδεσμο στον οποίο θα επισυνάψω στο τέλος της ανάρτησης.
Πώς να χρησιμοποιήσετε;
Προσεκτικά. Οι εικόνες που χρησιμοποιούνται για τη συσκευασία επιλέγονται με αναζήτηση χρησιμοποιώντας μια τυπική έκφραση στον δεδομένο ριζικό κατάλογο. Μετά την ολοκλήρωση, τα αρχεία μπορούν να μετακινηθούν, να μετονομαστούν και να αντιγραφούν κατά βούληση εντός των ορίων τους, να αλλάξουν αρχεία και λειτουργικά συστήματα κ.λπ. Ωστόσο, θα πρέπει να είστε εξαιρετικά προσεκτικοί και να μην αλλάξετε με κανέναν τρόπο το άμεσο περιεχόμενο. Η απώλεια της αξίας έστω και ενός bit μπορεί να καταστήσει αδύνατη την ανάκτηση πληροφοριών.
Μετά την ολοκλήρωση, το βοηθητικό πρόγραμμα αφήνει ένα ειδικό αρχείο αρχειοθέτησης που περιέχει όλες τις απαραίτητες πληροφορίες για την αποσυσκευασία, συμπεριλαμβανομένων των δεδομένων σχετικά με τις εικόνες που χρησιμοποιούνται. Από μόνο του, ζυγίζει περίπου μερικά kilobyte και δεν έχει καμία σημαντική επίδραση στον κατειλημμένο χώρο στο δίσκο.
Μπορείτε να αναλύσετε την πιθανή χωρητικότητα χρησιμοποιώντας τη σημαία '-a': './f5ar -a [φάκελος αναζήτησης] [Τακτική έκφραση συμβατή με Perl]'. Η συσκευασία πραγματοποιείται με την εντολή './f5ar -p [φάκελος αναζήτησης] [Τακτική έκφραση συμβατή με Perl] [συσκευασμένο αρχείο] [όνομα αρχείου]' και η αποσυσκευασία με το './f5ar -u [αρχείο αρχείου] [όνομα ανακτημένου αρχείου ]'.
Επίδειξη εργασίας
Για να δείξω την αποτελεσματικότητα της μεθόδου, ανέβασα μια συλλογή από 225 εντελώς δωρεάν φωτογραφίες σκύλων από την υπηρεσία και βρέθηκε στα έγγραφα ένα μεγάλο pdf 45 μέτρων του δεύτερου τόμου Κνούτα.
Η σειρά είναι αρκετά απλή:
$ 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/Στιγμιότυπα οθόνης για θαυμαστές
Το αποσυσκευασμένο αρχείο μπορεί και πρέπει να διαβαστεί:
Όπως μπορείτε να δείτε, από τα αρχικά 633 + 36 == 669 megabyte δεδομένων στον σκληρό δίσκο, καταλήξαμε σε πιο ευχάριστα 551. Μια τέτοια ριζική διαφορά εξηγείται από τη μείωση των τιμών των συντελεστών, η οποία επηρεάζει τους επακόλουθη συμπίεση χωρίς απώλειες: η μείωση ενός προς ένα μπορεί εύκολα να «κόψει μερικά byte από το τελικό αρχείο. Ωστόσο, πρόκειται για απώλεια δεδομένων, αν και εξαιρετικά μικρή, την οποία θα πρέπει να υπομείνετε.
Ευτυχώς, είναι απολύτως αόρατα στο μάτι. Κάτω από το spoiler (καθώς το habrastorage δεν μπορεί να χειριστεί μεγάλα αρχεία), ο αναγνώστης μπορεί να αξιολογήσει τη διαφορά τόσο με το μάτι όσο και με την έντασή τους, που προκύπτει αφαιρώντας τις τιμές του αλλαγμένου στοιχείου από το πρωτότυπο: , , (όσο πιο θαμπό είναι το χρώμα, τόσο μικρότερη είναι η διαφορά στο μπλοκ).
Αντί για ένα συμπέρασμα
Λαμβάνοντας υπόψη όλες αυτές τις δυσκολίες, η αγορά ενός σκληρού δίσκου ή η αποστολή των πάντων στο cloud μπορεί να φαίνεται σαν μια πολύ πιο απλή λύση στο πρόβλημα. Όμως, παρόλο που ζούμε σε μια τόσο υπέροχη εποχή τώρα, δεν υπάρχει καμία εγγύηση ότι αύριο θα μπορείτε ακόμα να συνδεθείτε στο διαδίκτυο και να ανεβάσετε κάπου όλα τα επιπλέον δεδομένα σας. Ή πηγαίνετε στο κατάστημα και αγοράστε άλλο σκληρό δίσκο χιλιάδων terabyte. Αλλά μπορείτε πάντα να χρησιμοποιήσετε τα υπάρχοντα σπίτια.
->
Πηγή: www.habr.com