Дослiдження методiв компресiї даних та створення власної програми-кодека

Під час роботи над цим комп'ютерним проєктом ми розглянули різні методи компресії даних, дослідили їх ефективність та написали програму-кодек для безпосереднього використання цих алгоритмів.

Реалізовані алгоритми

• Код Гаффмана (Huffman Coding) - алгоритм оптимального префіксного кодування з мінімальною надмірністю, реалізований на основі побудови дерева Хаффмана. Алгоритм закодовує певні послідовності, надаючи найбільш використовуваним послідовностям коди найменшої довжини, і навпаки.
• LZ77 - алгоритм стиснення даних без втрат, який шукає повторювані послідовності байтів у вже оброблених даних та замінює ці послідовності спеціальними посиланнями. Цей підхід базується на концепції "ковзного вікна" sliding window("ковзного вікна").
• LZ78 - алгоритм стиснення даних без втрат, який будує словник під час обробки вхідного потоку даних та зберігає побачені підрядки і замінює повторення посиланнями на словник.
• LZW - алгоритм стискає дані, замінюючи повторювані підрядки у вхідному потоці на індекси словника, який автоматично розширюється в процесі обробки.
• DEFLATE - алгоритм безвтратного стиснення даних, який поєднує два методи: LZ77 (для виявлення повторень) і Huffman-кодування (для кодування частих символів коротшими бітами).
  
• RLE - алгоритм безвтратного стиснення даних, який замінює повторювані символи на пару: (символ, кількість повторів). Додатково:
• DPCM - алгоритм написаний для роботи з .wav, який кодує не самі значення, а різницю між поточним і попереднім значенням сигналів.

Програма-кодек (UI)

Функції, реалізовані у програмі

• Вибір файлу: користувач обирає файл для стиснення. Якщо вибрано формат, який не підтримується, то виводиться повідомлення з інформацією про це.
• Вибір алгоритму: користувач може обрати, який алгоритм для компресії використовувати.
• Compress: натискаючи на цю кнопку, користувач запускає алгоритм компресування даних. Програма перевіряє чи попередньо обрано файл та повідомляє користувача, якщо це не так. Виводиться інформація про файл до компресії та після.
• Decompress: натискаючи на цю кнопку, користувач запускає алгоритм декомпресування даних. Програма перевіряє чи попередньо обрано файл та, чи компресованого його і повідомляє користувача, якщо це не так. Виводиться інформація про успішну декомпресію.

Структура проєкту

Exploration-of-data-compression-methods/
├── algorithms/              # Реалізація алгоритмів
├── test/         # Семпли для тестування алгоритмів
├── gui.py           # UI програми-кодека
└── testing_performance.ipynb      # Спостереження під час дослідження & тестування

Встановлення

1. Попередні налаштування Перед завантаженням рекомендуємо переглянути файл requirements.txt, у якому містяться усі необхідні бібліотеки та модулі, та встановити їх для ефективної роботи.

2. Клонування репозиторію:

   git clone https://github.com/Luzefik/Exploration-of-data-compression-methods.git
   cd Exploration-of-data-compression-methods
   

3. Запуск UI

   python3 gui.py # або python gui.py
   

Склад команди та розподіл обов'язків

• Андрій Кульбаба - реалізація LZ77, DEFLATE, DPCM
• Оксана Москв'як - реалізація Huffman Coding, програми-кодека(UI), README.
• Олександр Стаднік - реалізація LZW
• Олег Гуцуляк - реалізація LZ78, RLE

@Створено студентами УКУ в межах курсу "Дискретна математика 2"