pip install di_compression

Клас Huffman_Compression надає функції для стиснення та розпакування файлів за допомогою алгоритму кодування Хаффмана. Кодування Хаффмана - широко використовуваний алгоритм стиснення даних без втрат.

• Основні методи:

1. generate_code: генерує коди Хаффмана для всіх символів на основі наданого дерева Хаффмана.
2. encode: кодує вхідний текст за допомогою кодування Хаффмана і повертає закодовану послідовність бітів разом зі словником Хаффмана.
3. frequency: обчислює частоту всіх символів у вхідному тексті.
4. decode: декодує вхідну послідовність бітів, використовуючи наданий словник Хаффмана.
5. add_fictious_bins: додає фіктивні біти в кінець закодованих даних для вирівнювання байтів.
6. remove_fictious: видаляє фіктивні біти, додані під час стиснення.
7. dict_to_bytes і dict_from_bytes: перетворюють словники Хаффмана у байти і навпаки.
8. compress: стискає файл за допомогою кодування Хаффмана і записує стиснуті дані до нового файлу.
9. decompress: розпаковує файл, стиснутий за допомогою кодування Хаффмана, і записує розпаковані дані до нового файлу.
10. клас Node - використовується для створення дерева, і подальшого опрацювання.

Щоб стиснути файл, створіть екземпляр класу Huffman_Compression, а потім викличте метод compress, вказавши шлях до файлу як аргумент. У результаті буде створено стиснутий файл з розширенням ".huff". Щоб розпакувати стиснутий файл - викличте метод decompress, вказавши шлях до стиснутого файлу як аргумент. У результаті буде створено розпакований файл, до назви якого буде додано "_decoded". Стиснення: Обчислення частоти: Метод обчислює частоту кожного символу у вхідному тексті. Він повертає список пар символ-частота, відсортованих за частотою. Побудова дерева Хаффмана: нформація про частоту використовується для побудови дерева Хаффмана, де кожен листок представляє символ і його частоту, а кожна внутрішня вершина представляє об'єднане піддерево. Дерево будується знизу вгору шляхом багаторазового злиття двох вершин з найнижчими частотами, поки не залишиться корінь Генерація кодів Хаффмана:

Після того, як дерево Хаффмана побудовано, метод generate_code проходить по дереву, щоб призначити коди (двійкові представлення) кожному символу. Цей процес включає рекурсивний обхід дерева, присвоєння '0' лівим гілкам і '1' правим гілкам та збереження кодів у main_dict. Кодування тексту: Метод encode використовує згенеровані коди Хаффмана для кодування вхідного тексту. Він замінює кожен символ у тексті відповідним кодом Хаффмана, створюючи послідовність бітів, що представляє стиснуті дані. Корегування байтів: В кінець закодованих даних додаються фіктивні біти, якщо це необхідно. На початку ж вказується на кількість доданих фіктивних бітів. Запис у файл: Закодовані дані разом зі словником Хаффмана записуються до нового файлу. Словник конвертується у байти і записується перед закодованими даними.

Розширення:

Читання словника Хаффмана: Під час декомпресії першим кроком є читання словника Хаффмана зі стисненого файлу. Словник зберігається у вигляді байтів і відокремлюється від закодованих даних заздалегідь визначеним роздільником ('separ'). Декодування словника Хаффмана: Байти словника кодуються у словник, який зіставляє символи з їхніми кодами Хаффмана. Цей словник використовується для зворотного процесу кодування і відновлення оригінальних символів із закодованих даних. Декодування закодованих даних: Закодовані дані зчитуються з файлу і перетворюються назад у послідовність бітів. Фіктивні біти, якщо вони присутні - видаляються. Декодування символів: Використовуючи словник Хаффмана, послідовність бітів декодується назад у вихідні символи. Коди зіставляються з відповідними символами, і вихідний текст відновлюється. Запис декомпресованих даних у файл: Розпакований текст записується до нового файлу з додаванням "_decoded" до початкового імені файлу.

Стиснення досягається шляхом заміни символів, що часто зустрічаються, коротшими кодами, а символів, що рідше зустрічаються - довшими кодами. Цей метод стиснення дозволяє значно зменшити розмір файлу, зберігаючи при цьому цілісність вихідних даних.

Застосування: Алгоритм LZW широко використовується для стиснення текстових файлів, зображень та інших типів даних. Він був реалізований у програмі compress, яка стала стандартною утилітою Unix-систем приблизно у 1986 році. Також він використовується у форматах файлів, таких як GIF і TIFF. encoding(data: bytes) -> list: Ця функція відповідає за кодування бінарних даних за допомогою алгоритму LZW. Вона ініціалізує словник з усіма можливими однобайтовими послідовностями, а потім проходить через вхідні дані, шукаючи вже існуючі послідовності в словнику. Якщо послідовність знайдена, вона продовжує додавати байти до послідовності (w). Якщо послідовність не знайдена, вона додається до словника, а попередня послідовність (w) записується у вихідний список.

