20). Физическое и логическое сжатие

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

Логичес сжатие выполн только на символьном или более высоком уровне.Основано на инф-ии,содерж в исх-х данных.Логичес сжатие не примен для данных изображ-ия.

Методы физического сжатия дел на 2 категории:1)сжатие всего файла 2)сжатие, включён в структуру файла.

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

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

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

Неадаптивная кодировка сод-т статический словарь примерно предопределённых подстрок,о кот-х известно,что они появл в часто кодируемых данных.

Адаптивная кодировка не сод-т предопределённых правил для сжимаемых данных. Адаптивные компрессоры,такие как LZN, не зависят от типов обраб-х данных.т.к. строят свои словари полностью из поступивших данных. Адаптив компрессоры настраив-ся на любой тип вводимых файлов, добиваясь при этом максимально возможной степени сжатия.

Полуадаптивная кодировка основана на применении обоих методов кодирования. Работает в два прохода:

1).при 1-ом проходе он работает,как адаптивный кодировщик,т.е. он просматривает все данные и строит свой словарь.2).при 2-ом заходе он работает,как неадаптив кодир-щик,выполняя кодир-ия на основе данных, полученных на 1-ом этапе.такой подход позволяет построить оптимальный словарь перед кодир-ем.

22). Групповое кодир-ие rle

Это алгоритм сжатия,кот поддержив-ся большин-ом растровых форматов.//сжатие ТТР,bpf и т.д.

Алгоритм RLE позволяет считать данные любых типов,невзирая на содержащ-ся в них инф-ию.Сама же инф-ия влияет на полноту сжатия. Большин-во алгоритмов RLE не достигают большой степени сжатия,но выполн-ся легко и быстро. RLE уменьшает физич-ий размер повторяющ-ся строк символов.Такие повтор-ся строки наз группами и обычно кодир-ся в 2-х байтах:

-1 байт определяет кол-во символов в группе и наз счётчиком группы. Закодир-ая группа может содер-ть от 1 до 128(или 256) символов,что запис-ся в счётчик,как кол-во символов-1.

-2 байт содержит значение симв-в в группе и наз значением группы.Если программа читает подряд несколько пикселей с одним значением,она не записывает цветовое значение ещё раз,а просто запоминает сколько пикселей с этим значением следует друг за другом.

Этот код,сгенерированный для представления строки,наз RLE-пакетом. Новый пакет генерир-ся снова,когда измерится группа или когда кол-во символов в группе превысит значение счётчика.Т.к. для кодир-ия группы RLE треб-ся как минимум два байта,то группы из одиночных символов займут в памяти больше места,если их закодировать искусственно.

//ABRACADABRA-11 символов. RLE:OAOBOROA….-22 символа.

Эффективность сжатия зав-ит от типа данных изображ-ия.Ч/б изображ кодир-ся очень хорошо этим способом.т.к. сод-т очень большие объёмы непрер-х данных.Для сложных изображ-ий с большим кол-вом цветов,групповое кодир-ие практически не примен-ся.Групповое кодир-ие не явл форматом файлов.Это метод кодир-ия,кот м.б. включён в некоторые графические форматы.

Варианты группового RLE-кодир-ия

Данные изображ-ия обычно кодир-ся последовательно.Растер кодир-ся,начиная с верхнего лев угла по оси Х слева направо к нижн правому углу. Альтернатив схемы позволяют записывать закодир-ые данные по высоте растора(т.е. по оси Y),а также кодируют растр зигзагом.

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

Программа-кодировщик помещает в закодированные данные маркер конца строки развёртки, чтобы программа-декодировщик могла распознать начало строки развертки. Этот маркер предст собой уникальный пакет, точно определённый спецификацией RLE. Обычно маркер конца строки развёртки им длину 1 байт. Преимущество построчного кодирования - программа легко воспроизводит любую часть изображения. Другим способом определения в блоке закодир-х данных начальных точек любой строки развертки является создание таблиц строк разверток TCR, содержащих по 1 элементу для любой строки, в этот элемент записана инф-я о смещении начала каждой строки развертки в файле.

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

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

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

Байтового уровня – эти схемы кодируют в группы одинаковые байтовые знчения, игнорируя при этом отдельные биты. RLE-сх байтового ур кодируют в 2-х байтовый пакет: 1-ый байт – счетчик группы(0-255)

2-ой байт – значение группы (0-255). Используемая схема 2х байтового кодирования, позволяет хранить в потоке данных как закодированные, так и не закодированные группы. Незакодированные группы – литералы. В этом случае 1-7 бит 1- го байта пакета содержит счетчик группы, а самый старший бит 1-го байта – тип группы: 1- закодированная группа, 0 – литеральная группа, т. е следующие байты должны читаться на прямую из закодированных данных изображения в количестве, указанном счетчиком группы +1.

Группа- указывает, сколько пикселей подряд будут считаны. RLE-сх байтового ур эффективны для данных изображения, кот хран-ся в виде 1 байта на пиксель.

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

1-ый байт – счетчик(0-255)

2-ой байт – пиксель1 го канала(0-255)

3-ий байт – пиксель 2го канала(0-255)

4-ый байт – пиксель 3 го канала(0-255)

Сущ-ют литеральные гр пиксельного уровня: для этого также как и в схемах байтового уровня используется старший бит 1 го байта. В RLE схемах пиксельного уровня счетчик содержит данные о количестве пикселей .

24). RLE-схемы с использованием флага.

RLE-пакет вертикального повторения

При таком способе кодир-ия для представления группы используется не 2 ,а 3 байта.

1-ый байт – флаг, значение которого указывает на то , что следующие 2 байта явл частью закодиров-ого пакета.

2-ой байт – счетчик группы

3-ий байт – значение группы

Значение флага д.б. заранее задано.

Если нет флага – незакодированная группа.

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

Недостатки:1).минимальный размер группы, пригодной для кодир-я увеличив до 4х байт. 2).если поток незакодированных данных содержит значения символов = флаговому значению, то этот символ д.б. закодирован в 3х байтовый пакет.

RLE-пакет вертикального повторения

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

25). LZW-сжатие

Этот метод сжатия без потерь применяется в различных форматах файлов: GIF, TIFF; включен в стандарт сжатия для модемов и язык Post Script. Используется для сжатия текста и является основой архивирующих программ: ZIP,ARG, COMPRESS. Был разработан в 1977 г., в 1984 был доработан и стал наз LZW.

Алгоритм LZW позволяет работать с любым типом данных, обеспечивает быстрое сжатие и распаковку. Этот алгоритм основан на поиске шаблонов в изображении и сохранении их. Программа считывает значения пикселей и строит таблицы кодов, которые представляют повторяющиеся пиксельные узоры, найденные этой программой. Степень сжатия достигается 3:1 или 4:1. Хорошо сжимаются насыщенные узорами изображения, содержащие большие блоки однотонной окраски или повторяющиеся одинаковые значения цветовых элементов. Этот алгоритм, как и RLE, не является форматом – он лишь включен в различные другие форматы файлов.

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