Сжатие без потерь

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

В основе алгоритмов сжатия без потерь лежат несколько методов. Рассмотрим два наиболее распространённых из них.

Метод сжатия RLE (Run length encoding – кодирование с переменной длиной строки). При сжатии по методу RLE в каждой строке растра изображения оттискивается непрерывная последовательность пикселей одинакового цвета. После этого каждая такая последовательность заменяется дескриптором, содержащим информацию о номере описываемого цвета (значения базовых составляющих) и количестве пикселей данного цвета в цепочке. Алгоритм RLE даёт хорошие результаты при сжатии искусственно созданных или обработанных изображений, содержащих большие участки однородного цвета. При сжатии этим методом детализированных фотографий, содержащих большое количество мелких многоцветных фрагментов, вместо сокращения размера файла может произойти его увеличение. Этот метод обеспечивает коэффициент сжатия до 10:1 и полное восстановление исходной графической информации.

Метод сжатия LZW (Lempel-Ziv-Welch), названный по первым буквам фамилий его разработчиков, сначала осуществляет поиск одинаковых областей, узоров (называемых фразами) во всём файле. Выявленные повторяющиеся комбинации сводятся в перечень, где каждой уникальной последовательности (фразе) присваивается свой код (ключ) – число, занимающее в памяти меньше места, чем сама комбинация. Механизм сжатия заключается в том, что всякий раз вместо встреченной в растре «знакомой фразы» сохраняется только её ключ, при обращении к которому впоследствии произойдёт полное восстановление графической информации данного фрагмента.

Хотя процесс кодирования и распаковки происходит медленнее, чем с RLE-алгоритмом, описанный способ более эффективен при сжатии произвольных графических данных (фотографий и т. п.) и является в настоящее время наиболее распространённым методом неразрушающего сжатия.