Адаптивное, полу адаптивное и неадаптивное кодирование.

Неадаптивные кодировщики содержат статический словарь определенных подстрок, о которых известно, что они встречаются в данных достаточно часто (RLE). Адаптивный кодировщик предопределяет правила для сжимаемых данных. Адаптивные компрессоры не зависят от типов обрабатываемых данных, т.к строят свои словари полностью из поступивших данных, они не имеют предопределенного списка подстрок, а строят фразы динамически в процессе кодирования (LZW – кодирование). Полу адаптивное основано на применении обоих словарных методов кодирования. Полу адаптивный кодировщик работает в 2 прохода. В 1-ом он рассматривает все данные и строит свой словарь; во 2-ом выполняется собственно кодирование.

Сжатие с потерями и минимизацией потерь.

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

RLE-кодирование.

Это кодирование используется большинством растровых файловых форматов. Алгоритм RLE позволяет сжимать данные любых типов, независимо от содержащейся в них информации. Сама информация влияет лишь на полноту сжатия. Большинство алгоритмов RLE не достигают большой степени сжатия, но выполняются легко и быстро. RLE уменьшает физический размер повторяющихся строк символов и кодирует эти строки, которые в RLE называются группами, в двух байтах. Первый байт определяет количество символов в группе и называется счетчиком группы (группа может содержать от 1 до 256 символов); второй – содержит значения символов группы и называется значением группы. Если программа читает подряд несколько пикселей с одинаковым значением, она не записывает цветовое значение пикселей еще раз, а просто запоминает сколько пикселей с таким значением следует друг за другом. Новый пакет генерируется всякий раз, когда изменяется группа или когда количество символов в группе превышает максимальное значение счетчика. Для кодирования группы в RLE требуется 2 байта, поэтому группы из 1 символа займут в 2 раза больше памяти, чем незакодированные данные. Эффективность сжатия RLE зависит от типа данных изображения. Черно-белое кодируется с помощью RLE особенно хорошо, т.к. включает большие объемы непрерывных данных. Сложное изображение с большим количеством цветов с помощью RLE кодируется плохо. Групповое кодирование не является форматом файла, это метод кодирования, который может быть включен в некоторые графические форматы. Данные изображения кодируются последовательно, начиная с верхнего левого угла, затем слева направо по линиям развертки. Альтернативные схемы RLE позволяют записать данные по длине растра, т.е. по вертикали, либо кодировать фрагментами или загзагом по диагонали. Иногда говорят, что бывает RLE-кодирование с потерями – это когда отбрасываются в процессе кодирования младшие биты в каждом пикселе. RLE-кодировщик должен останавливаться в конце каждой строки развертки растровых данных. Построчное кодирование требует меньшего размера буфера и предотвращает проблему перекрестного кодирования. Перекрестное кодирование – слияние строк развертки, происходящее из-за того, что в процессе кодирования различие между строками исчезает. В RLE закодированную группу принято заканчивать в конце строки развертки. Программа-кодировщик помещает в закодированные данные маркер конца строки, чтобы программа-декодировщик могла распознать начало строки развертки. Маркер представляет собой уникальный пакет, который нельзя спутать с другими данными, имеет длину 1 байт. Также для определения в закодированных данных начала точек строки развертки используется таблица строк развертки. Она содержит по одному элементу для каждой строки развертки, а элемент содержит информацию о смещении каждой строки развертки от начала данных.

RLE-схемы битового, байтового и пиксельного уровней.

Различают алгоритмы группового кодирования по длине групп данных. RLE-схемы, применяемые для кодирования растровой графики, делятся на классы в зависимости от уровня обрабатываемых данных. Большинство форматов используют 3 класса: битовый, байтовый и пиксельный уровни. Битового уровня – кодируют в группы биты строк развертки, игнорируя при этом границы битов и слов. Используются только при обработке монохромных изображений, которые содержат достаточное количество битовых групп. RLE-схемы битового уровня кодируют в группы только до 128 битов, создавая из них однобайтовый пакет. 7 младших битов этого байта содержат счетчик группы, старшие – значения группы.

RLE-схемы битового уровня – кодируют в группы байтовые значения, игнорируя отдельные биты и границы слов в строке развертки. Простая такая схема кодирует группы байтов в двухбитовые пакеты. Один байт содержит счетчик, а второй – значение группы. Также применяется схема, которая позволяет хранить в потоке данных литералы, т.е. блоки незакодированных данных. 7 младших битов первого байта содержат счетчик, а самый старший – тип группы. Если самый старший бит установлен «1», то значит, группа закодирована. Если в «0», то он указывает на литеральную группу (т.е. на незакодированную группу), т.е. байты читаются напрямую из данных изображения. Счетчик содержит значения от 0 до 127, значения группы – от 0 до 255.

RLE-схемы пиксельного уровня – применяются тогда, когда для хранения одного пиксельного значения используется 2 или более байтов данных изображения. На пиксельном уровне биты игнорируются, а байты используются для идентификации пиксельного значения.

Пакеты вертикального повторения.

Некоторые RLE-схемы для повышения эффективности сжатия используют пакет повторения строк развертки или пакет вертикального повторения. Этот пакет не хранит реальных строк развертки, он содержит указатель на необходимость повторить предыдущую строку. Пакет вертикального повторения занимает всего 1 байт для счетчика группы, причем этот байт равен 0. Второй байт – на значение количества строк (значение повторений).

LZW-сжатие.

Этот метод сжатия без потерь применяется в различных форматах файлов: GIF, TIFF; включен в стандарт сжатия для модемов и язык ПостСкрипт (Post Script). Используется для сжатия текста и является основой архивирующих программ: PK ZIP и ARG. Алгоритм LZW позволяет работать с любым типом данных, обеспечивает быстрое сжатие и распаковку. Этот алгоритм основан на поиске шаблонов в изображении и сохранении их. Программа считывает значения пикселей и строит таблицы кодов, которые представляют повторяющиеся пиксельные узоры, найденные этой программой. Степень сжатия достигается 3:1 или 4:1. Хорошо сжимаются насыщенные узорами изображения, содержащие большие блоки однотонной окраски или повторяющиеся одинаковые значения цветовых элементов. Это алгоритм, как и RLE, не является форматом – он лишь включен в различные другие форматы файлов. LZW является полуадаптивным, т.к. строит словарь данных из входного потока, образцы данных идентифицируются в потоке данных и сопоставляются с записями из словаря. Если данные не представлены в словаре, то создается кодовая фраза, которая записывается как в словарь, так и в выходной поток сжатых данных. Т.к. фразы имеют меньший физический размер, чем исходные данные, то LZW считается сжатием. Декомпрессор работает в порядке, обратном кодированию. Преимущество LZW в том, что для него необязательно сохранять словарь для последующего декодирования. При сжатии текстовых файлов LZW инициализирует первые 256 записей символами ASCII как фразами, а затем ищет их повторения.