Kuidas erikujuline meetod kõvaketta ruumi säästmiseks

Järjekordne kasutaja soovib kirjutada kõvakettale uue andmeploki, kuid tal pole selleks piisavalt vaba ruumi. Ei soovi ka midagi kustutada, sest "kõik on väga oluline ja vajalik". Mida me sellega teeme?

Selline probleem ei ole ainult tema oma. Meie kõvaketastel lebab teraabandeid teavet, ja see arv ei kavatse väheneda. Kuid kui unikaalne see on? Lõppude lõpuks on kõik failid lihtsalt kindla pikkusega bitikogumid ning tõenäoliselt ei erine uus oluliselt juba salvestatud failist.

Muidugi on juba salvestatud andmepalade leidmine kõvakettalt kui mitte lootusetu, siis vähemalt ebaefektiivne ülesanne. Teisest küljest, kui erinevus on väike, siis võib-olla natuke kohandada ...

TL;DR — teine katse rääkida kummalisest andmete optimeerimise meetodist JPEG-failide abil, nüüd arusaadavamal kujul.

Bitidest ja erinevustest

Kui võtta kaks täiesti juhuslikku andmeplokki, siis on nende bittide keskmine kattuvus pooled. Tõepoolest, igas paaris (’00, 01, 10, 11′) on just pooled väärtustele kattuvuses, see on lihtne.

Aga loomulikult, kui me lihtsalt võtame kaks faili ja kohandame ühe teise järgi, kaotame me ühe neist. Kui aga salvestame muudatused, siis leiutame lihtsalt uuesti. delta-kodeerimine, mis eksisteerib ka ilma meie abita, kuigi tavaliselt ei kasutata seda samadel eesmärkidel. Saame proovida väiksema järjestuse integreerimist suuremasse, kuid isegi sel juhul riskime andmefragmentide kriitilise kaduja kaotamisega, kui kasutame seda kõike määgiliselt.

Millest ja millisest on siis võimalik erinevust kõrvaldada? Noh, see tähendab, et kasutaja salvestatud uus fail on lihtsalt bitijada, millega me iseenesest midagi teha ei saa. Seega tuleks järjest otsida kõvakettalt selliseid bitte, mida saaks muuta ilma vajaduseta erinevust salvestada, et oleks võimalik nende kadumist üle elada tõsiste tagajärgedeta. Ja on mõistlik muuta mitte ainult faili failisüsteemis, vaid ka mingit vähem tundlikku teavet selle sees. Kuid mida ja kuidas?

Sobivusmeetodid

Appi tulevad kaotusega tihendatud failid. Kõik need jpeg, mp3 ja muud sarnased, kuigi nad on kaotusega tihendatud, sisaldavad palju bitte, mida on ohutu muuta. Saame kasutada edasijõudnud tehnikaid, mis märkamatult modifitseerivad nende komponente erinevates kodeerimise osades. Oodake. Edasijõudnud tehnikad… märkamatud modifikatsioonid… ühte bitte teiseks… see on ju peaaegu steganograafia!

Tõepoolest, teabe ühte vormi integreerimine meenutab selle meetodeid. Mul on mulje, et muudatused ei ole inimmeele jaoks tuvastatavad. Siinkohal lähevad teed lahku — meie ülesanne on võimaldada kasutajal oma kõvakettale lisainfot salvestada, mis võib talle ainult kahju tuua. Ta unustab selle veel.

Seetõttu, kuigi me saame neid kasutada, on vajalik teha mõned muudatused. Edasi seletan ja näitan neid ühe olemasoleva meetodi ja laialdaselt kasutatava failivormingu näitel.

Šakaalid

Kui juba tihendada, siis maailma kõige tihendatumat. Räägime loomulikult JPEG-failidest. Lisaks sellele, et on olemas tohutult tööriistu ja meetodeid andmete integreerimiseks neisse, on see kõige populaarsem graafiline formaat meie planeedil.

