Сжатие данных уменьшает размер файлов без потери информации. Это основа архиваторов, форматов PNG, ZIP, GZIP и множества сетевых протоколов. Среди классических подходов особенно важны Huffman и LZ77 — два алгоритма, которые решают задачу по-разному.
Huffman coding
Алгоритм Хаффмана строит для символов коды разной длины:
- частые символы получают короткие коды
- редкие — длинные
Пример: если в тексте буква “о” встречается часто, её код будет короче, чем у редкой буквы “щ”. За счёт этого средняя длина сообщения сокращается.
Плюсы Huffman:
- простая и эффективная идея
- хорошо работает на данных с неравномерной частотой символов
- используется в JPEG, DEFLATE и других форматах
Минусы:
- плохо сжимает данные, если символы встречаются примерно одинаково часто
- сам по себе не ищет повторяющиеся фрагменты строк
LZ77
Алгоритм LZ77 ищет повторы в потоке данных. Вместо повторной записи одинаковых фрагментов он сохраняет ссылку вида: (смещение, длина)
Например, если в тексте уже встречалась последовательность data, при повторе можно записать не сами символы, а указание, где они были раньше и сколько символов нужно взять.
Как работает LZ77:
- есть окно уже просмотренных данных
- алгоритм ищет в нём самое длинное совпадение
- если совпадение найдено — записывает ссылку
- если нет — сохраняет символ как есть
Плюсы LZ77:
- отлично работает на данных с повторами
- эффективен для текстов, логов, HTML, JSON, исходного кода
- лежит в основе ZIP, GZIP, PNG
Минусы:
- требует больше вычислений, чем простое кодирование символов
- эффективность зависит от размера окна и характера данных
Huffman vs LZ77: в чём разница
Huffman сжимает за счёт частоты символов.
LZ77 сжимает за счёт повторяющихся последовательностей.
На практике их часто комбинируют. Самый известный пример — DEFLATE:
- LZ77 находит повторы
- Huffman дополнительно кодирует результат более компактно
Именно поэтому архивы и сетевые форматы могут показывать высокую степень сжатия 🚀
Где это применяется
- ZIP и GZIP
- PNG
- HTTP-сжатие
- архиваторы и бэкапы
- передача данных по сети
Вывод:
Huffman и LZ77 — это фундаментальные алгоритмы сжатия данных. Первый лучше работает с распределением частот, второй — с повторяющимися фрагментами. Вместе они дают мощный результат, который до сих пор используется в современных IT-системах 🧠⚙️
📚 Ниже — подборка каналов про IT: разработка, архитектура, DevOps, безопасность и технологии без воды.