Kummalisest meetodist ketta ruumi säästmiseks

Järjekordne kasutaja soovib kõvakettale salvestada uut andmeplokki, kuid tal puudub selle jaoks vaba koht. Samuti ei taha ta midagi kustutada, kuna "kõik on väga oluline ja vajalik". Mida me temaga siis teeme?

Sama probleem ei ole ainult tema mure. Meie kõvaketastel puhkab terabyte kaupa informatsiooni ning see kogus ei kavatse kahaneda. Kuid kui unikaalne see on? Lõppude lõpuks on kõik failid lihtsalt teatud pikkusega bitikogumid ja tõenäoliselt ei erine uus oluliselt sellest, mis juba salvestatud.

Selge on see, et juba salvestatud andmepulkade otsimine kõvakettal on ülesanne, mis on vähemalt mitteefektiivne, kui mitte hoopis lootusetu. Teisest küljest, kui erinevused on väikesed, siis võib neid ju veidi kohandada...

TL;DR — teine katse rääkida kummalisest andmete optimeerimise meetodist JPEG-failide abil, seekord arusaadavamas vormis.

Bitidest ja erinevustest

Kui võtta kaks täiesti juhuslikku andmepulka, siis on nende vahel keskmiselt pooled bitsid ühesugused. Tõepoolest, iga paari (’00, 01, 10, 11′) võimalike kombinatsioonide seas on täpselt pooled omavahel kattuvad, siin on kõik lihtne.

Kuid muidugi, kui me lihtsalt võtame kaks faili ja kohandame ühe teise järgi, siis kaotame me ühe neist. Kui aga säilitame muudatused, siis leiutame lihtsalt uuesti delta-koodimise, mis eksisteerib ilma meie abita suurepäraselt, kuigi ei kasutata tavaliselt sarnastes eesmärkides. Saame proovida väiksemat järjestust suuremasse integreerida, kuid isegi siis riskime me oluliste andmesegmentide kaotamisega, kui me kasutame seda mõtlematult koos millegagi.

Mille vahel siis on võimalik erinevust kõrvaldada? Niisiis, kasutaja salvestatav uus fail — lihtsalt bitijada, millega me iseenesest midagi teha ei saa. Peame lihtsalt leidma kõvakettalt sellised bitid, mida saab muuta ilma, et peaksime salvestama erinevust, et saaksime nende kaotamise ilma tõsiste tagajärgedeta üle elada. Ja on mõtet muuta mitte ainult fail ise failisüsteemis, vaid ka mõnda vähem tundlikku teavet selle sees. Kuid millist ja kuidas?

Kohandamismeetodid

Abi aitavad kaotatud andmetega kokku surutud failid. Kõik need jpeg, mp3 ja muud, kuigi nad on kaotatud kompressiooni, sisaldavad hulga bitte, mis on ohutult muudetavad. Saame kasutada edasijõudnud tehnikaid, mis muudavad nende komponente märkamatult erinevates kodeerimise osades. Oota. Edasijõudnud tehnikad… märkamatud muudatused… mõned bitid muudesse… see on peaaegu steganograafia!

Tõepoolest, ühe teabe peidetud teise sisse meenutab see meetodeid nagu ükski teine. Samuti muljetavaldav on tehtud muudatuste märkamatuks jäämine inimeste aistingute jaoks. Siin on teed lahku minemas — nii et meie ülesanne on lisada kasutaja kõvakettale täiendavat teavet, mis talle enamasti ainult kahju toob. Unustab selle veel.

Seetõttu, kuigi me saame neid kasutada, peame need kohandama. Edasi räägin ja näitan neid ühte olemasolevatest meetoditest ja levinud failiformaadist.

Šakalitest

Kui juba komprimeerida, siis kõige kokku surutuma maailmas. Räägime loomulikult JPEG-failidest. Lisaks sellele, et olemas on tohutult tööriistu ja meetodeid, et andmeid sinna peita, on see planeedi kõige populaarsem graafiline formaat.

Siiski, et koerust teha, tuleb piirata oma tegevusala selle formaadi failides. Keegi ei armasta ühevärvilisi ruute, mis tekivad ülemäärasest kompressioonist, seetõttu peaks piirduma juba kokku surutud failiga, välja arvatud ümberkodeerimine. Konkreetselt — täisarvukvoodiga, mis jääb andmete kaotsimineku eest vastutavate operatsioonide — DCT ja kvantimise — järel, mis on suurepäraselt kujutatud kodeerimise skeemil (aitäh Baumanu riikliku raamatukogu wikile):

JPEG-failide optimeerimiseks on olemas palju võimalikke meetodeid. On kaotusteta optimeerimine (jpegtran), on optimeerimine “kaotusteta“, mis tegelikult toovad veel rohkem, kuid meid need ei huvita. Sest kui kasutaja on valmis ühe teabe teise sisse peitma, et suurendada kõvakettal vaba ruumi, siis on ta oma pilte juba ammu optimeerinud või ei taha seda üldse teha, kartes kvaliteedi kaotust.

F5

Selle tingimuste alla sobivad kogu rida algoritme, millega saab tutvuda selles heas esituses. Kõige arenenum neist on algoritm F5 autoriõigusega Andreas Westfeld, mis töötab heleduskomponendi koefitsientidega, kuna inimsilmas on kõige vähem tundlikud just nende muutustele. Veelgi enam, see kasutab sisestamismeetodit, mis põhineb maatriksi kodeerimisel, sundides seega muutma vähem koefitsiente sama informatsiooni sisestamiseks, mida suurem on kasutatava konteineri suurus.

Iseenesest muutused vähendavad absoluutsete koefitsientide väärtust üksuse võrra teatud tingimustel (st mitte alati), mis võimaldab F5 kasutada andmete salvestamise optimeerimiseks kõvakettale. Asi on selles, et pärast selliseid muutusi võib koefitsient tõenäoliselt nõuda vähem bitte pärast Huffmani kodeeringu tegemist JPEGis, ja uued nullid toovad kasu nende kodeerimisel RLE abil.

Kohustuslikud muudatused piirduvad osa eemaldamisega, mis vastutab konfidentsiaalsuse (paroolide segamise) eest, mis säästab ressursse ja täitmise aega, ning mitmete failidega töötamise mehhanismi lisamisega korraga ühe asemel. Üksikasjalikumalt protsessist kindlasti lugejale huvitav ei tundu, liikume seetõttu elluviimise kirjeldamise juurde.

Tipptehnoloogia

Selle lähenemise töö demonstreerimiseks realiseerisin meetodi puhaskoodis ja tegin mitmeid optimeerimisi nii täitmise kiirusel kui ka mälu osas (te ei kujuta ette, kui palju need pildid kaaluvad isegi alati DCT-ni kompressimata). Platvormideülene teostatavus saavutati raamatukogude kombinatsiooni abil libjpeg, pcre ja tinydir, mille eest neile tänu. Kõik see kokku pannakse „make’iga, seega soovivad Windowsi kasutajad hindamiseks paigaldada Cygwini või tegeleda Visual Studio ja raamatukogudega iseseisvalt.

Teostus on saadaval konsooli utiliidi ja raamatukogu kujul. Rohkem teavet viimase kasutamise kohta võivad huvilised leida readmi failist GitHubi hoidlas, mille lingi ma postituse lõpus lisaks.

Kuidas kasutada?

Ohtlikult. Pildifailide pakendamiseks kasutatakse regulaaravaldiste põhjal otsitud faile määratud juurkataloogis. Lõpetamisel saab faile liigutada, ümber nimetada ja kopeerida soovi korral nende sees, muuta failisüsteemi ja operatsioonisüsteemi jne. Kuid tuleb olla äärmiselt ettevaatlik ja mitte muuta otsest sisu. Isegi ühe bit'i väärtuse kaotamine võib viia teabe taastamise võimatuks.

Lõpetamisel jätab utiliit spetsiaalse arhivifaili, mis sisaldab kogu vajalikku info täieliku taastamise jaoks, sealhulgas kasutatud piltide andmeid. Selle suurus on umbes paar kilobaiti ja see ei avalda suuremat mõju hõivatud kettaruumi peale.

Võimaliku mahtuvuse analüüsimiseks saab kasutada lippu ‘-a’: ‘./f5ar -a [otsingukaust] [Perl-ühilduv regulaaravaldis]’. Pakendamine toimub käsuga ‘./f5ar -p [otsingukaust] [Perl-ühilduv regulaaravaldis] [pakendatav fail] [arhivi nimi]’, ja pakkimise taastamine toimub käsuga ‘./f5ar -u [arhivi fail] [taastatud faili nimi]’.

Töö demonstreerimine

Kuna meetodi efektiivsust näidata, laadisin üles kogu 225 täiesti tasuta koera fotograafia kogu teenusest. Unsplash ja leidsin dokumentidest suure 45-megabaidise pdf-i teise köite. Programmeerimise Kunst Knuth.

Järjekord on üsna lihtne:

$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/

$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
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 up to 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'id huvilistele

Taastatud faili saab ja tuleb veel lugeda:

Kuidas näha, lähtudes algsetest 633 + 36 == 669 megabaidist andmeid kõvakettal, oleme jõudnud meeldivamate 551-ni. See radikaalne erinevus tuleneb täpselt nende koefitsientide väärtuste vähenemisest, mis mõjutavad edasist kaotusteta tihendamist: üheainese vähenemine võib rahulikult „lõigata“ paar bait viimasesse faili. Sellegipoolest on need siiski andmete kadumised, kuigi äärmiselt väikesed, millega tuleb leppida.

Õnneks ei ole need silmale absoluutselt märgatavad. Spoileris (kuna habrastorage ei oska suurtest failidest) saab lugeja hinnata erinevust nii visuaalselt kui ka nende intensiivsust, mis saadakse muudetud komponendi väärtuste lahutamisega originaalist: originaal, infoga sees, erinevus (mida tuhmim on värv, seda väiksem on erinevus plokis).

Lõpetuseks

Vaadates kõiki neid keerukusi, võib kõvaketta ostmine või kõik pilve laadimine tunduda palju lihtsam lahendus probleemile. Kuid kuigi elame praegu ilusas ajastus, ei ole mingeid garantiisid, et homme saab veel internetti minna ja kõik oma üleliigsed andmed kuhugi üles laadida. Või minna poodi ja osta endale järjekordne tuhande terabaidi kõvaketas. Samas võib alati kasutada juba kodus olevaid.

-> GitHub

Allikas: habr.com