За чуден метод за заштеда на простор на тврдиот диск

Друг корисник сака да напише нов податок на хард дискот, но нема доволно слободен простор за да го направи тоа. Исто така, не сакам да избришам ништо, бидејќи „сè е многу важно и неопходно“. И што да правиме со тоа?

Никој го нема овој проблем. Има терабајти информации на нашите хард дискови и оваа количина нема тенденција да се намалува. Но, колку е уникатен? На крајот, сите датотеки се само збирки од битови со одредена должина и, најверојатно, новата не се разликува многу од онаа што е веќе зачувана.

Јасно е дека пребарувањето на делови од информации веќе зачувани на хард диск е, ако не неуспех, тогаш барем не е ефикасна задача. Од друга страна, ако разликата е мала, тогаш можете малку да ја прилагодите ...

TL;DR - втор обид да се зборува за чуден метод за оптимизирање на податоците користејќи JPEG-датотеки, сега во поразбирлива форма.

За битови и разлика

Ако земете два сосема случајни парчиња податоци, тогаш во просек половина од битови што ги содржат се совпаѓаат. Навистина, меѓу можните распореди за секој пар ('00, 01, 10, 11'), точно половина ги имаат истите вредности, сè е едноставно овде.

Но, се разбира, ако земеме само две датотеки и ја вклопиме едната во втората, тогаш ќе изгубиме една од нив. Ако ги зачуваме промените, едноставно повторно ќе измислиме делта кодирање, кој совршено постои и без нас, иако обично не се користи за исти цели. Можеме да се обидеме да вградиме помала секвенца во поголема, но и покрај тоа ризикуваме да изгубиме критични сегменти од податоците ако ги користиме непромислено со сè.

Помеѓу што и што тогаш може да се елиминира разликата? Па, тоа е, нова датотека напишана од корисникот е само низа од битови, со кои не можеме да направиме ништо сама по себе. Тогаш само треба да најдете такви битови на хард дискот што ќе можат да се сменат без да мора да ја складирате разликата, за да можете да ја преживеете нивната загуба без сериозни последици. И има смисла да се смени не само датотеката на самиот FS, туку и некои помалку чувствителни информации во него. Но, кој и како?

Методи на монтирање

Загубените компресирани датотеки доаѓаат на помош. Сите овие jpegs, mp3 и други, иако се со загуба на компресија, содржат еден куп битови што можат безбедно да се променат. Можно е да се користат напредни техники кои незабележливо ги менуваат нивните компоненти во различни фази на кодирање. Чекај. Напредни техники... незабележлива модификација... еден дел во друг... тоа е речиси како стеганографија!

Навистина, вградувањето на една информација во друга потсетува на нејзините методи како ништо друго. Импресиониран сум и од незабележливоста на промените направени во човечките сетила. Онаму каде што патеките се разминуваат е во тајност: нашата задача се сведува на тоа корисникот да внесе дополнителни информации на неговиот хард диск; тоа само ќе му наштети. Пак ќе заборави.

Затоа, иако можеме да ги користиме, треба да направиме некои модификации. И тогаш ќе им кажам и ќе им покажам користејќи го примерот на еден од постоечките методи и заеднички формат на датотека.

За шакалите

Ако навистина го исцедите, тоа е најкомпресивното нешто на светот. Ние, се разбира, зборуваме за JPEG-датотеки. Не само што постојат тони алатки и постоечки методи за вметнување податоци во него, туку тој е најпопуларниот графички формат на оваа планета.

Меѓутоа, за да не се занимавате со одгледување кучиња, треба да го ограничите вашето поле на активност во датотеки од овој формат. Никој не сака монохроматски квадрати што се појавуваат поради прекумерна компресија, па затоа треба да се ограничите на работа со веќе компресирана датотека, избегнување на прекодирање. Поконкретно, со целобројни коефициенти, кои остануваат по операциите одговорни за загуба на податоци - DCT и квантизација, што е совршено прикажано во шемата за кодирање (благодарение на викито на Националната библиотека Бауман):

Постојат многу можни методи за оптимизирање на jpeg-датотеките. Постои оптимизација без загуби (jpegtran), постои оптимизација "нема загуби“, кои всушност придонесуваат за нешто друго, но ние не се грижиме за нив. На крајот на краиштата, ако корисникот е подготвен да вгради една информација во друга за да го зголеми слободниот простор на дискот, тогаш тој или ги оптимизирал своите слики одамна, или воопшто не сака да го стори тоа поради страв од губење на квалитетот.

F5

