Комп'ютерне моделювання та дизайн
У сучасному інформаційному суспільстві світі, що стрімко розвивається, досить гостро стоїть питання збереження і передачі інформації. Незважаючи на безперервно зростаючий накопичувальний обсяг інформаційних носіїв, деколи потрібно зберегти велику кількість даних у сховищі невеликої ємності.
Надмірність даних часто пов'язана з якістю інформації. Вона покращує зрозумілість і сприйняття інформації. Однак, при зберіганні і передачі інформації засобами комп'ютерної техніки, надмірність може призвести до зростання вартості зберігання та передачі інформації. Особливо актуальною ця проблема постає в разі обробки величезних обсягів інформації при незначних обсягах носіїв даних. У зв'язку з цим, постійно виникає проблема зменшення надмірності або стиснення даних.
Стиснутий (упакований) файл називається архівом. Процес запису файлу в архівний файл називається архівуванням (упаковкою, стисненням), а витяг файлу з архіву - розархівування (розпакуванням). Архівація інформації - це таке перетворення інформації, при якому обсяг інформації зменшується, а кількість інформації залишається колишньою [1].
Сьогодні архіватори використовуються переважно для викладання даних у Мережу. Більшість драйверів на сайтах виробників викладаються саме в архівах, і велика частина програм на різних ресурсах також заархівовані. До речі, і сам користувач перш ніж викласти будь які дані в Мережу (наприклад, на файлообмінні ресурси), запаковує дані в архів [2]
Більшість цифрових даних зберігаються в двійкових (бінарних) файлах. Чисті текстові файли зустрічаються досить рідко (ймовірно, менше 2% даних у світі). Є кілька причин, за якими використовуються бінарні файли:
1. Введення і виведення набагато швидше при використанні двійкових даних. Перетворення 32-розрядного цілого числа в символи займає деякий час. Не так багато часу, але якщо файл (наприклад, файл зображення) містить мільйони чисел, накопичений час перетворення є значним. Комп'ютерні ігри сповільнювалися б, якби їх дані зберігалися у вигляді символів.
2. Бінарний файл зазвичай набагато менше текстового файлу, який містить еквівалентну кількість даних. Для зображень, відео та аудіо даних це важливо. Невеликі файли економлять місце на диску, вони можуть швидше передаватися і оброблятися швидше. Введення / виведення з меншими файлами також відбувається швидше, оскільки потрібно менше байтів для переміщення.
3. Майже ніколи людина не збирається дивитися на окремі зразки даних, тому немає ніяких підстав робити їх легкими для читання. Наприклад, люди дивляться на всю картинку GIF-файлу і мало цікавляться переглядом окремих пікселів у вигляді чисел. Іноді програміст або вчений повинен зробити це, можливо, для налагодження або наукових вимірювань. Але в цих особливих випадках можна використовувати шістнадцяткові дампи або інші спеціалізовані програми [3].
Тому саме бінарні дані були обрані для роботи в розробці цього програмного засобу.
При експлуатації ПК можлива втрата інформації з найрізноманітніших причин: через фізичне псування диска, неправильного коригування або випадкового видалення файлу, руйнування інформації вірусом і т.д. Щоб зменшити шкідливі наслідки таких ситуацій, потрібно мати копії файлів. Засоби резервного копіювання, що надаються операційною системою і програмами-оболонками для зберігання інформації, вимагають великих обсягів зовнішньої пам'яті. Більш зручно для створення архівних файлів використовувати спеціальні програми, що стискають інформацію [4].
Стиснення - це спосіб кодування цифрових даних так, щоб вони займали менший обсяг пам'яті. Для стиснення даних використовуються методи двох типів - з втратою і без втрати даних. Методики з втратою даних дозволяють стиснути файл, але деякі дані при цьому втрачаються безповоротно. А методи стиснення без втрати даних стискають інформацію, не спотворюючи її і нічого не втрачаючи під час цього процесу. Після відновлення оригінальний документ ідентичний вихідному з точністю до біта [5]. Тому при роботі з бінарними даними потрібно використовувати саме методи стиснення без втрати даних. Одними з таких є алгоритми стиснення зображень, які будуть використовуватися у даній роботі.
Метою роботи є розробка методу стиснення бінарних даних на основі методів стиснення зображень.
У процесі роботи необхідно виконати наступні завдання:
Результатом роботи є розроблені метод і програмний засіб для архівації даних на основі відомих алгоритмів стиснення зображень.
Внаслідок зростаючих обсягів оброблюваної і зберігаємої інформації особливого значення набуває архівація даних з їх стисненням.
Завдання ефективного стиснення даних завжди було однією з найактуальніших в інформатиці, а з розвитком комп'ютерної, цифрової техніки та Інтернет вона набула ще більшого значення.
Методи стиснення даних мають досить довгу історію розвитку, яка почалася задовго до появи першого комп'ютера [6]. Вже існує чимало стандартизованих методів стиснення [7], але потреба у появі нових і поліпшених методах залишається до сих пір.
У статті [8] Салауддін М. запропонував новий метод стиснення для загальних даних, заснований на логічній таблиці істинності. Послідовність вхідних даних перевіряється там, де вона парна або непарна. Якщо послідовність непарна, тоді додається біт, 0 або 1, залежно від останнього біта, а якщо парна, тоді цей крок пропускається. Якщо останній біт вхідної послідовності дорівнює 0, тоді додається 0, а якщо дорівнює 1, то додається 1. Потім бінарні дані представляються одним бітом на підставі запропонованої таблиці істинності. Таким чином, здійснюється стискання даних.
Нестандартно до стиснення інформації підійшли Сатеш Р. , Мохан Р.,Партасараті P. в статті [9], в якій описано алгоритм приховування одного зображення в іншому, в наслідок чого, зменшується в два рази кількість місця займаного зображеннями.
Павлов І.В. в своїй роботі [10] представляє розроблені різні варіанти алгоритмів пошуку співпадаючих послідовностей символів, що є попередньою процедурою для стиснення даних за допомогою алгоритму Лемпела - Зива. Запропоновані алгоритми, на відміну від відомих, засновані на використанні дерев цифрового пошуку, що призводить до низької критичності тимчасових витрат на пошук до довжини вихідної послідовності символів. Крім того, запропоновані алгоритми дозволяють вибирати оптимальний варіант алгоритму пошуку в залежності від наявних обчислювальних ресурсів. Розроблена модифікація алгоритму Лемпела - Зива забезпечує збільшення ступеня стиснення в порівнянні з відомими його варіантами на 10-40% в залежності від даних.
У роботах магістрів Донецького національного технічного університету також розглядалася тема архівації та стиснення даних:
Розробки програмних засобів архівації бінарних даних на основі алгоритмів стиснення зображень в роботах магістрів не було виявлено.
Архівація бінарних даних повинна бути заснована на алгоритмах стиснення зображень, тому для цього виконавчі файли, перед стисненням повинні бути представлені у вигляді растрових зображень. Особливістю растрового зображення є те, що воно як мозаїка складається з маленьких частин званих пікселями. Саме на такі частини потрібно розбити двійковий файл. Кожен піксель описується трійкою чисел, відповідних базових складових в моделі представлення кольору RGB.
Колір в моделі RGВ представляється як сума трьох базових кольорів - червоного (Red), зеленого (Green) і синього (Blue), З перших букв англійських назв цих кольорів складено назву моделі. На рис. 1 показано, які кольори виходять при додаванні трьох базових.
Рисунок 1 – Комбінації базових кольорів моделі RGB [14]
Оскільки яскравість кожної з базових складових кольору може приймати тільки 256 цілочисельних значень, кожне значення можна уявити 8-розрядних двійковим числом (послідовністю з 8 нулів і одиниць) або, іншими словами, одним байтом. Таким чином, в моделі RGB інформація про кожного кольорі вимагає 3 байта [14].
Перетворені з виконуваного файлу пікселі необхідно зберегти в файлі, який використовує встановлений формат файлу растрового зображення і яким присвоєно ім'я з трьохлітерним розширенням .bmp. Встановлений формат файлу растрового зображення складається зі структури bitmapfileheader, за якою слідує структура bitmapinfoheader і масив структур rgbquad (також званий таблицею кольорів). Таблиця кольорів супроводжується другим масивом індексів в таблицю кольорів (фактичні дані растрового зображення).
У структурі bitmapfileheader ідентифікується файл, вказується розмір файлу в байтах і зміщення від першого байта у заголовку до першого байта даних растрового зображення. У структурі bitmapinfoheader визначається ширина і висота растрового зображення в пікселях; формат кольору (кількість колірних площин і колірних бітів на піксель) пристрою відображення, на якому була створена бітова карта; чи були дані растрового зображення стиснуті перед зберіганням і тип використовуваного стиснення; кількість байтів растрових даних; дозвіл пристрою відображення, на якому було створено растрове зображення; і кількість кольорів представлених в даних. Структури RGBQUAD задають яскравості значення RGB для кожного з кольорів в палітрі пристрої [15]
Щоб повністю перетворити перетворені з бінарного файлу пікселі в растрове зображення, його спочатку потрібно доповнити на початку заповненими структурами bitmapfileheader і bitmapinfoheader, які є необхідними для ідентифікації растрового зображення у форматі .bmp.
Після створення реєстрового зображення у форматі .bmp, воно конвертується в формат .png, що використовує метод стиснення Deflate, або в формат .pcx, в якому використовується RLE стиснення.
Процес архівації бінарних даних на основі алгоритмів стиснення даних представлений на рис. 2.
Рисунок 2 – Процес архівації / розархівації бінарних даних на основі алгоритмів стиснення зображень (анімація: 10 кадрів, 7 циклів, 52 кілобайт)
З не згасаючою швидкістю збільшення кількості інформації завдання архівації та стиснення даних залишається актуальною і їй цікавляться по всьому світу. Розробники пропонують свої нові рішення. Проте дослідження і розробка поліпшених методів стиснення триває.
В ході виконання роботи були визначені завдання, які повинні бути вирішені для успішної розробки програмного засобу для архівації, реалізація якого повинна надати поліпшений спосіб стиснення бінарних даних.
На момент написання даного реферату магістерська робота ще не завершена. Остаточне завершення: травень 2019 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.