Лекция 5. Комплексные методы сжатия без потерь
Курс “Теория информации и кодирования”

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

Подходы к созданию и оценке комплексных методов сжатия
Словарные методы сжатия. Семейство алгоритмов LZ*
Прогнозный метод сжатия. Алгоритм PPM
Сортировочный метод сжатия. Алгоритм bzip2

5.1 Подходы к созданию и оценке комплексных методов сжатия

Статистическое и контекстное сжатие
Современные методы сжатия сообщений без потерь информации стремятся использовать все важные закономерности, которые обычно существуют в сообщениях (рис.5.1):
  • статистические закономерности выражаются в различиях вероятностей знаков. Они характерны для большинства сообщений, то-есть, универсальны. Вторая универсальная категория закономерностей — связи между знаками в сообщениях (например, между буквами в словах): появление определенного знака зависит от его предыстории или, иначе говоря, от контекста. Комплексные методы сжатия учитывают как статистические, так и контекстные закономерности;
  • в существующих комплексных методах сжатия использование упомянутых закономерностей реализуется в два этапа: сначала выполняется контекстное сжатие (то-есть, кодирование цепочек соседних знаков), а затем — статистическое сжатие полученных на первом этапе данных;
  • контекстное сжатие обычно связано с некоторым обобщением характеристик исходных сообщений. Например, повторяющиеся слова можно компактно представить ссылками на них в предыдущем тексте. Каждая из таких ссылок может включать номер первой буквы слова в тексте и количество букв в слове. Теперь вместо громадного множества слов описание источника должно включать лишь числовые характеристики ссылок. Очевидно, что при этом оно значительно обобщается и упрощается. Такое обобщенное описание уместно назвать “информационной моделью источника”. Соответственно, этап контекстного сжатия часто называют также “моделированием источника”;
  • обобщающий характер контекстного сжатия очень важен для сжатия статистического. Если его непосредственное применение ограничивалось из-за разнообразия исходных алфавитов и статистик, то теперь широкий класс источников сообщений может успешно сжиматься одним статистическим кодером (например, статистические характеристики ссылок для текстов на разных европейских языках достаточно близки). Все это объясняет широкое распространение двухэтапной схемы комплексного сжатия сообщений.

Направления разработки комплексных методов
В современной практике используется несколько принципиально различных подходов к контекстному сжатию и, соответственно, к формированию комплексных методов (рис.5.2):
  • простейшим и очень распространенным (хотя и не универсальным в строгом смысле) является метод сжатия однородных цепочек знаков. Такой метод известен под названием «кодирование длин серий» run-length encoding (RLE). Он предполагает замену серии одинаковых знаков парой <знак, число повторений>. В дальнейшем для значений счетчиков повторов может выполняться статистическое сжатие, хотя на практике такое решение используется нечасто. Разумеется, применение данного подхода ограничено сообщениями, где однородные цепочки встречаются часто (как в факсах или файлах некоторых графических форматов). Однако, он широко используется также в качесте вспомогательного (например, для обработки результатов моделирования источников). ;
  • среди универсальных подходов, пригодных для любых типов сообщений, наибольшее распространение получил так называемый «словарный» метод. Он основан на замене ранее встречавшихся цепочек знаков, - например, слов, - короткими ссылками на их предшественников в уже обработанной части текста (мы упоминали данный подход выше). Cуществует большое разнообразие способов поиска повторяющихся цепочек, которые применяются в многочисленных версиях метода. Сатистическое сжатие здесь может выполняться для числовых параметров ссылок. Метод предложен Лемпелем и Зивом и потому в обозначениях различных его версий в качестве префикса используются буквы LZ;
  • еще одно направление часто называют «прогнозным». Здесь модель источника включает набор повторяющихся цепочек знаков с данными о количестве повторений (в общем случае отдельный знак тоже рассматривается как элементарная цепочка). Для эффективного статистического сжатия метод предусматривает прогнозирование вероятностей появления разных знаков в каждой следующей позиции и постоянную корректировку кодовой таблицы исходя из меняющегося прогноза. Метод обычно обозначают аббревиатурой PPM - Prediction by Partial Matching — предсказание по частичному совпадению;
  • последнее направление, которое принято называть “сортировочным” или “блочно-сортирующим”, предусматривает обработку блоков данных сообщения. Благодаря специальному преобразованию, предложенному Барроузом и Уиллером (Burrows-Wheeler transform - BWT ), все одинаковые знаки, встретившиеся в разных позициях блока, собираются в однородные цепочки. В дальнейшем может быть использован метод RLE или статистическое сжатие. Последнее оказывается наиболее эффективным, если предварительно применить преобразование MTF (move-to-front, движение к началу), в результате которого чаще встречающиеся знаки получают меньшие номера, а все знаки в цепочке кроме первого заменяются нулями.

