Un altro utente vuole scrivere un nuovo pezzo di dati sul disco rigido, ma non ha spazio libero a disposizione. Non vuole nemmeno eliminare nulla, poiché "tutto è molto importante e necessario". E cosa possiamo fare con lui?
Questo problema non riguarda solo lui. Sui nostri dischi rigidi giacciono terabyte di informazioni, e questa quantità non tende a diminuire. Ma quanto è unica? In fin dei conti, tutti i file non sono altro che insiemi di bit di una certa lunghezza e, probabilmente, un nuovo file non differisce molto da uno già conservato.
È evidente che cercare i pezzi di informazioni già memorizzati sul disco rigido è un compito che, se non fallimentare, è almeno poco efficace. D'altra parte, se la differenza è piccola, si può anche cercare di adattarla un po'...
TL;DR — un secondo tentativo di raccontare un metodo strano per ottimizzare i dati utilizzando file JPEG, ora in una forma più comprensibile.
Sui bit e sulle differenze
Se prendiamo due pezzi di dati completamente casuali, in media metà dei bit contenuti coincide. Infatti, tra le possibili combinazioni per ogni coppia (‘00, 01, 10, 11’), esattamente la metà ha valori coincidenti, qui è tutto semplice.
Ma naturalmente, se prendiamo semplicemente due file e adattiamo uno all'altro, perderemo uno dei due. Se invece ci occupiamo di salvare le modifiche, semplicemente ri-inventeremo , che esiste già senza di noi, anche se di solito non è utilizzata per scopi simili. Possiamo provare a inserire una sequenza più piccola in una più grande, ma anche in questo modo rischiamo di perdere segmenti critici di dati se usati imprudentemente con tutto ciò che ci capita a tiro.
Tra cosa e cosa possiamo quindi eliminare la differenza? Cioè, il nuovo file che l'utente vuole scrivere è semplicemente una sequenza di bit, con cui di per sé non possiamo fare nulla. Quindi dobbiamo semplicemente trovare sul disco rigido quei bit che possano essere modificati senza necessità di conservare la differenza, in modo da poter sopportare la loro perdita senza gravi conseguenze. E modificare non ha senso solo per il file stesso nel filesystem, ma anche per alcune informazioni meno sensibili al suo interno. Ma quali e come?
Metodi di adattamento
A supporto arrivano file compressi con perdita. Tutti questi jpeg, mp3 e altri, sebbene siano compressi con perdita, contengono una marea di bit disponibili per modifiche sicure. Si possono utilizzare tecniche avanzate che modificano discretamente i loro componenti in diverse aree di codifica. Aspetta. Tecniche avanzate... modifica invisibile... alcuni bit in altri... sì, è quasi !
E in effetti, incorporare un'informazione in un'altra ricorda i suoi metodi. Impressiona anche la discrezione delle modifiche effettuate per i sensi umani. Qui le strade si separano: il nostro obiettivo è inserire ulteriori informazioni sul disco rigido dell'utente, il che solo gli creerà problemi. Dimenticherà anche.
Quindi, anche se possiamo usarli, è necessario apportare alcune modifiche. E più avanti parlerò e mostrerò queste modifiche utilizzando uno dei metodi esistenti e un formato di file comune.
Sugli sciacalli
Se proprio bisogna comprimere, si deve scegliere il più comprimibile al mondo. Si parla, ovviamente, di file JPEG. Non solo esiste un sacco di strumenti e metodi esistenti per incorporare dati, ma è anche il formato grafico più popolare su questo pianeta.
Tuttavia, per non impazzire, è necessario limitare il proprio campo d'azione ai file di questo formato. Nessuno ama i quadratini monocolore che si formano a causa di una compressione eccessiva, quindi è necessario lavorare solo con file già compressi, evitando la ricodifica. Più precisamente, con coefficienti interi, che rimangono dopo le operazioni responsabili della perdita di dati - DCT e quantizzazione, come ben mostrato nello schema di codifica (grazie a Wiki della Biblioteca Nazionale Bauman):
Esistono molti metodi possibili per ottimizzare i file jpeg. C'è l'ottimizzazione senza perdita (jpegtran), c'è l'ottimizzazione "" che in realtà ne apportano alcune, ma a noi non interessano. Infatti, se l'utente è disposto a incorporare un'informazione in un'altra per aumentare lo spazio libero sul disco, significa che ha già ottimizzato le sue immagini a lungo, oppure non desidera farlo affatto per paura di perdere qualità.
F5
Sotto tali condizioni, si adatta un'intera famiglia di algoritmi, con cui è possibile familiarizzare . Il più avanzato di essi è l'algoritmo di Andreas Westfeld, che lavora con i coefficienti del componente luminosità, poiché l'occhio umano è meno sensibile proprio ai suoi cambiamenti. Inoltre, utilizza una metodologia di embedding basata sulla codifica della matrice, grazie alla quale è possibile effettuare meno cambiamenti durante l'embedding della stessa quantità di informazioni, più grande è la dimensione del contenitore utilizzato.
Le variazioni stesse si riducono all'abbassamento del valore assoluto dei coefficienti di un'unità in determinate condizioni (cioè, non sempre), il che consente di utilizzare F5 per ottimizzare lo storage dei dati su disco rigido. Infatti, il coefficiente dopo tale modificazione occupa probabilmente un numero minore di bit dopo la codifica Huffman a causa della distribuzione statistica dei valori in JPEG, e i nuovi zeri offriranno vantaggi nella loro codifica tramite RLE.
Le modifiche necessarie consistono nell'eliminazione della parte responsabile della segretezza (permutazione della password), che consente di risparmiare risorse e tempi di esecuzione, e nell'aggiunta di un meccanismo per gestire più file invece di uno alla volta. Maggiori dettagli sul processo di modifica potrebbero non interessare il lettore, quindi passiamo a descrivere l'implementazione.
Tecnologie avanzate
Per dimostrare il funzionamento di questo approccio ho implementato un metodo in puro C e ho svolto una serie di ottimizzazioni sia per la velocità di esecuzione che per la memoria (non potete immaginare quanto pesino queste immagini senza compressione anche dopo DCT). La portabilità è stata raggiunta utilizzando una combinazione di librerie , e , per cui li ringrazio. Tutto ciò viene assemblato con il comando ‘make’, quindi gli utenti Windows per valutare vogliono installare Cygwin, oppure cimentarsi con Visual Studio e le librerie da soli.
L'implementazione è disponibile sotto forma di utilità da console e libreria. Maggiori informazioni sull'uso della seconda possono essere consultate nel README nel repository su GitHub, il cui link fornirò alla fine del post.
Come usare?
Con cautela. Le immagini utilizzate per l'imballaggio vengono scelte tramite una ricerca con espressione regolare nella directory radice specificata. Al termine, i file possono essere spostati, rinominati e copiati a piacere all'interno di essa, modificarne i sistemi operativi e altro ancora. Tuttavia, è fondamentale essere estremamente attenti e non modificare il contenuto diretto. La perdita di valore anche di un solo bit può portare all'impossibilità di recuperare le informazioni.
Al termine del lavoro, l'utility lascia un file di archivio speciale contenente tutte le informazioni necessarie per l'estrazione, incluse le informazioni sulle immagini utilizzate. Il file stesso pesa circa un paio di kilobyte e non ha un impatto significativo sullo spazio disco occupato.
È possibile analizzare la potenziale capacità utilizzando il flag ‘-a’: ‘./f5ar -a [cartella di ricerca] [espressione regolare compatibile con Perl]’. L'imballaggio viene eseguito con il comando ‘./f5ar -p [cartella di ricerca] [espressione regolare compatibile con Perl] [file da imballare] [nome dell'archivio]’, mentre l'estrazione avviene con ‘./f5ar -u [file di archivio] [nome del file estratto]’.
Dimostrazione del funzionamento
Per dimostrare l'efficacia del metodo, ho caricato una collezione di 225 fotografie di cani completamente gratuite dal servizio e ho trovato un grande file pdf di 45 metri del secondo volume di Knuth.
La sequenza è piuttosto semplice:
$ du -sh knuth.pdf cani/
44M knuth.pdf
633M cani/
$ ./f5ar -p cani/ .*jpg knuth.pdf dogs.f5ar
Lettura file di compressione... ok
Inizializzazione dell'archivio... ok
Analisi della capacità della libreria... completata in 17.0s
Capacità garantita rilevata di 48439359 bytes
Capacità possibile rilevata fino a 102618787 bytes
Compressing... completato in 39.4s
Salvataggio dell'archivio... ok
$ ./f5ar -u cani/dogs.f5ar knuth_unpacked.pdf
Inizializzazione dell'archivio... ok
Lettura del file di archivio... ok
Riempimento dell'archivio con file... completato in 1.4s
Decompressione... completato in 21.0s
Scrittura dei dati estratti... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh cani/
551M cani/Screenshot per gli appassionati
Il file estratto può ancora essere letto e deve essere:
Come si può vedere, dai 633 + 36 == 669 megabyte di dati sul disco rigido siamo arrivati a un più piacevole 551. Questa radicale differenza è spiegata dalla stessa riduzione dei valori dei coefficienti, che influiscono sulla loro successiva compressione senza perdite: la diminuzione di uno solo può tranquillamente "cancellare" un paio di byte dal file finale. Tuttavia, si tratta comunque di perdite di dati, sebbene estremamente ridotte, con cui dovremo fare i conti.
Fortunatamente, per l'occhio non sono assolutamente visibili. Sotto spoiler (poiché habrastorage non gestisce file di grandi dimensioni) il lettore può valutare la differenza sia a colpo d'occhio sia la loro intensità, ottenuta sottraendo i valori della componente modificata dall'originale: , , (più il colore è tenue, minore è la differenza nel blocco).
In conclusione
Guardando tutte queste complessità, comprare un disco rigido o caricare tutto nel cloud può sembrare una soluzione molto più semplice al problema. Ma sebbene ora viviamo in un periodo così meraviglioso, non ci sono garanzie che domani potremo comunque andare su Internet e caricare da qualche parte tutti i nostri dati in eccesso. O entrare in un negozio e comprare un altro disco rigido da mille terabyte. Tuttavia, utilizzare quelli già presenti in casa è sempre un'opzione.
->
Fonte: habr.com
