Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ЗАДАНИЕ 9 Оптимальное кодирование и сжатие текстов

Часто необходимо сжимать данные, чтобы минимизировать объем памяти для их хранения или время передачи данных. Для сжатия текстовых данных преимущественно используют оптимальные алфавитные коды. Все они основаны на двух принципах: выполнение свойства префикса; кодирование более короткими элементарными кодами тех букв, которые чаще встречаются в тексте. Наиболее известный из этих кодов - код Хаффмена [2, 25]. Цель данного задания - изучение и программирование алгоритмов построения кода Хаффмена, практика анализа алгоритмов.

Средняя длина элементарного кода

Предположим, что некоторый источник генерирует сообщения в алфавите А = {аь ..., а„). Для кодирования сообщений используется алфавит В = {Ь,..., bq), при этом п> q>1. Кодирование выполняется побуквенно на основе схемы

(а, е А, р, е В*, i — 1, ..., п). Схема (р определяет алфавитный код ср(А) = {рь ..., Р„} как некоторую совокупность элементарных кодов. Будем далее полагать, что элементарные коды в ф(А) перечисляются в том же порядке, что и соответствующие им буквы алфавита А.

Очевидно, что если ф(А) является однозначно декодируемым кодом, то алфавитный код ф*(А), получаемый из ф(А) перестановкой элементарных кодов, также является однозначно декодируемым. Когда длины элементарных кодов равны (ф(А) - равномерный код), то перестановка Р, в ф(А) не влияет на длину кода сообщения. Но если длины элементарных кодов различны, то длина кода сообщения зависит от состава букв в сообщении и от того, какие элементарные коды каким буквам назначены.

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

В математике мерой частоты появления того или иного события (в нашем случае появления буквы а, еА в сообщении а) является вероятность. Не останавливаясь на строгом определении, заметим, что вероятность некоторого события определяет долю случаев, в которых это событие произошло, к общему числу случаев. В дальнейшем вероятность события я, будем обозначать pt.

Пример 9.1. Пусть А — {яь а2, я3, я4} - исходный алфавит. Известны вероятности

Это означает, что в сообщении а е А* длиной 1000 букв около 500 раз появится буква яь около 250 раз - буква а2 и примерно 125 раз - каждая из букв я3 и а4.

Важно отметить, что

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

Если использовать 2-разрядный равномерный код

то сообщению а длины 1000 будет всегда отвечать код сообщения <Рх(а) длины 2000. Применение неравномерного префиксного кода

приводит к коду сообщения фг(а), длина которого примерно равна так что | ф2(а) | < | cpi(ot) |.

Примечательно, что в примере 9.1 буквы в алфавите А перечислены в порядке убывания вероятностей их появления, а элементарные коды в <р2(А) - в порядке возрастания длин этих кодов. Таким образом, применение неравномерного кода и учет вероятностных характеристик источника сообщений позволяет уменьшить длину кодов сообщений.

Основной характеристикой алфавитного кода является средняя длина его элементарных кодов. Определим это понятие.

Пусть заданы алфавиты

Кроме того, известен набор вероятностей

где pi - вероятность появления буквы at е А в словах, генерируемых источником сообщений. Не ограничивая общности, будем считать, что

т. е. из А сразу исключим буквы, которые не могут появляться в сообщениях, а остальные упорядочим по убыванию вероятностей их появления. Пусть ср(А) = {рь ..., Р„} - алфавитный код, в котором слово Р, является кодом буквы я, е А и t( - длина Р, е В* (/ = 1, ..., и). Тогда число

называется средней длиной элементарного кода для ср(А) относительно Р. Значение ?ср - это среднее число букв кодирующего алфавита В, приходящихся на одну букву исходного алфавита А.

Пример 9.2. Рассмотрим для два алфавитных кода

где ср2(А) получается из cpi(A) перестановкой элементарных кодов. Вычислим среднюю длину элементарного кода для (pi(А) и (р2(А):

Следовательно, значение ?ср зависит от порядка назначения элементарных кодов буквам алфавита А.

Обозначим через L = (?ь tn) набор длин элементарных кодов для ф(А) = {рь —, Р„}, где ?/ = | |3,1, i = 1, ..п. Заметим, что если наборы Р = (р, ...,р„), L - (th ..., ?„) рассматривать как векторы, то ?ср - скалярное произведение этих векторов. Нетрудно убедиться в справедливости следующего утверждения.

Утверждение 9.1. При р >р2 > ... >р„ наименьшее значение скалярного произведения векторов Р = (р, ...,рп), L = (?],..., ?„) достигается, когда 1 < 12 < ... < 1„.

Ясно, что равномерные коды можно считать частным случаем неравномерных кодов, когда l = i2 = ... = В этих условиях

т. е. значение ?ср совпадает с разрядностью равномерного кода и не зависит от порядка назначения элементарных кодов буквам алфавита А.

В случае равновероятности появления букв алфавита А в передаваемых сообщениях, когда

?ср также не зависит от того, какие элементарные коды каким буквам назначены, и

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>