В дальнейшем мы детально рассмотрим все упомянутые здесь методы.

Эффективность сжатия
Эффективность сжатия сообщений характеризуется рядом факторов (рис.5.3):
  • качество оценивается прежде всего по степени сжатия (показателем здесь обычно служит отношение полученного объема кода к исходному объему в процентах). Однако, на практике важны также скорость и необходимый объем памяти. При этом требования по скорости и памяти могут существенно различаться для сжатия (упаковки) и восстановления (распаковки) сообщений. В таком случае говорят об асимметрии алгоритма по этим параметрам;
  • требования к показателям эффективности, как правило, противоречивы. Наилучшие показатели плотности сжатия достигаются обычно за счет более трудоемкой обработки и при использовании больших объемов памяти. Уместный компромисс зависит от области применения. Например, в системах реального времени предпочтение отдается скорости, а при массовом архивировании данных — плотности;
  • описанные выше универсальные методы сжатия имеют типичные особенности по показателям эффективности. “Cловарный” метод характеризуется максимальным быстродействием при приемлемой плотности сжатия, он также наиболее требователен к памяти. “Прогнозный” метод, напротив, медлен, но экономичен по памяти, при этом он обеспечивает максимальную степень сжатия для текстовых данных (для других данных это не всегда так). «Сортировочный» метод занимает промежуточное положение по всем показателям. При этом с точки зрения пользователя программ архиваторов различия в эффективности методов не слишком заметны;
  • эффективность сжатия зависит не только от используемого метода, но и от его программной реализации: один и тот же метод в разных программах-архиваторах может давать существенно разные показатели.

Кодирование длин серий RLE
В этом разделе мы также детально рассмотрим наиболее простой способ контекстного сжатия — кодирование однородных цепочек знаков. Рис.5.4 иллюстрирует примеры его применения:
  • в случае А способ кодирования RLE используется в самом простом варианте. В примере 6 однородных цепочек суммарной длиной 32 знака заменяются шестью парами «повторитель+знак», что позволяет сократить длину кода до 12 байт;
  • однако, на практике цепочки повторяющихся знаков могут чередоваться с одиночными знаками. В таком случае эффективность описанного простого решения резко снижается. Так, в случае Б на рисунке 5.4 исходной цепочке из 12 знаков соответствует код длиной 14 байтов;
  • усовершенствованное решение показано для случая В. Здесь для кодирования однородной цепочки знаков используется условно положительное значение повторителя (старший разряд байта равен 0). Если же в сообщение включается цепочка разнородных знаков, ее длина (до начала следующей однородной цепочки) кодируется условно отрицательным повторителем (старший разряд байта равен 1). В примере длина кода составит уже не 14, а 10 байт. Платой за такую возможность является сокращение предельной длины цепочки с 256 знаков до 128. Однако, на практике столь длинные однородные цепочки знаков встречаются редко.

Напомним, что метод RLE кодирования используется при передаче факсов и встроен в отдельные графические форматы (в частности, в формат pcx). Однако даже более важным является частое применение данного кода как вспомогательного элемента различных методов сжатия, с которыми мы познакомимся в дальнейшем.

Контрольные вопросы
1) Какие основные виды закономерностей в появлении знаков сообщений учитывают современные методы сжатия. В какой последовательности они учитываются.
2) Поясните термин “моделирование источника”. В чем состоит преимущество предварительной контекстной обработки для применения статистического сжатия.
3) Перечислите основные направления разработки комплексных методов сжатия и кратко охарактеризуйте их подходы, опираясь на рис.5.2.
4) Назовите основные показатели эффективности сжатия сообщений. В чем проявляется их противоречивость.
5) Сравните основные виды комплексных методов сжатия с точки зрения показателей эффективности.
6) Охарактеризуйте метод кодирования длин серий однотипных знаков RLE. Опираясь на рис.5.4 поясните простейший и усовершенствованный способы такого кодирования.


