Um undarlega aðferð til að spara pláss á harða disknum

Annar notandi vill skrifa nýtt gögn á harða diskinn en hann hefur ekki nóg pláss til að gera þetta. Ég vil heldur ekki eyða neinu, þar sem "allt er mjög mikilvægt og nauðsynlegt." Og hvað eigum við að gera við það?

Enginn á við þetta vandamál að stríða. Það eru terabæt af upplýsingum á hörðum diskum okkar og þetta magn hefur ekki tilhneigingu til að lækka. En hversu einstakt er það? Að lokum eru allar skrár bara sett af bitum af ákveðinni lengd og líklega er sú nýja ekki mikið frábrugðin þeirri sem þegar er geymd.

Það er ljóst að leit að upplýsingum sem þegar eru geymdar á harða disknum er, ef ekki bilun, þá að minnsta kosti ekki árangursríkt verkefni. Aftur á móti, ef munurinn er lítill, þá er hægt að stilla hann aðeins...

TL;DR - önnur tilraunin til að tala um undarlega aðferð til að fínstilla gögn með JPEG skrám, nú í skiljanlegri mynd.

Um bita og mismun

Ef þú tekur tvö algjörlega tilviljunarkennd gögn, þá fellur að meðaltali helmingur bitanna sem þeir innihalda saman. Reyndar, meðal mögulegra útlita fyrir hvert par ('00, 01, 10, 11′), hefur nákvæmlega helmingur sömu gildi, allt er einfalt hér.

En auðvitað, ef við tökum bara tvær skrár og pössum eina við aðra, þá missum við eina af þeim. Ef við vistum breytingarnar munum við einfaldlega finna upp á nýtt delta kóðun, sem er fullkomlega til án okkar, þó að það sé venjulega ekki notað í sömu tilgangi. Við getum reynt að fella minni röð inn í þá stærri, en þó eigum við á hættu að missa mikilvæga hluta af gögnum ef við notum þau kæruleysislega með öllu.

Á milli hvers og hvers er þá hægt að eyða mismuninum? Jæja, það er að segja, ný skrá skrifuð af notandanum er bara röð bita, sem við getum ekki gert neitt af sjálfu sér. Þá þarf bara að finna slíka bita á harða disknum að hægt sé að breyta þeim án þess að þurfa að geyma mismuninn, þannig að þú getur lifað tap þeirra af án alvarlegra afleiðinga. Og það er skynsamlegt að breyta ekki bara skránni á FS sjálfum, heldur einhverjum minna viðkvæmum upplýsingum inni í henni. En hver og hvernig?

Mátunaraðferðir

Tapaðar þjappaðar skrár koma til bjargar. Allar þessar jpeg-myndir, mp3-myndir og fleiri, þó að þjöppun sé taps, innihalda fullt af bitum sem hægt er að breyta á öruggan hátt. Það er hægt að nota háþróaða tækni sem ómerkjanlega breytir íhlutum þeirra á ýmsum stigum kóðun. Bíddu. Háþróuð tækni ... ómerkjanleg breyting ... einn bitinn í annan ... það er næstum eins og stiganography!

Reyndar minnir það á aðferðir hennar að fella eina upplýsingar inn í aðra eins og ekkert annað. Ég er líka hrifinn af því hversu ómerkjanlegar breytingarnar sem gerðar eru á skynfærum mannsins. Þar sem leiðir skilja er leynd: Verkefni okkar kemur niður á því að notandinn slær inn viðbótarupplýsingar á harða diskinn sinn; það mun aðeins skaða hann. Hann mun gleyma aftur.

Þess vegna, þó við getum notað þau, þurfum við að gera nokkrar breytingar. Og þá mun ég segja frá og sýna þá með því að nota dæmi um eina af núverandi aðferðum og algengu skráarsniði.

Um sjakala

Ef þú kreistir það virkilega, þá er það samþjappaðasta hlutur í heimi. Við erum auðvitað að tala um JPEG skrár. Það eru ekki aðeins fullt af verkfærum og núverandi aðferðum til að fella gögn inn í það, heldur er það vinsælasta grafíksniðið á þessari plánetu.

Hins vegar, til þess að taka ekki þátt í hundarækt, þarftu að takmarka starfssvið þitt í skrám á þessu sniði. Engum líkar einlita ferninga sem birtast vegna of mikillar þjöppunar, svo þú þarft að takmarka þig við að vinna með þegar þjappaða skrá, forðast endurkóðun. Nánar tiltekið, með heiltölustuðlum, sem eru eftir eftir aðgerðir sem bera ábyrgð á gagnatapi - DCT og magngreiningu, sem er fullkomlega birt í kóðunkerfinu (þökk sé wiki Bauman Landsbókasafnsins):

Það eru margar mögulegar aðferðir til að fínstilla jpeg skrár. Það er taplaus hagræðing (jpegtran), það er hagræðing "ekkert tap“, sem í raun leggja eitthvað annað til, en okkur er alveg sama um þá. Þegar öllu er á botninn hvolft, ef notandinn er tilbúinn að fella eina upplýsingar inn í aðra til að auka laust diskpláss, þá hefur hann annað hvort fínstillt myndirnar sínar fyrir löngu síðan, eða vill alls ekki gera þetta af ótta við gæðatap.

F5

Heil fjölskylda reiknirita passar við þessar aðstæður, sem þú getur kynnt þér í þessari góðu kynningu. Það fullkomnasta þeirra er reikniritið F5 eftir Andreas Westfeld, sem vinnur með stuðla birtuþáttarins, þar sem mannsaugað er minnst næmt fyrir breytingum hans. Þar að auki notar það innfellingartækni sem byggir á fylkiskóðun, sem gerir það mögulegt að gera færri breytingar þegar sama magn upplýsinga er fellt inn, því stærri sem ílátið er sem notað er.

Breytingarnar sjálfar ganga út á að lækka algildi stuðlanna um einn við ákveðnar aðstæður (þ.e. ekki alltaf), sem gerir þér kleift að nota F5 til að hámarka gagnageymslu á harða disknum þínum. Málið er að stuðullinn eftir slíka breytingu mun líklegast taka færri bita eftir Huffman kóðun vegna tölfræðilegrar dreifingar gilda í JPEG, og nýju núllin munu gefa ávinning þegar þau eru kóðuð með RLE.

Nauðsynlegar breytingar ganga út á að útrýma þeim hluta sem ber ábyrgð á leynd (endurröðun lykilorða), sem sparar auðlindir og framkvæmdartíma, og bæta við kerfi til að vinna með margar skrár í stað eina í einu. Ekki er líklegt að lesandinn hafi áhuga á breytingaferlinu nánar, svo við skulum halda áfram í lýsingu á framkvæmdinni.

Hátækni

Til að sýna fram á hvernig þessi nálgun virkar, innleiddi ég aðferðina í hreinu C og framkvæmdi fjölda hagræðinga bæði hvað varðar keyrsluhraða og minni (þú getur ekki ímyndað þér hversu mikið þessar myndir vega án þjöppunar, jafnvel fyrir DCT). Þverpalla náð með því að nota blöndu af bókasöfnum libjpeg, tölvu и örlítið, sem við þökkum þeim fyrir. Allt þetta er sett saman af 'make', svo Windows notendur vilja setja upp Cygwin fyrir sig til að meta, eða takast á við Visual Studio og bókasöfn á eigin spýtur.

Útfærslan er fáanleg í formi console gagnsemi og bókasafns. Áhugasamir geta fundið meira um notkun þess síðarnefnda í readme í geymslunni á Github, hlekkinn sem ég mun hengja á í lok færslunnar.

Hvernig á að nota?

Varlega. Myndirnar sem notaðar eru fyrir pökkun eru valdar með því að leita með venjulegri tjáningu í tiltekinni rótarskrá. Þegar þeim er lokið er hægt að færa skrár, endurnefna og afrita að vild innan þeirra marka, breyta skrám og stýrikerfum o.s.frv. Hins vegar ættir þú að vera mjög varkár og ekki breyta strax innihaldi á nokkurn hátt. Að missa gildi jafnvel einn bita getur gert það ómögulegt að endurheimta upplýsingar.

Þegar því er lokið skilur tólið eftir sérstakt skjalasafn sem inniheldur allar nauðsynlegar upplýsingar til að pakka niður, þar á meðal gögn um myndirnar sem notaðar eru. Út af fyrir sig vegur það um nokkur kílóbæti og hefur ekki nein veruleg áhrif á upptekið pláss.

Þú getur greint mögulega getu með því að nota '-a' fánann: './f5ar -a [leitarmöppu] [Perl-samhæfð regluleg tjáning]'. Pökkun er gerð með skipuninni './f5ar -p [leitarmöppu] [Perl-samhæfð regluleg tjáning] [pakkað skrá] [nafn skjalasafns]', og upppakkning með './f5ar -u [skjalasafn] [endurheimt skráarnafn ]'.

Sýning á vinnu

Til að sýna árangur aðferðarinnar hlóð ég upp safni af 225 algerlega ókeypis myndum af hundum frá þjónustunni Unsplash og fann í skjölunum stóra pdf af 45 metrum af öðru bindi Forritunarlist Knúta.

Röðin er frekar einföld:

$ 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/

Skjáskot fyrir aðdáendur

Ópakkaða skrána má og ætti enn að lesa:

Eins og þú sérð, frá upprunalegu 633 + 36 == 669 megabæti af gögnum á harða disknum, komum við að skemmtilegri 551. Slíkur róttækur munur skýrist af lækkun á gildum stuðlanna, sem hefur áhrif á þeirra taplaus þjöppun í kjölfarið: með því að minnka einn í einu getur auðveldlega „skorið nokkur bæti af lokaskránni. Hins vegar er þetta enn gagnatap, þó afar lítið sé, sem þú verður að sætta þig við.

Sem betur fer eru þeir algjörlega ósýnilegir fyrir augað. Undir spoilernum (þar sem habrastorage ræður ekki við stórar skrár) getur lesandinn metið muninn bæði með augum og styrkleika þeirra, sem fæst með því að draga gildi breytts íhlutans frá upprunalegu: frumritið, með upplýsingum inni, munur (því daufari sem liturinn er, því minni munur á kubbnum).

Í stað þess að niðurstöðu

Miðað við alla þessa erfiðleika gæti það virst vera miklu einfaldari lausn á vandamálinu að kaupa harða diskinn eða hlaða öllu upp í skýið. En þó svo að við lifum á svo yndislegum tíma núna er engin trygging fyrir því að á morgun verði enn hægt að fara á netið og hlaða upp öllum aukagögnum einhvers staðar. Eða farðu út í búð og keyptu þér á annað þúsund terabæta harðan disk. En þú getur alltaf notað núverandi hús.

-> GitHub

Heimild: www.habr.com