Алгоритм Лемпеля—Зива. LZW (Lemple-Zif-Welch)

Алгоритм сжатия данных, основанный на поиске и замене в исходном файле одинаковых последовательностей данных для их исключения и уменьшения размера "архива". В отличие от предыдущих рассмотренных методов сжатия, более "интеллектуально" просматривает сжимаемое cодержимое, а все ради большей степени сжатия данных.

Основан на сведении к минимальной избыточности. Вместо кодирования каждого символа кодируются часто встречающие последовательности символов (например, слова «который», «также»). Имена же собственные, встречающиеся один раз не кодируются.

Программа алгоритма просматривает файл с текстом или байтами графической информации и выполняет статистический анализ для построения кодовой таблицы.

Если заменить 60-70% текста символами, длина которых меньше половины от первоначальной, можно добиться сжатия %.

При применении этого алгоритма к загрузочным файлам (*.exe, *.com), результат — 10-20%, так как избыточность кода, создаваемого компиляторами меньше избыточности текста на естественном языке.

Файлы баз данных — тоже трудный случай, так как может содержать редко повторяющуюся информацию (имена, номера телефонов, адрес).

Графические контурные файлы архивируются хорошо, так как обладают большой избыточностью (фон).

Полутоновые и цветные изображения тоже можно архивировать, но с меньшим успехом.

Данный тип сжатия не вносит искажений в исходный графический файл и подходит для обработки растровых данных любого типа - монохромных, черно-белых или полноцветных. Наилучшие результаты получаются при компрессии изображений с большими областями одинакового цвета или изображений с повторяющимися одинаковыми структурами. Этот метод демонстнрирует самые поразительные результаты степени сжатия (среди других существующих методов сжатия графических данных) при полном отсутствии потерь или искажений в исходных файлах. Используется в файлах формата TIFF, PDF, GIF, PostScript (в инкапсулированных объектах) и других.

ZIP

Метод сжатия, аналогичный использующемуся в популярном алгоритме архивации PKZip. В основу ZIP положен метод, аналогичный LZW. Как и LZW, не вносит искажений в исходный файл и лучше всего подходит для обработки графических данных с одинаковыми одноцветными или повторяющимися областями. Используется в файлах формата PDF, TIFF и некоторых других.

Алгоритм RLE (Run Length Encoding) «сжатие последовательности одинаковых символов»

Изображение рассматривается как последовательность байтов. Одинаковые байты кодируются парой, 1-ый байт (count) — счетчик одинаковых байтов, 2-ой — байтом из кодируемой последовательности. Для отличия счетчика 2 его старших бита устанавливается равным 1. Это позволяет кодировать последовательности длиной не более 63. Байты изображения со значениями больше 191 кодируются 2 байтами.

RLE дает хороший результат для графических адаптеров с 1 или 2 бита на (CGA), либо при раздельном хранении цветовых плоскостей (EGA, VGA — 16-ти цветовые режимы). Степень сжатия зависит от графического адаптера и самого изображения («гладкие» картинки сжимаются сильнее). Для CGA и EGA коэффициент сжатия больше 2. RLE работает плохо для режима 8 бит/ .

Достоинства: простота, скорость декодирования.

Декодирование — для очередного байта В осуществляется проверка, установлены ли старшие биты не равными 0, если да, то байт является счетчиком, число повторений равно count (сбрасывается старшие биты). Следующий байт переписывается в видео память в Count экземплярах. Если старшие биты байта не установлены, то он переписывается в видеопамять без изменения.