5.2 Словарные методы сжатия. Семейство алгоритмов LZ*

Способ «скользящего окна»
Напомним, что словарные методы обеспечивают сжатие в основном за счет замены повторяющихся цепочек знаков более короткими ссылками на ранее встретившиеся цепочки, которые хранятся в специальном “словаре”. Наибольшее распространение получил способ, где словарь представляет собой «окно», перемещающееся по тексту сообщения (рис.5.5). При этом:
  • словарь заполняется по мере обработки сообщения. Это похоже на перемещения рамки, которая движется от начала текста к его концу и внутрь которой попадают несколько сотен или тысяч знаков. Поиск повторяющихся цепочек ведется только внутри рамки (словаря) и знаки, оказавшиеся за ее левой границей “забываются”. В начале рамки (у правой границы) имеется узкая “прорезь” “буфер” для знаков, чей код подлежит сжатию (обычно их число не велико — например, от 16 до 64);
  • кодер выбирает цепочку знаков из буфера и пытается найти совпадающую с ней в словаре. Если это удается, то содержание буфера можно заменить короткой ссылкой на фрагмент словаря. Иначе Кодер постепенно укорачивает искомую цепочку и повторяет поиск. Если даже короткие цепочки в словаре не находятся, кодер передает эту часть сообщения по отдельным знакам. В любом случае все обработанные знаки пополняют словарь, одновременно из него удаляются знаки «устаревшие». С ростом объема словаря растет и вероятность нахождения совпадающих цепочек знаков, однако при этом время поиска быстро увеличивается;
  • сжатый код сообщения помещается в архивный файл. Он включает коды ссылок на найденные цепочки в словаре. Такая ссылка формата [d,l] включает номер первого знака d (distance) и длину цепочки l (length). В словарь также попадают стандартные коды знаков для случаев, когда цепочки в словаре не обнаруживались. Чтобы различать эти два типа кодов, они предваряются битовым префиксом (0 для кода знака и 1 для кода цепочки). Например, если объем буфера составляет 32 знака, то l=log232=5 бит, а при объеме словаря 1024 знака d=log21024=10 бит. Вместе с битовым префиксом длина кода цепочки составит 10+5+1=16 бит. При этом длина кода знака с учетом префикса составит 8+1 = 9 бит (для Unicode – 17 бит).

Пример сжатия способом “скользящего окна”
Рассмотрим пример сжатия по рассмотренному способу фразы «коси косой, косой Косой», в которой очевидно присутствуют повторяющиеся цепочки знаков (рис.5.6):










  • для первых пяти знаков в словаре (шаги 1-5) не находится подходящих цепочек и они передаются по отдельности (за счет использования битовых признаков на этом этапе мы проигрываем в объеме кода);
  • далее в словаре находится цепочка “кос”, которой отвечает ссылка [1,3] (начиная с первого знака в словаре — длина 3 знака) – шаг 6. Исходя из длины буфера и словаря длина кода цепочки составит 3+4+1=8 бит. Последующие 3 знака передаются по отдельности (шаги 7-9);
  • шаги 10-12 - передача кода длинной цепочки из 6 знаков, а затем 2 отдельных знаков. Наконец, шаг 13 — передача кода цепочки из 4 знаков. На этом этапе мы получаем наиболее существенный эффект по сжатию;
  • в целом длина сжатого кода в примере составляет 66% от исходной. Обратим внимание, что заметные потери в эффективности связаны с начальным заполнением словаря. В примере значимость этого этапа преувеличена, поскольку сжимаемый текст короток. В среднем степень сжатия текста словарным методом составляет обычно 40-60%.

