В.Д. Валединский - Избранные главы лекций по программированию (1114957), страница 9
Текст из файла (страница 9)
4.5. Адаптивное арифметическое кодированиеАлгоритм адаптивного арифметического кодирования по принципам построения аналогичен адаптивномуметоду Хаффмана. Этот алгоритм можно описать следующим образом:1. Строится таблица частот для равномерного распределения (все отрезки разбиения имеют длину 1/256).2. Очередной отрезок разбиения выбирается по очередному входному символу на основании текущей таблицычастот.3. Таблица частот пересчитывается с учётом появления только что обработанного входного символа.4.
Продолжаем обработку по пунктам 2 — 4, пока есть входные символы.5. В окончательном отрезке разбиения выбираем кодирующую дробь.Адаптивное декодирование строится аналогично:1. Строится таблица частот для равномерного распределения (все отрезки разбиения имеют длину 1/256).222. Ищется очередной отрезок, содержащий кодирующую дробь, на основании текущей таблицы частот.
Выходной символ определяется по найденному отрезку.3. Таблица частот пересчитывается с учётом появления только что полученного выходного символа.4. Продолжаем обработку по пунктам 2 — 4, пока не исчерпается общее количество символов.Заметим, что данный алгоритм принципиально отличается от алгоритма Хаффмана, хотя оба они используют статистические таблицы частот входных символов. Если алгоритм Хаффмана строит оптимальный код, т.
е.старается минимизировать общую длину кода при фиксированном кодировании каждого отдельного байта, топри арифметическом кодировании строится кодирующая дробь для всего входного потока в целом. В частности,длина кода зависит от порядка следования байтов во входном потоке, в то время как код Хаффмана не зависитот порядка байтов.4.6. Алгоритм LZW (Lempel – Ziv – Welch)Различные модификации этого алгоритма используются в программах-архиваторах.Суть алгоритма состоит в обнаружении во входном потоке повторяющихся цепочек байтов, составлении таблицы таких обнаруженных цепочек и выдаче номеров строк таблицы, соответствующих обнаруженной цепочке,в выходной поток. Таким образом, если исходный файл имеет много повторяющихся последовательностей байтов, то каждая такая последовательность будет заменена на её порядковый номер в таблице.Важной особенностью алгоритма является то, что распаковщик, анализируя сжатые данные в процессе работы, строит копию исходной таблицы, и потому её не надо передавать вместе со сжатыми данными.4.6.1.
КодированиеСоздаётся таблица, способная вместить достаточно большое количество строк (в каноническом алгоритме —4096 строк). Первые 256 строк этой таблицы инициализируются всевозможными односимвольными цепочками(т. е. просто символами с кодами от 0 до 255). Дальнейший алгоритм выглядит так:S = "";while ((C = NextByte()) != EOI){if (InTable(S + C)) S += C;else{Out(Code(S));Add(S + C);S = C;}}Out(Code(S));// если цепочка S+C уже есть в таблице, удлиняем её// цепочки S+C нет в таблице// вывод кода, соответствующего цепочке S// добавляем новую цепочку S+C в таблицу// готовимся к обнаружению следующей цепочки// вывод кода для оставшейся цепочки SЗдесь знак «+» обозначает склейку цепочек, а функция Code(String) возвращает код цепочки String втаблице. Алгоритм кодирования каждый раз пытается найти в таблице наиболее длинную цепочку, соответствующую читаемой последовательности символов.
Если это в какой-то момент не удаётся, то накопленная кэтому времени цепочка заносится в таблицу.В какой-то момент может наступить переполнение таблицы. В этом случае кодировщик выводит в выходнойпоток специальный код очистки и таблица цепочек инициализируется заново. Обычно в реальных алгоритмахчисло 256 является кодом очистки (обозначим его CLC), а число 257 — кодом конца информации (EOI), поэтомуэти строки таблицы не используются для цепочек. Заметим, что в случае, когда таблица создаётся на 4096 цепочек, для каждого выходного кода достаточно 12 бит.
Поэтому при выводе целесообразно упаковывать каждыедва кода в три байта. Для упрощения логики декодера обычно первым кодом сжатых данных является CLC,что сразу вызывает инициализацию таблицы цепочек. Построенный здесь алгоритм декодирования используеткоды очистки и потому несовместим с приведённым выше кодировщиком.4.6.2. ДекодированиеРаспаковка сжатых данных основывается на построении идентичной таблицы цепочек. Инициализация таблицы выполняется так же, как и при кодировании.while ((K = NextCode()) != EOI){if (K == CLC){InitTable();if ((K = NextCode()) == EOI) break;Out(String(K));// пока не кончился поток кодов// K есть код очистки// заново инициализируем таблицу// читаем следующий код// выводим цепочку для кода K23}else{if (InTable(K)){Out(String(K));Add(String(Old) + FirstChar(K));}else{S = String(Old) + FirstChar(Old);Out(S);Add(S);}}Old = K;// в таблице есть строка для кода K// выводим цепочку для кода K// формируем и добавляем новую цепочку// в таблице нет строки для кода K// формируем цепочку// выводим цепочку// и добавляем ее в таблицу// запоминаем текущий код}В этом алгоритме функция String(Code) возвращает строку из таблицы, соответствующую коду Code, афункция FirstChar(Code) возвращает только первый символ такой строки.
Заметим, что функция NextCode()должна извлекать 12-битные коды из входного потока байтов.Степень сжатия этого алгоритма оценить непросто, однако здесь применим всё тот же вывод: сжатие будетхорошим, если входной поток байтов обладает свойствами повторяемости отдельных фрагментов. С другойстороны, можно предложить такую последовательность входных байтов, что почти все они будут кодироватьсяодносимвольными цепочками и алгоритм даст даже некоторый проигрыш в размере результата.Заметим, что кодировщик и декодер алгоритма LZW заполняют таблицу цепочек по одинаковым правилам.Если кодировщик обработал m входных байтов, а декодер раскодировал m выходных байтов, то они имеютодинаковые состояния таблиц цепочек. Этот факт позволяет еще немного улучшить степень сжатия алгоритма.Действительно, пока в таблице менее 512 цепочек, кодировщик может выдавать на выход 9-битные коды.Когда число зарегистрированных цепочек станет не меньше 512, но еще будет меньше 1024, кодировщик может перейти на 10-битные коды.
В диапазоне от 1024 до 2048 кодировщик выдает 11-битные коды, и толькопотом — 12-битные. Декодер сначала извлекает из входного потока 9-битные коды и аналогично переходит кболее длинным кодам по мере разрастания своей таблицы цепочек.В заключение заметим, что четыре рассмотренные примера алгоритмов сжатия используют различные подходы к определению информационной избыточности и различные методы для её сокращения. Поэтому с практической точки зрения оправдано последовательное применение нескольких различных алгоритмов сжатия.
Так,например, выходная кодовая последовательность алгоритма LZW может содержать много одинаковых кодов длянекоторой часто встречающейся цепочки входных символов. В этом случае можно сжать сам код некоторым алгоритмом, ориентированным на анализ частотных характеристик появления отдельных байтов (Хаффмана либоарифметического кодирования). Для больших черно-белых изображений можно сначала использовать алгоритмRLE, а затем какой-либо другой алгоритм.24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