decoding(code: list) -> bytes: Функція decoding робить зворотнє перетворення: вона перетворює список кодів назад у байти. Вона використовує словник кодування, який відновлюється під час декодування, і відтворює оригінальні дані, використовуючи інформацію зі списку кодів.

compress(path:str): Метод compress відкриває файл за вказаним шляхом, читає його вміст як бінарні дані, використовує метод encoding для стиснення даних, а потім записує стиснені дані у новий файл. Кожне стиснене значення записується як 3 байти, використовуючи маленьке порядкове число (little-endian).

decompress(path:str): Метод decompress відкриває стиснений файл, читає стиснені дані, декодує їх за допомогою методу decoding, а потім записує розпаковані дані у новий файл. Ім’я нового файлу формується шляхом додавання суфікса “_decoded” до оригінального імені файлу.

Можливі недоліки: Ступінь стиснення: Іноді LZW може мати гіршу степінь стиснення порівняно з іншими алгоритмами, такими як LZ77. Переповнення словника: При великій кількості унікальних послідовностей словник може швидко заповнитися, що може призвести до зниження ефективності стиснення. Патенти: Раніше існували патентні обмеження на використання LZW, що могло ускладнювати його застосування. Чому ці недоліки важливі: Недоліки важливі, оскільки вони впливають на вибір алгоритму стиснення для конкретних завдань. Наприклад, якщо потрібно стиснути великий об’єм даних з багатьма унікальними послідовностями, алгоритм LZW може не бути найкращим вибором через ризик переповнення словника і зниження степеня стиснення.

Основна мета алгоритму стиснення даних Deflate полягає в зменшенні обсягу даних шляхом видалення зайвої інформації та заміни символів бітовими кодами, які використовують менше місця. Це робиться за допомогою двох основних методів стиснення: алгоритму Гаффмана і алгоритму LZ77. Алгоритм Гаффмана: (більше описано зверху) Алгоритм Гаффмана використовується для створення оптимального префіксного коду для символів вихідних даних. Кожен символ замінюється унікальним бінарним кодом, який коротший для часто зустрічаючихся символів і довший для рідкісних. Це дозволяє зменшити кількість біт, необхідних для представлення даних, і відповідно зменшує загальний обсяг даних.

Опис роботи алгоритму:

Алгоритм LZ77 використовує скользящее вікно для пошуку найкращого збігу між певним відрізком даних і попередніми даними. Він кодує дані шляхом збереження зміщення (offset) та довжини (length) найкращого збігу, а також наступного символу, який не збігається. Пояснення етапів алгоритму: Пошук найкращого збігу: Алгоритм переглядає дані у скользящему вікні та знаходить найкращий збіг між поточним відрізком даних і вже закодованими даними. Найкращий збіг - це найдовший збіг, який зустрічається у відомих даних, знаходиться найдалі від поточного місця та має найменший зсув (offset). Кодування даних: Після знаходження найкращого збігу, алгоритм кодує цей збіг, використовуючи зсув (offset) та довжину (length) збігу, а також наступний символ, який не збігається. Приклад застосування алгоритму до текстового рядка: Нехай ми маємо текстовий рядок "abracadabra": Пошук найкращого збігу: Починаємо з порожнього вікна та додаємо кожен символ тексту в вікно по черзі. Коли додається новий символ, алгоритм шукає найкращий збіг між цим символом і попередніми даними у вікні. Найкращий збіг - це найдовший рядок, який вже зустрічався у вікні та починається найдалі від поточного місця. Наприклад, якщо у нас є вікно "abrac", алгоритм знайде збіг "abra" з символами, які йдуть після нього. Кодування даних: Після знаходження найкращого збігу, алгоритм кодує цей збіг, використовуючи зсув (offset) та довжину (length) збігу, а також наступний символ, який не збігається. Наприклад, якщо ми знаходимо збіг "abra" з зсувом 1 та довжиною 4, наступним символом буде "c". Отже, алгоритм LZ77 дозволяє стиснути дані шляхом виявлення та кодування збігів у вхідних даних. Коли обидва ці методи комбінуються в алгоритмі Deflate, вони працюють разом, щоб максимально зменшити розмір даних, зберігаючи при цьому їхній зміст. Результатом роботи алгоритму є стислий потік даних, який може бути ефективно використаний для передачі або зберігання, зменшуючи при цьому вимоги до місця.