Способ «прямой адресации цепочек»
Значительное замедление сжатия при больших объемах словаря в случае способа “скользящего окна” побудило использовать альтернативный способ организации словаря, который характеризуется меньшим временем поиска (рис.5.7):
  • словарь представляет собой не длинную однородную последовательность, а таблицу, каждая строка которой содержит цепочку знаков. При этом двоичный номер строки — это и есть код такой цепочки. Первоначально таблица содержит стандартный набор знаков с однобайтными кодами. В дальнейшем она дополняется появляющимися цепочками знаков. Содержание таблицы охватывает всю обработанную часть сообщения. Чтобы ограничить ее объем, редко используемые строки удаляются;
  • кодер ищет в таблице словаря строки с цепочками знаков, появляющимися в буфере. Такой поиск значительно быстрее, чем по длинной последовательности, и мало зависит от длины словаря. К найденной цепочке кодер добавляет следующий знак из сообщения и заводит для дополненного варианта новую строку, дополняя словарь. Слабостью данного метода является медленное заполнение словаря, поскольку новые цепочки каждый раз увеличиваются лишь на один знак;
  • сжатый код содержит двоичные номера строк словаря. При этом для одиночных символов такие коды однобайтны, а для цепочек — увеличиваются по мере роста их длины, однако их рост медлен (например, строка с номером 2000 будет иметь длину всего 11 бит).

Пример способа «прямой адресации цепочек»
Пример сжатия уже упомянутой выше фразы иллюстрирует рис.5.8.










  • первые пять знаков (шаги 1-5) сохраняются в виде стандартных кодов, в то же время в словаре сохраняются первые короткие двухзнаковые цепочки, которым присваиваются номера, следующие за емкостью байта;
  • на шаге 6 впервые появляется возможность использовать цепочку знаков из словаря. При этом в словарь помещается ее дополненный вариант. В дальнейшем сохранение отдельных знаков (шаги 7-11, 14, 15, 17) чередуется с сохранением ссылок на цепочки (шаги 12, 13, 16);
  • степень сжатия в примере получается существенно более низкой, чем по способы со скользящим окном. Это связано с краткостью сжимаемого текста, из-за которой сильно сказывается медленное заполнение словаря. При больших объемах сообщений эффективность сжатия будет существенно выше. В целом показатели эффективности двух рассмотренных подходов отличаются не слишком значительно.

Обзор реализация словарного сжатия
Показательна и интересна история развития словарного метода (рис.5.9):
  • первоначальная реализация метода была разработана около 40 лет назад Лемпелем и Зивом: сначала в варианте со скользящим словарем (алгоритм LZ77), а затем — с прямой адресацией цепочек (алгоритм LZ78). В обоих случаях это были теоретические работы, в которых не рассматривались проблемы эффективности (по скорости и памяти). Интересно, что для LZ78 была показана сходимость средней длины кода к энтропии, но лишь для очень длинных сообщений. В дальнейшем обе ветви развивались в направлении практической оптимизации:
  • практичные алгоритмы, приспособленные для программной реализации, были предложены Сторером и Шимански (LZSS) и Вэлчем (LZW). В приведенном выше описании мы опирались именно на эти алгоритмы. В дальнейшем они стали основой последующих разработок, которые уже занимались оптимизацией по отдельным показателям эффективности;
  • для направления “скользящего словаря” можно привести примеры усовершенствований на базе LZSS. В частности, алгоритм LZM оптимизирован по скорости (за счет использования где возможно быстрого сжатия RLE) и несколько проигрывет в сжатии. LZH, напротив, увеличивает плотность путем сжатия по Хаффмену указателей и кодов одиночных знаков, но при этом он заметно медленнее;
  • для направления «прямой адресации цепочек» на основе LZW был создан улучшенный по скорости алгоритм LZC (в основном за счет оптимизации программной реализации). Позже на его базе реализован алгоритм LZMV, в котором за счет ускорения роста длины цепочек в словаре улучшена плотность сжатия;
  • в целом существует большое разнообразие алгоритмов семейства LZ. Каждый из них имеет свои особенности и преимущества.

Особенности алгоритма LZMA (архиватор 7-Zip)
В качестве примера удачного современного решения можно привести алгоритм LZMA (Lempel-Ziv-Markov Algorithm), реализованный в архиваторе 7-Zip, с которым мы познакомимся в лабораторной работе (рис.5.10). К его особенностям относятся, в частности:
  • использование предварительного «разностного» кодирования (синоним «дельта- кодирование») для входного потока знаков. Поток исходных кодов знаков преобразуется в их разности. При этом набор используемых значений и необходимая разрядность значительно сокращаются. Например, для текста разность кодов букв не превышает 5 бит, а для цифр — 4 бит. Между тем, при исходном кодировании в Unicode для каждого знака требовалось 16 бит;
  • усовершенствованная бит-ориентированная модель сжатых данных, которая позволяет более экономично кодировать ссылки, а также значительно увеличить объем словаря (вплоть до 4 ГБ);
  • применение арифметического (интервального) кодирования для дополнительного статистического сжатия
  • оптимизация на программном уровне (например, поддержка многопоточности сжатия, а также использование исключительно команд целочисленной арифметики).

