Un altro utente desidera scrivere un nuovo pezzo di dati su un disco rigido, ma non ha spazio disponibile. Non vuole nemmeno eliminare nulla, poiché «tutto è molto importante e necessario». E cosa possiamo fare quindi?
Questo problema non è unico per lui. Nei nostri dischi rigidi giacciono terabyte di informazioni, e questa quantità non tende a diminuire. Ma quanto è unica? Dopotutto, tutti i file sono solo insiemi di bit di una certa lunghezza e, molto probabilmente, il nuovo non differisce molto da quello già archiviato.
È chiaro che cercare già i pezzi di informazioni memorizzati su un disco rigido è un compito che, se non è fallimentare, è almeno poco efficace. D'altra parte, se la differenza è minima, si può anche modificare leggermente...
TL;DR — un secondo tentativo di raccontare un metodo strano di ottimizzazione dei dati usando file JPEG, ora in una forma più comprensibile.
Di bit e differenze
Se prendiamo due pezzi di dati completamente casuali, in media metà dei bit contenuti coincidono. Ed è vero, tra le possibili disposizioni per ogni coppia ('00, 01, 10, 11') esattamente metà ha valori coincidenti, qui è tutto semplice.
Ma certo, se semplicemente prendiamo due file e adattiamo uno all'altro, perderemo uno dei due. Se invece salviamo le modifiche, semplicemente reinventiamo , che esiste già splendidamente anche senza di noi, sebbene non venga solitamente utilizzata con questi scopi. Si può provare a integrare una sequenza più piccola in una più grande, ma anche così rischiamo di perdere segmenti critici di dati se usata imprudentemente con tutto.
Tra quali elementi possiamo quindi eliminare la differenza? Cioè, il nuovo file scritto dall'utente è semplicemente una sequenza di bit, con cui non possiamo fare nulla di utile. Dobbiamo semplicemente trovare sul disco rigido bit tali da poter essere modificati senza la necessità di conservare la differenza, in modo da poter sopportarne la perdita senza gravi conseguenze. Inoltre, ha senso modificare non solo il file stesso su FS, ma anche qualche informazione meno sensibile al suo interno. Ma quale e come?
Metodi di adattamento
Entrano in gioco i file compressi con perdita. Tutti questi jpeg, mp3 e altri, sebbene siano compressi con perdita, contengono una miriade di bit disponibili per modifiche sicure. Possono essere utilizzate tecniche avanzate che modificano in modo invisibile i loro componenti in diverse sezioni della codifica. Aspetta. Tecniche avanzate… modifica invisibile… bit in altri… questo è quasi !
E in effetti, integrare una informazione in un'altra ricorda molto i suoi metodi. Impressiona anche l'invisibilità delle modifiche effettuate per gli organi sensoriali umani. Qui è dove i percorsi si biforcano: il nostro compito è ridotto a inserire informazioni aggiuntive dall'utente sul proprio disco rigido, che gli causerebbe solo danni. Potrebbe addirittura dimenticare.
Pertanto, sebbene possiamo usarle, dobbiamo apportare alcune modifiche. E in seguito parlerò e mostrerò questo utilizzando un esempio di uno dei metodi esistenti e di un formato di file comune.
Sugli sciacalli
Se dobbiamo comprimere, scegliamo ciò che è più comprimibile al mondo. Riguarda, naturalmente, i file JPEG. Non solo esiste un sacco di strumenti e metodi esistenti per incorporare dati in esso, ma è anche il formato grafico più popolare su questo pianeta.
Tuttavia, per non occuparci di cani da caccia, è necessario limitare il proprio campo d'azione ai file di questo formato. Nessuno ama i quadrati monocromatici che si formano a causa di una compressione eccessiva, quindi dobbiamo limitarci 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, come ben illustrato nello schema di codifica (grazie a Wikipedia della biblioteca nazionale di Bauman):
Esistono molti possibili metodi di ottimizzazione dei file jpeg. C'è ottimizzazione senza perdita (jpegtran), c'è ottimizzazione “«, che in realtà ne apportano ancora altre, ma a noi non interessano. Infatti, se un utente è disposto a incorporare un'informazione in un'altra per aumentare lo spazio libero su disco, allora le sue immagini o sono già state ottimizzate da tempo, oppure non vuole farlo affatto per paura di perdere qualità.
F5
che in realtà ne apportano molte, ma a noi non interessano. Dopotutto, se l'utente è disposto a integrare un'informazione in un'altra per aumentare lo spazio libero su disco, significa che ha già ottimizzato le sue immagini o non vuole affatto farlo per paura di perdere qualità. . Il più avanzato di essi è l'algoritmo sotto la direzione di Andreas Westfeld, lavora con i coefficienti della componente luminosa, poiché l'occhio umano è meno sensibile alle sue variazioni. Inoltre, utilizza una metodologia di incorporamento basata sulla codifica a matrice, grazie alla quale si possono effettuare meno modifiche durante l'incorporazione della stessa quantità d'informazione quanto maggiore è la dimensione del contenitore utilizzato.
Le modifiche stesse consistono nella riduzione del valore assoluto dei coefficienti di un'unità in determinate condizioni (cioè, non sempre), il che consente di utilizzare F5 per ottimizzare la memorizzazione dei dati sul disco rigido. Infatti, si prevede che il coefficiente, dopo una simile modifica, occupi probabilmente un numero inferiore di bit dopo la codifica di Huffman a causa della distribuzione statistica dei valori nel JPEG, e i nuovi zeri offriranno un vantaggio nella loro codifica tramite RLE.
Le modifiche necessarie consistono nell'eliminazione della parte responsabile della segretezza (permutazione della password), che permette di risparmiare risorse e tempo, e nell'aggiunta di un meccanismo per lavorare con più file invece che uno alla volta. Maggiori dettagli sul processo di modifica probabilmente non interesseranno il lettore, quindi passiamo alla descrizione dell'implementazione.
Tecnologie avanzate
Per dimostrare la funzionalità di tale approccio, ho implementato il metodo in C puro e ho effettuato una serie di ottimizzazioni sia per la velocità di esecuzione sia per la memoria (non avete idea di quanto pesino queste immagini senza compressione anche fino a DCT). La compatibilità multipiattaforma è stata raggiunta utilizzando una combinazione di librerie , e , per cui ringrazio. Tutto questo è compilabile con 'make', quindi gli utenti Windows vogliono eventualmente installare un Cygwin o sbattersi con Visual Studio e le librerie da soli.
L'implementazione è disponibile sotto forma di utilità da linea di comando e libreria. Maggiori dettagli sull'uso di quest'ultima possono essere trovati nel readme nel repository su GitHub, del quale fornirò il link alla fine del post.
Come si utilizza?
Con cautela. Le immagini utilizzate per l'imballaggio vengono selezionate tramite espressioni regolari nella directory radice specificata. Al termine, i file possono essere spostati, rinominati e copiati a piacere al suo interno, cambiare file e sistemi operativi, ecc. Tuttavia, è fondamentale essere estremamente cauti e non modificare in alcun modo il contenuto diretto. La perdita di anche un singolo bit può portare all'impossibilità di recuperare le informazioni.
Al termine del lavoro, l'utilità lascia un file di archivio speciale che contiene tutte le informazioni necessarie per lo smaltimento, comprese le informazioni sulle immagini utilizzate. Di per sé pesa circa un paio di kilobyte e non ha un impatto significativo sullo spazio occupato sul disco.
Si può analizzare la capacità potenziale usando il flag ‘-a’: ‘./f5ar -a [cartella di ricerca] [espressione regolare compatibile con Perl]’. L'imballaggio avviene con il comando ‘./f5ar -p [cartella di ricerca] [espressione regolare compatibile con Perl] [file da imballare] [nome dell'archivio]’, mentre il disimballaggio avviene tramite ‘./f5ar -u [file dell'archivio] [nome del file ripristinato]’.
Dimostrazione del funzionamento
Per mostrare l'efficacia del metodo, ho caricato una collezione di 225 foto di cani completamente gratuite dal servizio e ho trovato un grosso pdf di 45 megabyte del secondo volume di Knuth.
La sequenza è abbastanza semplice:
$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/
$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Lettura del file di compressione... ok
Inizializzazione dell'archivio... ok
Analisi della capacità della libreria... completata in 17.0s
Capacità garantita rilevata di 48439359 byte
Capacità possibile rilevata fino a 102618787 byte
Compressione... completata in 39.4s
Salvataggio dell'archivio... ok
$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Inizializzazione dell'archivio... ok
Lettura del file dell'archivio... ok
Riempimento dell'archivio con file... completato in 1.4s
Decompressione... completata in 21.0s
Scrittura dei dati estratti... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs/
551M dogs/Screenshot per gli amanti
Il file estratto può ancora e deve essere letto:
Come si può vedere, dai 633 + 36 == 669 megabyte di dati sul disco rigido siamo arrivati a un più piacevole 551. Questa differenza radicale è spiegata dalla riduzione dei valori dei coefficienti, che influiscono sulla loro compressione successiva senza perdita: una riduzione di uno solo può tranquillamente "tagliare" un paio di byte dal file finale. Tuttavia, si tratta comunque di perdite di dati, seppure molto piccole, con cui dovremo convivere.
Fortunatamente, non sono affatto visibili all'occhio. Sotto il spoiler (poiché habrastorage non supporta file di grandi dimensioni) il lettore può valutare la differenza sia visivamente sia in base all'intensità, ottenuta sottraendo i valori della componente modificata da quelli originali: , , (più il colore è opaco, minore è la differenza nel blocco).
In conclusion
Considerando tutte queste difficoltà, acquistare un disco rigido o caricare tutto nel cloud potrebbe sembrare una soluzione molto più semplice al problema. Ma anche se ora viviamo in un’epoca così bella, non ci sono garanzie che domani si potrà ancora accedere a Internet e caricare da qualche parte tutti i propri dati superflui. O entrare in negozio e acquistare un altro disco rigido da mille terabyte. Tuttavia, si possono sempre utilizzare quelli già in casa.
->
Fonte: habr.com
