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

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

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

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

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

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

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

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

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

Методи за подгонване

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

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

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

За шакалите

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

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

Съществуват множество възможни методи за оптимизация на 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\/\n44M knuth.pdf\n633M dogs\/\n\n$ .\/f5ar -p dogs\/ .*jpg knuth.pdf dogs.f5ar\nЧтение файла сжатия... готово\nИнициализация архива... готово\nАнализ емкости библиотеки... завершено за 17.0 секунд\nОбнаруженная достаточно гарантированная емкость 48439359 байт\nОбнаруженная возможная емкость до 102618787 байт\nСжатие... завершено за 39.4 секунды\nСохранение архива... готово\n\n$ .\/f5ar -u dogs\/dogs.f5ar knuth_unpacked.pdf\nИнициализация архива... готово\nЧтение файла архива... готово\nЗаполнение архива файлами... завершено за 1.4 секунды\nДекомпрессия... завершена за 21.0 секунду\nЗапись извлеченных данных... готово\n\n$ sha1sum knuth.pdf knuth_unpacked.pdf\n5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf\n5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf\n\n$ du -sh dogs\/\n551M dogs\/

Скриншоты для любителей

Распакованный файл все еще можно и нужно читать:

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

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

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

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

-> GitHub

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