Un altro utente vuole scrivere nuovi dati sul disco rigido, ma non ha abbastanza spazio libero per farlo. Inoltre non voglio cancellare nulla, poiché “tutto è molto importante e necessario”. E cosa dovremmo farne?
Nessuno ha questo problema. Ci sono terabyte di informazioni sui nostri dischi rigidi e questa quantità non tende a diminuire. Ma quanto è unico? Alla fine, tutti i file sono solo insiemi di bit di una certa lunghezza e, molto probabilmente, quello nuovo non è molto diverso da quello già memorizzato.
È chiaro che la ricerca di informazioni già archiviate su un disco rigido è, se non un fallimento, almeno non un compito efficace. D'altra parte, se la differenza è piccola, puoi regolarla un po'...
TL;DR - il secondo tentativo di parlare di uno strano metodo di ottimizzazione dei dati utilizzando file JPEG, ora in una forma più comprensibile.
A proposito di bit e differenze
Se prendi due dati completamente casuali, in media la metà dei bit che contengono coincidono. Infatti, tra i possibili layout per ogni coppia ('00, 01, 10, 11′), esattamente la metà ha gli stessi valori, qui tutto è semplice.
Ma ovviamente, se prendiamo solo due file e ne adattiamo uno al secondo, ne perderemo uno. Se salviamo le modifiche, semplicemente reinventeremo , che esiste perfettamente senza di noi, anche se di solito non viene utilizzato per gli stessi scopi. Possiamo provare a incorporare una sequenza più piccola in una sequenza più grande, ma anche così rischiamo di perdere segmenti critici di dati se li usiamo incautamente con tutto.
Tra cosa e cosa allora si può eliminare la differenza? Bene, cioè, un nuovo file scritto dall'utente è solo una sequenza di bit, con la quale da sola non possiamo fare nulla. Quindi devi solo trovare sul disco rigido tali bit che possano essere modificati senza dover memorizzare la differenza, in modo da poter sopravvivere alla loro perdita senza gravi conseguenze. Ed è logico modificare non solo il file sull'FS stesso, ma anche alcune informazioni meno sensibili al suo interno. Ma quale e come?
Metodi di montaggio
I file compressi con perdita di dati vengono in soccorso. Tutti questi jpeg, mp3 e altri, nonostante la compressione con perdita, contengono un sacco di bit che possono essere modificati in sicurezza. È possibile utilizzare tecniche avanzate che ne modificano impercettibilmente le componenti nei vari stadi della codifica. Aspettare. Tecniche avanzate... modifiche impercettibili... un pezzo nell'altro... è quasi come !
In effetti, incorporare un’informazione nell’altra ricorda i suoi metodi come nient’altro. Sono impressionato anche dall'impercettibilità dei cambiamenti apportati ai sensi umani. Dove le strade divergono avviene nel segreto: il nostro compito spetta all'utente che inserisce informazioni aggiuntive sul suo disco rigido; questo gli farà solo del male. Lo dimenticherà di nuovo.
Pertanto, sebbene possiamo usarli, dobbiamo apportare alcune modifiche. E poi li dirò e mostrerò usando l'esempio di uno dei metodi esistenti e un formato di file comune.
A proposito di sciacalli
Se lo stringi davvero, è la cosa più comprimibile al mondo. Stiamo ovviamente parlando di file JPEG. Non solo esistono tantissimi strumenti e metodi esistenti per incorporare dati al suo interno, ma è il formato grafico più popolare su questo pianeta.
Tuttavia, per non dedicarsi all'allevamento di cani, è necessario limitare il proprio campo di attività a file di questo formato. A nessuno piacciono i quadrati monocromatici che appaiono a causa dell'eccessiva compressione, quindi è necessario limitarsi a lavorare con un file già compresso, evitando la ricodifica. Più specificamente, con i coefficienti interi, che rimangono dopo le operazioni responsabili della perdita di dati - DCT e quantizzazione, che è perfettamente visualizzato nello schema di codifica (grazie al wiki della Biblioteca Nazionale Bauman):
Esistono molti metodi possibili per ottimizzare i file jpeg. C'è l'ottimizzazione senza perdite (jpegtran), c'è l'ottimizzazione "“, che in realtà contribuiscono con qualcos’altro, ma a noi non interessano. Dopotutto, se l'utente è pronto a incorporare un'informazione in un'altra per aumentare lo spazio libero su disco, ha ottimizzato le sue immagini molto tempo fa o non vuole farlo affatto per paura di perdere qualità.
F5
Un'intera famiglia di algoritmi si adatta a queste condizioni, con le quali puoi familiarizzare . Il più avanzato di questi è l'algoritmo di Andreas Westfeld, lavorando con i coefficienti della componente luminosità, poiché l'occhio umano è il meno sensibile ai suoi cambiamenti. Inoltre, utilizza una tecnica di incorporamento basata sulla codifica a matrice, che consente di apportare meno modifiche quando si incorpora la stessa quantità di informazioni, maggiore è la dimensione del contenitore utilizzato.
Le modifiche stesse si riducono alla riduzione del valore assoluto dei coefficienti di uno in determinate condizioni (cioè non sempre), che consente di utilizzare F5 per ottimizzare l'archiviazione dei dati sul disco rigido. Il punto è che il coefficiente dopo tale modifica molto probabilmente occuperà meno bit dopo la codifica di Huffman a causa della distribuzione statistica dei valori in JPEG, e i nuovi zeri daranno un guadagno quando li codificherai utilizzando RLE.
Le modifiche necessarie si riducono all'eliminazione della parte responsabile della segretezza (riorganizzazione delle password), che consente di risparmiare risorse e tempo di esecuzione, e all'aggiunta di un meccanismo per lavorare con molti file invece che uno alla volta. È improbabile che il lettore sia interessato al processo di modifica in modo più dettagliato, quindi passiamo alla descrizione dell'implementazione.
Alta tecnologia
Per dimostrare come funziona questo approccio, ho implementato il metodo in C puro e effettuato una serie di ottimizzazioni sia in termini di velocità di esecuzione che di memoria (non potete immaginare quanto pesino queste immagini senza compressione, anche prima del DCT). Multipiattaforma ottenuta utilizzando una combinazione di librerie , и , per il quale li ringraziamo. Tutto questo è messo insieme da 'make', quindi gli utenti Windows vogliono installare qualche Cygwin per la valutazione, o gestire Visual Studio e le librerie per conto proprio.
L'implementazione è disponibile sotto forma di utility console e libreria. Chi fosse interessato può scoprire di più sull'utilizzo di quest'ultimo nel readme presente nella repository su Github, il link a cui allegherò alla fine del post.
Come usare?
Accuratamente. Le immagini utilizzate per il packaging vengono selezionate effettuando una ricerca utilizzando un'espressione regolare nella directory root specificata. Al termine, i file possono essere spostati, rinominati e copiati a piacimento entro i suoi limiti, modificare file e sistemi operativi, ecc. Tuttavia, dovresti stare estremamente attento e non modificare in alcun modo il contenuto immediato. La perdita del valore anche di un bit può rendere impossibile il recupero delle informazioni.
Al termine, l'utilità lascia uno speciale file di archivio contenente tutte le informazioni necessarie per il disimballaggio, compresi i dati sulle immagini utilizzate. Di per sé pesa circa un paio di kilobyte e non ha alcun impatto significativo sullo spazio occupato su disco.
Puoi analizzare la capacità possibile utilizzando il flag '-a': './f5ar -a [cartella di ricerca] [espressione regolare compatibile con Perl]'. Il confezionamento viene eseguito con il comando './f5ar -p [cartella di ricerca] [espressione regolare compatibile con Perl] [file compresso] [nome archivio]' e il decompressione con './f5ar -u [file archivio] [nome file recuperato ]' .
Dimostrazione di lavoro
Per dimostrare l'efficacia del metodo, ho caricato una raccolta di 225 foto di cani assolutamente gratuite dal servizio e trovato tra i documenti un grande pdf di 45 metri del secondo volume Knuta.
La sequenza è abbastanza semplice:
$ 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/Screenshot per i fan
Il file decompresso può e deve essere comunque letto:
Come puoi vedere, dagli originali 633 + 36 == 669 megabyte di dati sul disco rigido siamo arrivati ai più piacevoli 551. Una differenza così radicale è spiegata dalla diminuzione dei valori dei coefficienti, che ne influenza successiva compressione senza perdita di dati: riducendone uno solo si può facilmente “tagliare un paio di byte dal file finale. Si tratta comunque di una perdita di dati, anche se estremamente ridotta, che dovrai sopportare.
Fortunatamente sono assolutamente invisibili agli occhi. Sotto lo spoiler (poiché habrastorage non può gestire file di grandi dimensioni), il lettore può valutare la differenza sia a occhio che la loro intensità, ottenuta sottraendo i valori della componente modificata dall'originale: , , (più opaco è il colore, minore è la differenza nel blocco).
Invece di una conclusione
Considerando tutte queste difficoltà, acquistare un disco rigido o caricare tutto sul cloud può sembrare una soluzione molto più semplice al problema. Ma anche se viviamo in un periodo così meraviglioso, non ci sono garanzie che domani sarà ancora possibile andare online e caricare tutti i propri dati extra da qualche parte. Oppure vai al negozio e comprati un altro disco rigido da mille terabyte. Ma puoi sempre utilizzare le case esistenti.
->
Fonte: habr.com