За странен метод за икономия на пространство на диска

Поредният потребител иска да запише нов набор от данни на твърдия диск, но му липсва свободно пространство за това. Не иска да изтрива нищо, защото всичко е много важно и необходимо. Какво можем да направим с него?

Тази проблема не е само негова. На нашите твърди дискове лежат терабайти информация, а количеството не намалява. Но колко уникална е тя? В крайна сметка, всички файлове са просто набори от битове с определена дължина и, вероятно, новият файл не се различава много от вече съхранявания.

Разбираемо е, че търсенето на вече съхранени части информация на твърдия диск е задача, която не е най-ефективната. От друга страна, ако разликата е малка, можем да се опитаме да я адаптираме...

TL;DR — втора опит да разкажа за странен метод за оптимизация на данни с помощта на JPEG файлове, сега в по-разбираема форма.

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

Ако вземем два напълно случайни набора данни, в тях в среден буй съвпадат половината от битовете. Наистина, сред възможните комбинации за всяка двойка ('00, 01, 10, 11') точно половината имат съвпадащи стойности, тук всичко е просто.

Но разбира се, ако просто вземем два файла и адаптираме единия към другия, ще загубим единия от тях. Ако обаче запазим измененията, просто ще пренаправим делта-кодиране, което съществува и без наше участие, макар и обикновено да не се използва за същите цели. Можем да се опитаме да вградим по-малка последователност в по-голяма, но дори и така рискуваме да загубим критични сегменти данни при необмислено използване с всичко.

Между какво и как можем да отстраняваме разликата? Тоест, записваният от потребителя нов файл е просто последователност от битове, с които сами по себе си не можем да направим нищо. Трябва просто да намерим на твърдия диск такива битове, които можем да променяме без нужда от съхраняване на разликата, така че да можем да понесем загубата им без сериозни последици. Освен това, има смисъл да променяме не само самия файл на ФС, но и някаква по-малко чувствителна информация в него. Но каква и как?

Методи за адаптиране

На помощ идват файлове, които са компресирани с загуби. Всички тези jpeg, mp3 и други, макар и да представляват компресия с загуби, съдържат куп битове, достъпни за безопасни промени. Могат да се използват напреднали техники, които незабелязано модифицират техните съставки на различни участъци от кодирането. Изчакайте. Напреднали техники… незабележима модификация… едни битове в други… да, това е почти. стеганография!

И наистина, вграждането на една информация в друга напомня на неговите методи. Впечатлява и незабележимостта на извършените промени за човешките сетива. Тук обаче пътищата се разделят — основната ни задача е да внесем допълнителна информация на твърдия диск на потребителя, което само ще му навреди. Може да забрави за това.

Затова, макар да можем да ги използваме, трябва да направим известни модификации. И ще обясня и покажа как да ги направим на примера на един от съществуващите методи и популярния формат на файлове.

За шакалите

Ако ще компресираме, то трябва да е най-компресируемото в света. Става въпрос, разбира се, за JPEG файловете. Освен това, съществува тон инструменти и методи за вграждане на данни в тях, те също така са най-популярният графичен формат на тази планета.

Въпреки това, за да не се занимаваме с кучета, трябва да ограничим работата си до файлове от този формат. Никой не обича едноцветните квадрати, които се появяват от прекомерно компресиране, затова трябва да ограничим дейността си до работа с вече компресиран файл, избягвайки повторното кодиране. По-конкретно — с цели коефициенти, които остават след операциите, свързани с загубата на данни — ДКП и квантоване, което е прекрасно показано на схемата за кодирането (благодаря на вики на националната библиотека на им. Бауман):

Съществуват много възможни методи за оптимизация на jpeg файловете. Има оптимизация без загуби (jpegtran), има оптимизация "без загуби" които наистина внасят известни промени, но нас не ни интересуват. Все пак, ако потребителят е готов да вгради една информация в друга с цел да увеличи свободното пространство на диска, то той най-вероятно или отдавна е оптимизирал изображенията си, или изобщо не иска да го прави от страх от загуба на качество.

F5

При такива условия подхожда цял набор от алгоритми, с които можете да се запознаете. в тази добра презентация. Най-напредналият от тях е алгоритъм F5 по авторство на Андреас Вестфелд, работещ с коефициенти на компонентите на яркостта, тъй като човешкото око е най-малко чувствително именно към техните промени. Освен това, той използва метод за вграждане, който е основан на кодиране на матрици, благодарение на което позволява да се извършват толкова по-малко изменения при вграждане на същото количество информация, колкото по-голям е размерът на използвания контейнер.

Самите промени се свеждат до намаляване на абсолютната стойност на коефициентите с единица при определени условия (т.е. не винаги), което позволява да се използва F5 за оптимизация на съхранението на данни на твърдия диск. Дело е в това, че коефициентът след такава промяна вероятно ще заема по-малко битове след извършване на кодиране с Хъфман поради статистическото разпределение на стойностите в JPEG, а новите нули ще дадат предимство при кодиране с RLE.

Необходимите модификации се свеждат до премахване на частта, отговаряща за секретността (паролната перестановка), която позволява да се спестят ресурси и време за изпълнение, и добавяне на механизъм за работа с множество файлове вместо един по един. По-подробно за процеса на промяна на читателя едва ли ще бъде интересно, затова преминаваме към описанието на изпълнението.

Високи технологии

За демонстрация на работата на такъв подход реализирах метод на чист Си и проведох редица оптимизации както по скорост на изпълнение, така и по памет (не можете да си представите колко тези картинчета тежат без компресия дори до DCT). Крос-платформеността е постигната чрез използване на комбинация от библиотеки. libjpeg, pcre и tinydir, за което им благодаря. Всичко това се събира с „make“, така че потребителите на Windows за оценка биха искали да инсталират Cygwin или да се научат да работят със Visual Studio и библиотеките сами.

Реализацията е налична под формата на конзолна утилита и библиотека. По-подробно за използването на последната желаещите могат да се запознаят с ръководството в репозитория в GitHub, линк към който ще приложа в края на поста.

Как да използвате?

С внимание. Изображенията, използвани за опаковане, се избират с търсене по регулярни изрази в зададената коренова директория. След завършване файловете могат да се преместват, преименуват и копират по желание в нейните рамки, да се променят файловите и операционните системи и др. Обаче, трябва да бъдете изключително внимателни и да не променяте непосредственото съдържание. Загубата на стойността дори на един бит може да доведе до невъзможност за възстановяване на информацията.

След приключване на работата утилитата оставя специален архивен файл, съдържащ цялата необходима информация за разопаковане, включително данни за използваните изображения. Той сам по себе си тежи около два килобайта и не оказва сериозно влияние върху заето дисково пространство.

Може да се анализира възможната вместимост с помощта на флага ‘-a’: ‘. /f5ar -a [папка за търсене] [Perl-съвместимо регулярното изражение]’. Опаковането се извършва с командата ‘. /f5ar -p [папка за търсене] [Perl-съвместимо регулярното изражение] [опакования файл] [името на архива]’, а разопаковането - с помощта на ‘. /f5ar -u [архивен файл] [име на възстановения файл]’.

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

За да покажа ефективността на метода, качих колекция от 225 напълно безплатни снимки на кучета от услугата Unsplash и намерих в документите голяма pdf-книга с 45 метра втори том Изкуства на програмирането Кнут.

Последователността е доста проста:

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

$ . /f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Четене на компресирания файл... ок
Инициализиране на архива... ок
Анализ на капацитета на библиотеката... завърши за 17.0s
Открит някакъв гарантиран капацитет от 48439359 байта
Открит възможен капацитет до 102618787 байта
Компресиране... завърши за 39.4s
Запис на архива... ок

$ . /f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Инициализиране на архива... ок
Четене на архивния файл... ок
Пълнене на архива с файлове... завърши за 1.4s
Разкомпресиране... завърши за 21.0s
Записване на извлечените данни... ок

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

$ du -sh dogs/
551M dogs/

Екранни снимки за любители

Разопакованият файл все още може и трябва да се чете:

Както се вижда, от първоначалните 633 + 36 == 669 мегабайта данни на твърдия диск стигнахме до по-приятните 551. Тази радикална разлика се обяснява с намаляването на стойностите на коефициентите, влияещи на последващото им компресиране без загуби: намаляване само с единица може спокойно да 'отреже' няколко байта от крайния файл. Въпреки това, все пак става въпрос за загуба на данни, макар и крайно малки, с които ще трябва да се примирим.

За щастие, за окото те не са абсолютно забележими. Под спойлера (тъй като habrastorage не поддържа големи файлове) читателят може да оцени разликата както с окото, така и интензивността ѝ, получена чрез изваждане на стойностите на изменената компонента от оригиналната: оригинал, с информацията вътре, разлика (колкото по-блед е цветът, толкова по-малка е разликата в блока).

Вместо заключение

Виждайки всички тези трудности, купуването на твърд диск или качването на всичките данни в облака може да изглежда много по-просто решение на проблема. Но макар да живеем в такова прекрасно време, няма гаранции, че утре все още ще можем да се свържем с интернет и да качим всичките си излишни данни някъде. Или да отидем в магазина и да си купим нов твърд диск от хиляда терабайта. Но използването на вече наличните у дома винаги е възможно.

-> GitHub

Източник: habr.com