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

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

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

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

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

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

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

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

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

Методи за монтаж

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

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

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

Относно чакалите

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

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

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

F5

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

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

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

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

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

Внедряването е достъпно под формата на конзолна помощна програма и библиотека. Заинтересованите могат да научат повече за използването на последното в readme в хранилището на 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
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. Такава радикална разлика се обяснява с намаляването на стойностите на коефициентите, което се отразява на техните последващо компресиране без загуби: намаляването един по един може лесно да „отреже няколко байта от крайния файл. Това обаче все още е загуба на данни, макар и изключително малка, с която ще трябва да се примирите.

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

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

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

-> GitHub

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