ВУЗ:
Составители:
Рубрика:
Характеристики арифметического сжатия: позволяет сжимать несколько сильнее, чем алгоритм Хаффмана, однако
работает медленнее за счёт необходимости выполнения арифметических операций с рациональными дробями.
Методы сжатия источников c памятью
Входную последовательность символов можно рассматривать как последовательность строк, содержащих произ-
вольное количество символов. Идея словарных методов состоит в замене строк символов на такие коды, что их можно
трактовать как индексы строк некоторого словаря.
Можно сказать, что мы пытаемся преобразовать исходную последовательность путём её представления в таком ал-
фавите, что его "буквы" являются фразами словаря, состоящими, в общем случае, из произвольного количества символов
входной последовательности.
Словарь – это набор таких фраз, которые, как мы полагаем, будут встречаться в обрабатываемой последовательно-
сти. Индексы фраз должны быть построены таким образом, чтобы в среднем их представление занимало меньше места,
чем требуют замещаемые строки. За счёт этого и происходит сжатие.
1. Классические алгоритмы Зива-Лемпела.
Алгоритмы словарного сжатия Зива-Лемпела появились во второй половине 1970-х годов. Это были так называемые
алгоритмы LZ77 и LZ78, разработанные совместно Зивом (Ziv) и Лемпелом (Lempel). В дальнейшем первоначальные
схемы подвергались множественным изменениям, в результате чего мы сегодня имеем десятки достаточно самостоятель-
ных алгоритмов и бессчётное количество модификаций.
LZ77 и LZ78 являются универсальными алгоритмами сжатия, в которых словарь формируется на основании уже об-
работанной части входного потока, т.е. адаптивно. Принципиальным отличием является лишь способ формирования
фраз. В модификациях первоначальных алгоритмов это свойство сохраняется. Поэтому словарные алгоритмы Зива-
Лемпела разделяют на два семейства: алгоритмы типа LZ77 и алгоритмы типа LZ78. Иногда также говорят о словарных
методах LZ1 и LZ2.
Если некий исследователь существенно изменял какой-то алгоритм, относимый к семейству LZ, то в названии полу-
ченной модификации к строчке "LZ" обычно дописывалась первая буква его фамилии, например: алгоритм LZB, автор
Белл (Bell).
Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977
году, но сам алгоритм разработан не позднее 1975 года.
LZ77 является "родоначальником" целого семейства словарных схем – так называемых алгоритмов со скользящим
словарем или скользящим окном. В LZ77 в качестве словаря используется блок уже закодированной последовательности.
Как правило, по мере выполнения обработки положение этого блока относительно начала последовательности постоянно
меняется, словарь "скользит" по входному потоку данных;
LZSS. Модификация LZ77 была предложена в 1982 году Сторером (Storer) и Жимански (Szymanski) Идея алгоритма
заключается в добавление к каждому указателю и символу однобитового префикса, позволяющего различать эти объек-
ты.
В потоке сжатых данных идёт либо пара <счётчик, смещение относительно текущей позиции>, либо просто <счёт-
чик> "пропускаемых" байт и сами значения байтов (как во втором варианте алгоритма RLE). При разархивации для пары
<счётчик, смещение> копируются <счётчик> байт из выходного массива, полученного в результате разархивации, на
<смещение> байт раньше, а <счётчик> (т.е. число равное счётчику) значений "пропускаемых" байт просто копируются в
выходной массив из входного потока.
LZW. Название алгоритм получил по первым буквам фамилий его разработчиков – Lempel, Ziv и Welch. Модифика-
ция LZ78. За счёт предварительного занесения в словарь всех символов алфавита входной последовательности результат
работы LZW состоит только из последовательности индексов фраз словаря. Из-за устранения необходимости регулярной
передачи одного символа в явном виде LZW обеспечивает лучшее сжатие, чем LZ78.
Таблица словаря для LZW состоит из 4096 строк.
Коды 256 и 257 являются служебными, 258…4095 содержат непосредственно сжимаемую
информацию.
Класс изображений LZW ориентирован на 8-битные изображения, построенные на ком-
пьютере. Сжимает за счёт одинаковых подцепочек в потоке.
Почти симметричен, при условии оптимальной реализации операции поиска строки в таб-
лице.
LZW реализован в форматах GIF и TIFF.
4.3.2. Алгоритмы сжатия изображений c потерями
На сегодняшний день существует три основных методики сжатия изображений с потеря-
ми:
1. Фрактальное преобразование.
2. Дискретно-косинусоидальное преобразование (DCT).
Страницы
- « первая
- ‹ предыдущая
- …
- 24
- 25
- 26
- 27
- 28
- …
- следующая ›
- последняя »