Siiski, et mitte koeratoitmist teha, tuleb piirata oma tegevusala selle formaadi failidega. Keegi ei armasta ühevärvilisi ruute, mis tekivad liigse tihendamise tõttu, seetõttu tuleks töötada juba tihendatud failiga, vältides ümberkodeerimist.. Konkreetsemalt — täisarvuliste koefitsientidega, mis jäävad alles pärast operatsioone, mis vastutavad andmete kadumise eest — DKP ja kvantimine, mida on suurepäraselt kujutatud kodeerimise skeemil (aitäh Bauman'i nimelise raamatukogu Vikile):

JPEG-failide optimeerimise meetodeid on palju. On kadudeta optimeerimine (jpegtran), on optimeerimine «ilma kaotusteta«, mis tegelikult toovad sisule veel midagi, aga meid need ei huvita. Kui kasutaja on valmis ühte teavet teise sisse embedima, et suurendada vaba ruumi diskil, siis on ta oma pilte kas juba ammu optimeerinud või ei taha sellest üldse kuulda, kartes kvaliteedi kaotust.

F5

Selliste tingimuste alla sobib suur hulk algoritme, millega saab tutvuda selles heas esituses. Kõige arenenum neist on algoritm F5 Andreas Westfeldi autoriteet, kes töötab heleduskomponentide koefitsientidega, kuna inimsilma tundlikkus on nende muutuste suhtes kõige väiksem. Veelgi enam, ta rakendab kodeerimismatriisi põhjal embedimisprotsessi, mis võimaldab saavutada vähem muutusi sama informatsiooni embedimise korral, kui konteineri suurus on suurem.

Muudatused piirdusid koefitsiendi absoluutväärtuse vähendamisega ühe väärtuse võrra teatud tingimustes (ehkki mitte alati), mis võimaldab kasutada F5 andmete salvestamise optimeerimiseks kõvakettal. Asi on selles, et pärast seda muutust on koefitsient tõenäoliselt väiksema bittide arvu all Huffmani kodeerimise tõttu JPEG-i väärtuste statistilise jaotuse põhjal ning uued nullid pakuvad RLE kodeerimisel eeliseid.

Tugemised muudatused seisnevad osa kõrvaldamises, mis vastutab privaatsuse (parooli segamise) eest, mis võimaldab säästa ressursse ja täitmise aega, ning mitme faili töötlemise mehhanismi lisamises ühe faili asemel. Protsessi muutmise kohta ei pruugi lugejale üksikasjad huvi pakkuda, seega liigume edasi rakendamise kirjeldusele.

Tipptasemel tehnoloogia

Sellise lähenemise demonstreerimiseks rakendasin meetodi puhta C keeles ning viisain läbi rea optimeerimisi nii täitmise kiirusel kui ka mälus (te ei kujuta ette, kui palju need pildid kaaluvad isegi kohelduna DCT jaoks). Platvormidevaheline tugi saavutatakse raamatukogude kombinatsiooni kasutamisega. libjpeg, pcre ja tinydir, mille eest neile tänu. Kõik see kogutakse ‘make’ käsuga, seega Windowsi kasutajad peavad hindamiseks endale installima Cygwini või iseseisvalt Visual Studio ja raamatukogudega tegelema.

Rakendus on saadaval konsooli utiliidi ja raamatukoguna. Üksikasjalikumalt viimase kasutamisest saavad huvilised tutvuda readmi kaudu GitHubis, mille lingi lisan postituse lõppu.

Kuidas kasutada?

Ohtus on tõhus. Pildid, mida kasutatakse pakkimiseks, valitakse määratud juurkatalooge sobitades regulaarselt väljendeid. Pärast seda saab faile soovitud viisil liigutada, nime muuta ja kopeerida, samuti operatsioonisüsteemi ja faile muuta jne. Siiski tuleb olla äärmiselt ettevaatlik ja mitte muuta sisu. Isegi ühe biti väärtuse kaotamine võib põhjustada teabe taastamise võimatuse.

Pärast töö lõpetamist jätab utiliit erifaili, mis sisaldab kogu vajalikku teavet dekompresseerimiseks, sealhulgas teavet kasutatud piltide kohta. Fail kaalub iseenesest paar kilobaiti ja ei avalda mingit märkimisväärset mõju kasutatud kettaruumi hulgale.

Võimaliku mahutavuse analüüsimiseks saab kasutada lippu ‘-a’: ‘./f5ar -a [otsingukaust] [Perl-ühilduv regulaarne väljend]’. Pakkimine toimub käsu abil ‘./f5ar -p [otsingukaust] [Perl-ühilduv regulaarne väljend] [pakitav fail] [arhivi nimi]’, ent dekompresseerimine toimub käsuga ‘./f5ar -u [arhivifail] [taastatud faili nimi]’.

Demonstratsioon

Meetodi efektiivsuse näitamiseks laadisin üles 225 täiesti tasuta koerapilti teenusest Unsplash ja ja leidis dokumentidest suure pdf-faili, mille pikkus on 45 meetrit, teise köite kohta Programmimise Kunst Knuth.

Järjestus on üsna lihtne:

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

$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Loen tihendatud faili... okei
Arhiivi initsialiseerimine... okei
Raamatukogude kapatsiteedi analüüs... tehtud 17,0s
Tuvastatud - mingil määral garanteeritud maht 48439359 bait
Tuvastatud võimalik maht kuni 102618787 bait
Tihendamine... tehtud 39,4s
Arhiivi salvestamine... okei

$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Arhiivi initsialiseerimine... okei
Lugen arhiivifaili... okei
Arhiivi täitmine failidega... tehtud 1,4s
Dekompressioon... tehtud 21,0s
Asetatud andmete kirjutamine... okei

$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf

$ du -sh dogs/
551M dogs/

Ekraanipildid entusiastidele

Pärast lahtipakkimist on faili endiselt võimalik ja vajalik lugeda:

Nagu näha, liikusime algsetelt 633 + 36 == 669 megabaidilt kõvakettal meeldivamale 551-le. Selline radikaalne erinevus seletab neid sama määrade langust, mis mõjutavad nende hilisemaid kahjutuid tihendamise väärtusi: ühe nt vähendamine võib rahulikult «läikida» paar bait'i lõppfailist. Siiski on see ikkagi andmete kadu, ehkki äärmiselt väike, millega tuleb leppida.

Õnneks pole need silmale absoluutselt nähtavad. Spoileri all (kuna habrastorage ei suuda suuri faile töödelda) saab lugeja hinnata vahet nii visuaalselt kui ka nende intensiivsust, mis on saadud muudetud komponendi väärtuste originaalist lahutamisel: originaal, teabega sees, vahe (mida tuhmim on värv, seda vähem on erinevusi blokis).

Kokkuvõtte asemel

Vaadates kõiki neid keerukusi, võib kõvaketta ostmine või kõik pilve üles laadimine tunduda palju lihtsama lahendusena. Kuid kuigi me elame praegu nii ilusas ajastus, ei ole mingit garantiid, et homme on endiselt võimalik internetti pääseda ja kogu oma liigse teabe kuhugi üles laadida. Või minna poodi ja osta endale uus tuhat terabaidi kõvaketas. Kuid kodus juba olemasolevat saab alati kasutada.

-> GitHub

Allikas: habr.com