Цело семејство алгоритми одговара на овие услови, со кои можете да се запознаете во оваа добра презентација. Најнапредниот од нив е алгоритмот F5 од Андреас Вестфелд, работејќи со коефициентите на компонентата на осветленоста, бидејќи човечкото око е најмалку чувствително на неговите промени. Покрај тоа, тој користи техника за вградување базирана на матрично кодирање, што овозможува да се направат помалку промени при вградување на иста количина на информации, колку е поголема големината на контејнерот што се користи.

Самите промени се сведуваат на намалување на апсолутната вредност на коефициентите за еден под одредени услови (тоа е, не секогаш), што ви овозможува да користите F5 за да го оптимизирате складирањето податоци на вашиот хард диск. Поентата е дека коефициентот по таквата промена најверојатно ќе зафаќа помалку битови по кодирањето на Хафман поради статистичката распределба на вредностите во JPEG, а новите нули ќе дадат добивка при нивното кодирање со помош на RLE.

Потребните модификации се сведуваат на елиминирање на делот одговорен за тајност (преуредување на лозинката), што заштедува ресурси и време за извршување и додавање механизам за работа со многу датотеки наместо една по една. Малку е веројатно дека читателот ќе биде заинтересиран за процесот на промена подетално, па да преминеме на опис на имплементацијата.

Висока Технологија

За да покажам како функционира овој пристап, го имплементирав методот во чист C и извршив голем број оптимизации и во однос на брзината на извршување и меморијата (не можете да замислите колку тежат овие слики без компресија, дури и пред DCT). Крос-платформа постигната со помош на комбинација на библиотеки libjpeg, парче и малдир, за што им благодариме. Сето ова е составено од „make“, па корисниците на Windows сакаат да инсталираат Cygwin за себе за евалуација или сами да се занимаваат со Visual Studio и библиотеки.

Имплементацијата е достапна во форма на алатка за конзола и библиотека. Заинтересираните можат да дознаат повеќе за користењето на второто во readme во складиштето на Github, врската на која ќе ја прикачам на крајот од објавата.

Како да се користи?

Внимателно. Сликите што се користат за пакување се избираат со пребарување со користење на регуларен израз во дадениот root директориум. По завршувањето, датотеките може да се преместуваат, преименуваат и копираат по желба во нејзините граници, да се менуваат датотеките и оперативните системи итн. Сепак, треба да бидете исклучително внимателни и да не ја менувате непосредната содржина на кој било начин. Губењето на вредноста дури и на еден бит може да го оневозможи враќањето на информациите.

По завршувањето, алатката остава посебна архивска датотека која ги содржи сите информации потребни за распакување, вклучувајќи податоци за употребените слики. Сам по себе, тежи околу неколку килобајти и нема значајно влијание врз окупираниот простор на дискот.

Може да го анализирате можниот капацитет користејќи го знамето „-a“: „./f5ar -a [папка за пребарување] [Перл-компатибилен регуларен израз]“. Пакувањето се врши со наредбата './f5ar -p [папка за пребарување] [Перл-компатибилен регуларен израз] [спакувана датотека] [име на архива]' и отпакување со './f5ar -u [архивска датотека] [име на обновено датотека ]'.

Демонстрација на работа

За да ја покажам ефективноста на методот, поставив колекција од 225 апсолутно бесплатни фотографии од кучиња од услугата Unsplash а во документите најде голем pdf од 45 метри од вториот том Уметност на програмирање Кнута.

Редоследот е прилично едноставен:

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

Слики од екранот за обожавателите

Неотпакуваната датотека може и сè уште треба да се чита:

Како што можете да видите, од оригиналните 633 + 36 == 669 мегабајти податоци на хард дискот, дојдовме до попријатни 551. Ваквата радикална разлика се објаснува со намалувањето на вредностите на коефициентите, што влијае на нивната последователна компресија без загуби: намалувањето еден по еден лесно може да „отсече неколку бајти од конечната датотека. Сепак, ова е сепак загуба на податоци, иако екстремно мала, што ќе мора да ја поднесете.

За среќа, тие се апсолутно невидливи за око. Под спојлерот (бидејќи складиштето не може да ракува со големи датотеки), читателот може да ја процени разликата и со око и со нивниот интензитет, добиени со одземање на вредностите на променетата компонента од оригиналот: оригиналот, со информации внатре, разлика (колку е поматна бојата, толку е помала разликата во блокот).

Наместо заклучок

Имајќи ги предвид сите овие тешкотии, купувањето хард диск или поставувањето сè на облакот може да изгледа како многу поедноставно решение за проблемот. Но, иако сега живееме во толку прекрасно време, нема гаранции дека утре сè уште ќе биде можно да се вклучите онлајн и некаде да ги поставите сите ваши дополнителни податоци. Или оди до продавница и купи си уште илјада терабајти хард диск. Но, секогаш можете да ги користите постоечките куќи.

-> GitHub

Извор: www.habr.com