Опис роботи алгоритму: Алгоритм Deflate є комбінацією двох основних методів стиснення даних - алгоритму Гаффмана і алгоритму LZ77. Він використовує алгоритм Гаффмана для створення оптимального префіксного коду для стиснення даних, а потім кодує стислі дані за допомогою алгоритму LZ77. Пояснення етапів алгоритму: Застосування алгоритму Гаффмана до даних: Початкові дані спершу піддаються стисненню за допомогою алгоритму Гаффмана. Алгоритм Гаффмана використовується для створення оптимального префіксного коду, де більш часті символи мають коротші коди, що дозволяє зменшити загальний об'єм даних. Кодування стислого тексту за допомогою алгоритму LZ77: Отримані стислі дані за допомогою алгоритму Гаффмана подаються на вхід алгоритму LZ77. Алгоритм LZ77 використовує скользящее вікно для знаходження найкращих збігів у вхідних даних та кодує їх, використовуючи зсув (offset) та довжину (length) збігу, а також наступний символ, який не збігається. Приклад застосування алгоритму Deflate до текстового рядка: Нехай у нас є текстовий рядок "abracadabra". Після застосування алгоритму Гаффмана до цього рядка отримаємо оптимальні коди для кожного символу: 'a' - 0, 'b' - 10, 'r' - 110, 'c' - 1110, 'd' - 1111. Потім ці стислі дані кодуються за допомогою алгоритму LZ77, де знайдені збіги кодуються зсувом (offset) та довжиною (length) збігу, а також наступним символом, який не збігається. Наприклад, збіг "abra" може бути закодований як (4, 1, 'c'). Таким чином, стислий текст буде складатися з послідовності таких кодів для кожного символу та збігу.

Припущення щодо збільшення розміру файлу після використання алгоритму Deflate: Додаткові метадані: Після стиснення даних алгоритмом Deflate можуть додаватися додаткові метадані, такі як заголовки або таблиці кодів, які необхідні для правильного декодування. Наприклад, це можуть бути інформація про структуру стислого файлу або таблиці частотності для алгоритму Гаффмана. Ці додаткові дані можуть займати додатковий обсяг файлу, особливо для невеликих файлів. Власне стислі дані: Хоча алгоритм Deflate в основному призначений для стиснення даних, існують випадки, коли стислі дані можуть займати більше місця, ніж вихідні дані. Це може статися, наприклад, коли дані мають випадковий або непередбачуваний характер, що ускладнює їх стиснення. Також може виникнути ситуація, коли стислі дані складаються з багатьох коротких збігів, що може призводити до збільшення розміру стислого файлу через додаткові метадані для кожного збігу. Несприятливі умови: Деякі типи даних можуть бути неідеальними для стиснення за допомогою алгоритму Deflate. Наприклад, вже стислі або випадкові дані можуть не мати достатнього об'єму для ефективного стиснення, або ж дані можуть містити багато унікальних символів, що складається з низької ступені стиснення. Параметри алгоритму: Неефективні параметри алгоритму, такі як розмір буфера в алгоритмі LZ77, також можуть впливати на розмір стислого файлу. Наприклад, великий розмір буфера може призводити до більшого збільшення розміру файлу після стиснення через більшу кількість додаткових метаданих для збереження збігів.

Клас LZ78 надає можливість стиснення та розпакування файлів за допомогою однойменного алгоритму. Алгоритм LZ78 є одним з методів стиснення даних без втрат та ефективний у стисканні послідовностей даних.

Основні методи класу: compress: Метод для стиснення вхідних даних з використанням алгоритму LZ78. Він шукає повторювані фрагменти даних та замінює їх кодами, що дозволяє зменшити обсяг даних. decompress: Метод для розпакування стиснених даних, використовуючи надані коди та відновлення оригінальних даних. Використання класу: Для стиснення файлу необхідно створити екземпляр класу LZ78 і викликати метод compress, вказавши шлях до файлу як аргумент. Результатом буде стиснутий файл з розширенням ".lz78", також функція поверне стиснутий вміст файлу в бінарному рядку. Для розпакування стиснутого файлу слід викликати метод decompress, також вказавши шлях до стиснутого файлу як аргумент. У результаті буде створено розпакований файл, до назви якого можна додати відповідне розширення.

В алгоритмі стиснення файли зчитуються бінарно, що дозволяє обробляти файли з різними розширеннями. Бінарне зчитування дозволяє читати дані з файлу без змін, у формі послідовності байтів, незалежно від їхнього типу або розширення. Це означає, що алгоритм може ефективно працювати з будь-яким типом файлу, як от текстовий файл, аудіофайл, відеофайл або будь-який інший файл, із збереженням його структури та інформації. Такий підхід робить алгоритм гнучким та універсальним для застосування до різноманітних видів даних і файлів.

Опис алгоритму стиснення: Побудова словника: Метод compress використовує словник для збереження повторюваних фрагментів даних та їх кодів. Заміна фрагментів кодами: Під час обробки вхідних даних, алгоритм шукає повторювані фрагменти та замінює їх кодами, що дозволяє ефективно зменшити обсяг даних. Запис стиснених даних: Стиснені дані разом із створеними кодами записуються до нового файлу з відповідним розширенням. Висновок: Стиснення файлів за допомогою алгоритму LZ78 дозволяє ефективно зменшити їх розмір, зберігаючи при цьому цілісність вихідних даних. Використовуючи клас LZ78, можна легко стиснути та розпакувати файли, що робить його корисним інструментом для оптимізації роботи з обсягами даних.