Сжатие данных — это процесс уменьшения объема данных с целью экономии памяти или передачи по сети. Существует два типа сжатия данных:
- Сжатие без потерь (lossless): позволяет восстановить исходные данные без изменений после их декодирования.
- Сжатие с потерями (lossy): при декодировании восстанавливается не совсем точная копия исходных данных (например, для изображений или видео).
LZ77 — это алгоритм сжатия данных, который использует скользящее окно для поиска повторяющихся последовательностей символов и замены их ссылками на ранее встреченные фрагменты.
- Особенности: Работает с динамическими окнами. Применяет коды вида (сдвиг, длина), где сдвиг — это позиция начала повторяющейся строки, а длина — ее длина.
- Отличия: Предпочтительнее для файлов с большими блоками повторяющихся данных.
LZ78 — улучшение LZ77, где используется фиксированное окно и для каждого нового фрагмента создается новый индекс, который заменяет повторяющиеся фрагменты данных.
- Особенности: Меньше памяти и времени на поиск повторений.
- Отличия: Работает с фиксированными окнами и использует словарь для хранения повторяющихся фрагментов.
LZW (Lempel-Ziv-Welch) — улучшенная версия LZ78, которая использует кодирование с переменной длиной для создания более эффективных словарей.
- Особенности: Использует таблицу с уникальными индексами для каждого фрагмента данных.
- Отличия: Очень эффективен для текста и часто применяется в формате GIF.
RLE — один из самых простых алгоритмов сжатия, который заменяет длинные последовательности одинаковых символов на пару "символ-длина".
- Особенности: Очень эффективен для данных с длинными последовательностями одинаковых символов.
- Отличия: Простота и эффективность при сжатии изображений и текстов с длинными одинаковыми последовательностями.
Каждый из вышеперечисленных алгоритмов используется для сжатия текста. Однако эффективность сжатия зависит от структуры данных:
- RLE лучше работает с текстами, где часто повторяются одинаковые символы.
- LZ77 и LZ78 — эффективны для более сложных текстов с большим количеством повторений.
- LZW часто используется для сжатия текстов с разнообразием символов, таких как файлы GIF.
- Коды фиксированной длины: каждый символ или фрагмент данных кодируется одинаковым количеством бит (например, ASCII).
- Коды переменной длины: длина кода для каждого символа может быть разной и зависит от частоты его появления в данных (например, алгоритм Хаффмана).
Оптимальное кодовое дерево — это структура, используемая для хранения кодов переменной длины, где часто встречающиеся символы кодируются более короткими кодами, а редкие — более длинными.
- Префиксное дерево (или деревья Хаффмана) — это дерево, в котором код каждого символа является префиксом другого кода, то есть не существует кода, который является префиксом другого кода.
Алгоритм Шеннона-Фоно используется для построения оптимального кодового дерева для символов с известными вероятностями их появления.
- Шаги алгоритма:
- Сортируются символы по вероятности их появления.
- Разбиваются на две группы с минимальной разницей в вероятностях.
- Присваиваются коды для каждой из групп, и процесс повторяется до тех пор, пока не будет получено окончательное кодовое дерево.
Алгоритм Хаффмана — это один из самых эффективных алгоритмов сжатия данных с использованием кодов переменной длины.
- Шаги алгоритма:
- Для каждого символа вычисляется частота появления.
- Символы объединяются в пары с минимальной суммой частот, создавая двоичное дерево.
- Процесс продолжается до тех пор, пока не получится одно дерево, где каждый лист — это символ, а путь от корня до листа — его код.
- Подсчитываем частоту появления каждого символа в тексте.
- Строим дерево по алгоритму Хаффмана, объединяя символы с минимальной частотой.
- Присваиваем коды символам на основе дерева.
Для декодирования текста:
- Читаем код, начиная с корня дерева.
- При движении по дереву (влево или вправо) мы встречаем символы.
- Когда достигаем листа дерева, соответствующий символ выводится как результат.
- Процесс повторяется для всех кодов в зашифрованном сообщении.