Алгоритм LZMA наглядно демонстрирует, насколько важной является «тонкая» оптимизировання программная реализация метода. В настоящее время он является одной из самых эффективных и популярных реализаций словарного подхода к сжатию.

Контрольные вопросы
1) Поясните принцип сжатия со «скользящим словарем», опираясь на рис.5.5.
2) Прокомментируйте пример сжатия со «скользящим словарем», опираясь на рис.5.6.
3) Поясните принцип сжатия с «прямой адресацией цепочек», опираясь на рис.5.7.
4) Прокомментируйте пример сжатия с «прямой адресацией цепочек», опираясь на рис.5.8.
5) Охарактеризуйте направления и этапы развития словарных методов, используя рис.5.9.
6) Расскажите об основных особенностях алгоритма LZMA, опираясь на рис.5.10.


5.3 Прогнозный метод сжатия. Алгоритм PPM

Описание подхода
Метод основан на прогнозировании вероятностей последующих знаков на основе предыстории, а также их кодировании с помощью таблицы Хаффмена, корректируемой по мере изменения статистики. Особенности алгоритма иллюстрирует рис.5.11:
  • по мере обработки знаков сообщений накапливаются оценки их условных вероятностей на различную глубину. В описании метода использован термин “контекст глубины Ki”. В частности, контексту K0 соответствуют безусловные вероятности знаков, контексту K1 – условные вероятности на глубину 1 знак, К2 — на глубину 2 знака и т.д.
  • кодер предсказывает вероятности появления разных знаков в следующей позиции с учетом разных контекстов. При этом “старшим” контекстам с более глубокой памяти присваиваются большие веса, как более информативным. Например, предсказанная вероятность знака может рассчитываться по формуле P = 0,1*P0 + 0,3*P1 + 0,6*P2, где P0, P1 и P2 вероятности появления знаков соответсвенно в контекстах K0, K1 и K2. В современных архиваторах используются контексты вплоть до уровней 5-6;
  • исходя из предсказанных вероятностей знаков кодер корректирует таблицу Хаффмена. Опираясь на обновленную таблицу, выполняется статистическое кодирование фактически поступающего знака. Если бы прогноз был идеальным, то каждый поступающий знак кодировался бы максимально коротко. На самом деле прогноз статистический и он сбывается далеко не всегда, но в среднем такой метод дает выигрыш;
  • сжатый код представляет собой последовательность битов, которая корректно декодируется благодаря правилу префиксности и синхронному изменению таблиц Хаффмена. Напомним, что синхронизация достигается за счет использования общих правил изменения таблиц на стороне кодера и декодера. В целом прогнозный метод сжатия обеспечивает максимальную степень сжатия для текстов — это и есть целесообразная сфера его использования.

Пример применения прогнозного способа
На рис.5.12 отображен ключевой этап метода — прогноз вероятностей знаков в очередной позиции:
  • в примере из 23 знаков фразы обработано 16 и прогнозируется значение 17-го знака. При этом условно предполагается использования алфавита из 100 символов. Так что помимо 7 уже появлявшихся видов знаков могут появиться еще 93. Метод предусматривает начальную инициализацию счетчиков всех знаков 1, что учитывается при подсчете вероятностей;
  • исходя из подсчета безусловных вероятностей (контекст К0) наиболее ожидаемо появление буквы «o». С учетом предшествующей буквы (в контексте К1 это тоже «o») скорее всего может появиться “с” и также вероятна “й”. А вот в контексте К2 наиболее вероятно появление “й” (ранее фиксировалась цепочка “сой”). Учет значимости контекстов дает наибольшую вероятность букве “й” (благодаря контексту К2) и высоко оценивает и вероятность “с” (благодаря К1). Другие знаки имеют значительно меньшие вероятности (на рисунке они показаны для ранее встречавшихся “о” и “к”, но алгоритм предусматривает их подсчет для всех знаков используемого алфавита);
  • по результатам полного набора прогнозных вероятностей алгоритм строит таблицу Хаффмена. Когда появляется реальный следующий знак текста (в данном случае “й”), он будет закодирован оптимально, поскольку именно его алгоритм считал наиболее вероятным. Если бы оценки вероятностей получились несколько иными (например, наиболее вероятным получилось бы “с”, а “й” занял вторую позицию), кодирование все равно было бы неплохим, поскольку “й” находится в верхушке списка.

