Алгоритми стиснення: опис, основні прийоми, характеристики
Алгоритм стиснення Хаффмана
Цей процес, який можна використовувати для “зменшення” або шифрування.
Він заснований на призначення кодів різної довжини бітів відповідному кожному повторюваного символу, чим більше таких повторів, тим вище ступінь стиснення. Щоб відновити вихідний файл, необхідно знати призначений код і його довжину в бітах. Аналогічним чином, використовують програму для шифрування файлів.
Порядок створення алгоритми стиснення даних:
Прораховують, скільки разів кожен символ повторюється у файлі для “зменшення”.
Створюють зв’язаний список з інформацією про символи і частотах.
Виконують сортування списку від найменшого до найбільшого в залежності від частоти.
Перетворять кожен елемент списку в дерево.
Об’єднують дерева в одну, при цьому перші два утворюють нове.
Додають частоти кожної гілки в новий елемент дерева.
Вставляють нове в потрібне місце в списку, відповідно до суми отриманих частот.
Призначають новий двійковий код кожного символу. Якщо береться нульова гілку, до коду додається нуль, а якщо перша гілка, додається одиниця.
Файл перекодовується у відповідності з новими кодами.
Наприклад характеристики алгоритмів стиснення для короткого тексту:”ata la jaca a la estaca”
Підраховують, скільки разів з’являється кожен символ і складають зв’язаний список:” (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
Замовляють по частоті від нижчої до вищої: e (1), j (1), s (1), c (2), l (2), t (2), ” (5), a (9)
Як видно, кореневий вузол дерева створений, далі призначаються коди.
І залишилося тільки упакувати біти в групи по вісім, тобто в байти:
