Ще один користувач хоче записати на жорсткий диск новий шматок даних, але йому не вистачає вільного місця для цього. Видаляти теж нічого не хочеться, тому що "все дуже важливе і потрібне". І що нам із ним робити?
Така проблема постає в нього жодного. На наших жорстких дисках спочивають терабайти інформації, і ця кількість не прагне зменшуватись. Але як вона унікальна? Зрештою, адже всі файли це лише набори бітів певної довжини і, швидше за все, нова не сильно відрізняється від тієї, що вже зберігається.
Зрозуміло, що шукати шматки інформації, що вже зберігаються, на жорсткому диску — завдання якщо не провальне, то як мінімум не ефективне. З іншого боку, якщо різниця невелика, то можна трохи і підігнати…
TL;DR - друга спроба розповісти про дивний метод оптимізації даних за допомогою JPEG-файлів, тепер у більш зрозумілій формі.
Про біти та різницю
Якщо взяти два повністю випадкові шматки даних, то в них збігається в середньому половина бітів, що містяться. І справді, серед можливих розкладів для кожної пари ('00, 01, 10, 11') рівно половина має значення, що збігаються, тут все просто.
Але звичайно, якщо ми просто візьмемо два файли і підженемо один під другий, то ми втратимо один з них. Якщо ж зберігатимемо зміни, то просто винайдемо , Яке і без нас чудово існує, хоч і не використовується зазвичай з такою ж метою. Можна намагатися вбудувати меншу послідовність у більшу, але навіть так ризикуємо втратою критичних сегментів даних при необдуманому використанні з усім поспіль.
Між чим тоді можна різницю усувати? Ну, тобто записуваний користувачем новий файл - просто послідовність біт, з якою самої по собі ми нічого зробити не можемо. Тоді треба просто знайти на жорсткому диску такі біти, щоб їх можна було змінювати без необхідності зберігати різницю, щоб можна було пережити втрату без серйозних наслідків. Та й змінювати є сенс не просто сам файл на ФС, а якусь менш чутливу інформацію всередині нього. Але яку та як?
Методи припасування
На допомогу приходять файли, стиснуті із втратами. Всі ці jpeg, mp3 та інші хоч і є стисненням із втратами, містять купу біт, доступних для безпечної зміни. Можна використовувати просунуті техніки, які непомітним чином модифікують їх складові на різних ділянках кодування. Зачекайте. Просунуті техніки… непомітна модифікація… одні биті в інші… та це майже !
І справді, вбудовування однієї інформації в іншу як ні що нагадує її методи. Імпонує також непомітність здійснених змін для людських органів чуття. Ось у чому шляхи розходяться - так це в секретності: наше завдання зводиться до внесення користувачем на свій жорсткий диск додаткової інформації, йому тільки зашкодить. Забуде ще.
Тому ми хоч і можемо використовувати їх, потрібно провести деякі модифікації. І далі я розповім і покажу їх на прикладі одного з існуючих методів та поширеного формату файлів.
Про шакалів
Якщо вже стискати, то найстисніше у світі. Йдеться, звичайно ж, про JPEG-файли. Мало того, що існує тонна інструментарію та існуючих методів для вбудовування в нього даних, тому він є найпопулярнішим графічним форматом на цій планеті.
Проте, щоб не займатися собаківництвом, потрібно обмежити своє поле діяльності у файлах цього формату. Ніхто не любить однокольорові квадратики, що виникають через зайвий стиск, тому потрібно обмежитися роботою з вже стислим файлом, уникаючи перекодування. Конкретніше — з цілими коефіцієнтами, які й залишаються після операцій, які відповідають за втрати даних — ДКП та квантування, що чудово відображено на схемі кодування (дякую національної бібліотеки ім. Баумана):
Існує безліч можливих методів оптимізації jpeg-файлів. Є оптимізація без втрат (jpegtran), є оптимізація.«, які насправді ще якісь вносять, але нас вони не хвилюють. Адже якщо користувач готовий вбудовувати одну інформацію в іншу заради збільшення вільного місця на диску, то свої зображення або давно оптимізував, або зовсім цього робити не хоче через страх втрати якості.
F5
Під такі умови підходить ціла родина алгоритмів, з якими можна ознайомитися. . Найбільш просунутим є алгоритм за авторством Андреаса Вестфелда, що працює з коефіцієнтами компоненти яскравості, тому що людське око найменш чутливе саме до її змін. Більш того, він використовує методику вбудовування, засновану на кодуванні матриці, завдяки чому дозволяє здійснювати тим менше їх змін при вбудовуванні однієї і тієї ж кількості інформації, чим більше розмір контейнера, що використовується.
Самі зміни при цьому зводяться до зменшення абсолютного значення коефіцієнтів на одиницю в певних умовах (тобто не завжди), що дозволяє використовувати F5 для оптимізації зберігання даних на жорсткому диску. Справа в тому, що коефіцієнт після такої зміни, швидше за все, займатиме менше біт після проведення кодування Хаффмана через статистичний розподіл значень у JPEG, а нові нулі дадуть виграш при кодуванні їх за допомогою RLE.
Необхідні модифікації зводяться до усунення частини, що відповідає за секретність (парольної перестановки), яка дозволяє економити ресурси та час виконання, та додавання механізму роботи з безліччю файлів замість одного за раз. Більш детально процес зміни читачеві навряд чи буде цікавим, тому переходимо до опису реалізації.
Високі технології
Для демонстрації роботи такого підходу я реалізував метод на чистому Сі і провів ряд оптимізацій як за швидкістю виконання, так і по пам'яті (ви не уявляєте, скільки ці картинки важать без стиснення навіть до DCT). Крос-платформність досягнуто використанням комбінації бібліотек , и , за що їм дякую. Все це збирається 'make'ом, тому користувачі Windows для оцінки хочуть встановити собі якийсь Cygwin, або розбиратися з Visual Studio і бібліотеками самостійно.
Реалізація доступна у формі консольної утиліти та бібліотеки. Докладніше про використання останньої бажаючі можуть ознайомитись у рідмі у репозиторії на гітхабі, посилання на який я докладу наприкінці посту.
Як використовувати?
З обережністю. Використовувані для пакування зображення вибираються пошуком за регулярним виразом у заданій кореневій директорії. По завершенню файли можна переміщувати, перейменовувати і копіювати за бажанням у її межах, змінювати файлову та операційні системи та ін. Однак, варто бути вкрай акуратним і ніяк не змінювати безпосередній вміст. Втрата значення навіть одного біта може призвести до неможливості відновлення інформації.
Після завершення роботи утиліта залишає спеціальний файл архіву, що містить всю необхідну для розпакування інформацію, включаючи дані про використані зображення. Сам по собі він важить порядку кілобайт і хоч скільки істотного впливу на зайнятий дисковий простір не надає.
Можна аналізувати можливу місткість за допомогою прапора '-a': './f5ar -a [папка пошуку] [Perl-сумісний регулярний вираз]'. Упаковка виконується командою './f5ar -p [папка пошуку] [Perl-сумісний регулярний вираз] [упаковуваний файл] [ім'я архіву]', а розпакування за допомогою './f5ar -u [файл архіву] [ім'я відновленого файлу]' .
Демонстрація роботи
Щоб показати ефективність роботи методу, я завантажив колекцію із 225 абсолютно безкоштовних фотографій собак із сервісу і відкрив у документах велику 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 не вміє у великі файли) читач може оцінити різницю як на око, так і їх інтенсивність, отриману відніманням значень зміненої компоненти з оригінальної: , , (Чим тьмяніший колір, тим менша різниця в блоці).
Замість висновку
Дивлячись на всі ці складності, купити жорсткий диск або залити все в хмару може здатися більш простим вирішенням проблеми. Але хоч зараз ми і живемо в такий прекрасний час, немає жодних гарантій, що завтра все ще можна буде вийти в інтернет і залити кудись усі свої зайві дані. Або прийти до магазину та купити собі черговий жорсткий диск на тисячу терабайт. А ось використовувати вже лежачі будинки можна завжди.
->
Джерело: habr.com