Контрольные вопросы:
1) Опишите действие метода прогнозного сжатия, опираясь на рис.5.11.
2) Поясните понятие “глубина контекста” применительно к данному методу. Почему более глубокие контексты считаются более значимыми.
3) Поясните пример действия метода, исходя из рис.5.12.
4) Какова оптимальная область применения метода и почему.


5.4 Сортировочный метод сжатия. Алгоритм bzip2

Описание подхода способа
Сортировочный метод предусматривает преобразование контекста в форму, наиболее удобную для статистического сжатия. Такое преобразование выполняется в рамках блоков сообщения. Одной из наиболее популярных реализаций метода является алгоритм bzip2, структуру которого характеризует (рис.5.13):
  • на первом этапе обработка блока включает его преобразование по Барроузу-Уиллеру. В результате одинаковые знаки, которые были рассредоточены по всему блоку, группируются в однородные цепочки;
  • на втором этапе по отношению к результатам предыдущего может выполняться преобразование MTF (move-to-front), которое еще называют сортировкой по методу «стопки книг». Здесь часто встречающиеся знаки получают меньшие номера. К тому же все знаки однородной цепочки кроме первого заменяются нулями. В результате в блоке образуется большое количество одинаковых знаков (нулей), что очень удобно для статистического сжатия. Альтернативой MTF в других реализациях метода может быть сжатие однородных цепочек знаков по алгоритму RLE;
  • наконец, на последнем этапе выполняется статистичекое сжатие — например, по методу Хаффмена.

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

Как видно в примере, здесь выделяются повторяющиеся элементы текста: за буквой “У” часто следуют “-K”, за “-” повторяются “КУ”, а вслед за “K” - сочетание “У-”. В результате преобразования знаки “У”, “-” и “K” сосредотачиваются в однородные цепочки. Разумеется, в реальных сообщениях разнообразие знаков в блоках гораздо выше, однако и сами блоки обычно включают сотни знаков, так что эффект от перегруппировки существенен. Еще раз подчеркнем, что он тем больше, чем чаще встречаются повторяющиеся группы символов.

Важнейшей особенностью BWT является его обратимость. Полное описание алгоритма восстановления достаточно громоздко, так что мы ограничимся ссылкой на источник, где данный подход описан подробно.

Пример выполнения преобразования MTF
На рис.5.15 показано выполнение MTF для результатов предыдущего этапа.
  • первоначально все знаки получают исходные номера (в нашем примере для наглядности используем номера только четырех имеющихся в блоке знаков);
  • при появлении очередной знак блока кодируется своим текущим номером (в примере буква «У» заменяется на 3). После этого его код становится минимальным, а коды всех остальных знаков увеличиваются на «1» (последующие буквы «У» кодируются как «0», а знак «-» при первом появлении имеет номер «1». В дальнейшем эта процедура повторяется до конца блока).

Как видно, в результате такого преобразования неоднородность распределения вероятностей знаков существенно возросла (прежде всего за счет частого использования «0»). В результате статистическое кодирование по Хаффмену дает большее сжатие, чем до применения MTF.

Контрольные вопросы
1) Опишите этапность сортировочного сжатия в рамках алгоритма bzip2, опираясь на рис.5.13.
2) Охарактеризуйте действие преобразования Барроуза-Уиллера на блок данных, опираясь на пример рис.5.14.
3) Какие данные необходимы для восстановления исходного вида блока с помощью преобразования Барроуза-Уиллера.
4) Опишите выполнение преобразования MTF, опираясь на рис.5.15. Почему именно средняя длина кода при кодировании по Хаффмену значительно уменьшается в результате использования MTF.



О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP