Оптимізований спосіб стиснення даних на базі алгоритма Гаффмана
Вантажиться...
Дата
2022-12
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Актуальність теми. У епоху інформації людство змушено зберігати велику кількість інформації через постійне її накопичення, що є великою проблемою через обмеженість пам’яті у наших девайсах. Наразі кількість файлів може бути не великою, але роздільна здатність зображень, відео зумовлює дороговартісне зберігання, передачу інформації через мережі. Найбільш популярним є алгоритм Гаффмана, шо використовує техніку без втрат, тобто відбувається повне відновлення файлу до його першопочаткового вигляду після декодування. Стиснення даних також використовується для зберігання даних при резервному копіюванні, архівуванні, видаленні надлишковості.
Об’єктом дослідження є вивчення принципів роботи з даними та ознайомлення з жадібним алгоритмом Гаффмана.
Предметом дослідження оптимізація алгоритму Гаффмана у пам’яті, що в результаті призводять до його пришвидшення роботи.
Мета роботи: покращити використання пам’яті та часу роботи алгоритму за рахунок побудови оптимального Н-дерево, що конструюється на вхідних ймовірностях зустрічі певних символів у вхідному файлі.
Наукова новизна: запропонований спосіб стиснення даних, що створений на базі алгоритму Гаффмана та модифікований за допомогою застосування лишнього біту через особливості людьскої мови та реалізації її у носіях, що збільшує швидкість обходження Н-дерева.
Практична цінність: алгоритм навіть сьогодні застосовується в стисненні відео, аудіо та звичайних зображень, а в даній роботі, цінність результатів полягає в тому, що запропоновані методи дають змогу зменшити використання пам’яті при передавані даних, як наслідок пришвидшити цей процес. При оцінці результатів ми отримали, що дерево Гаффмана для англійського тексту взятого з книги зменшилося близько від 40 до 52 відсотків в залежності від вхідних даних.
Апробація роботи. Основні положення та результати роботи представлені та обговорювались на XV науковій конференції магістрантів та аспірантів «Прикладна математика та комп’ютинг» ПМК-2022 (Київ, 16-18 листопада 2022 р.). Опублікована стаття на конференції «IX Міжнародна науково-технічна Internet-конференція «Сучасні методи, інформаційне, програмне та технічне забезпечення систем керування організаційно-технічними та технологічними комплексами» (Київ, 25 листопада 2022 р.).
Структура та обсяг роботи. Магістерська дисертація складається з
вступу, чотирьох розділів та висновків.
У вступі подано загальну інформацію щодо проблеми сучасного світу, обґрунтовано актуальність дослідження, сформульовано поставлені цілі та задачі, показано наукову новизну та практичну цінність роботи, наведено відомості про апробацію результатів і їхнє впровадження.
У першому розділі розглянута теорія існуючих алгоритмів стистення даних, проведений їх аналіз відносно вибраного методу.
У другому розділі проведений аналіз оцінок методів стиснення, описано алгоритм дослідження, визначені основні переваги та недоліки, наведена теоретична частина модифікації алгоритму Гаффмана.
У третьому розділі наведена архітертура програми побудованої для дослідження результатів вдосконалення алгоритму Гаффмана на мові С++/Qt, описані технології, які були використані під час створення програми.
У четвертому розділі проведений аналіз результатів застосування методу оптимізації пам’яті в наявному алгоритмі з оригінальним алгоритмом та іншими найбільш розповсюдженими алгоритмами.
У висновках представлені результати проведеної роботи.
Робота представлена на 80 аркушах, наведено 5 таблиць, прикріплено 44 рисунки та наявні посилання на список використаних літературних джерел.
Опис
Ключові слова
жадібний алгоритм Гаффмана, стиснення даних без втрат, Huffman's greedy algorithm, lossless data compression
Бібліографічний опис
Білоха, А. К. Оптимізований спосіб стиснення даних на базі алгоритма Гаффмана : магістерська дис. : 123 Комп'ютерна інженерія / Білоха Анна Кирилівна. – Київ, 2022. – 88 с.