Учебное пособие 130

Очевидно, что чем больше m, тем меньше q и поэтому тем меньше Ha1(B) и тем больше Ha2(B). Информация I(A,B) тем больше, чем меньше число m.

Дискретные сообщения

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

Дискретными сообщениями называются такие сообщения, которые могут быть переданы с помощью дискретных сигналов.

Знаки, наборы знаков, алфавиты

Языковые сообщения в письменной форме строят обычно, записывая знаки письма (графемы) друг за другом. Хотя длинные сообщения могут размещаться на многих строчках и страницах, это разбиение не имеет никакого значения - разве что в стихах. По существу такие сообщения являются последовательностями знаков. Это справедливо и для устных сообщений, если разложить устный текст на элементарные составные части (фонемы), и под знаками понимать фонемы.

Знак - это элемент некоторого конечного множества отличимых друг от друга обозначений, набора знаков.

Пример: набор знаков клавиатуры, набор мастей игральных карт, наборы значений [0, 1] и [FALSE, TRUE].

Набор знаков, в котором определен порядок знаков, называется алфавитом.

Алфавит десятичных цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Алфавит русского языка (для тех кто подзабыл): а, б, в, г,

д, е, ѐ, ж, з, и, й, к, л, м, н, о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, ь, э, ю, я.

Коды и кодирования

Если N - предложение некоторого естественного языка, то N можно рассматривать как последовательность знаков по крайней мере тремя разными способами.

Прежде всего N представляет собой последовательность букв, цифр, знаков препинания и т.д.; далее, N - это последовательность слов, которые могут рассматриваться как знаки; наконец, все предложение можно рассматривать как один знак.

Дискретные сообщения представляют собой конечные или бесконечные последовательности знаков. Слова, созданные из двоичного набора знаков, называются двоичными словами. Они не обязаны иметь одинаковую длину.

Кодом называется правило, описывающее отображение одного набора знаков в другой набор знаков. Если каждый образ при кодировании является отдельным знаком, то такое отображение называют

шифровкой, а образы - шифром. Обращение этого отображения называют декодированием или дешифровкой.

Системы счисления

Необходимость хранения чисел в памяти компьютера обусловило включение средств кодирования-декодирования в состав арифмети- ко-логических устройств процессоров. Числовые объекты, т.е. объекты видов integer и real (соответственно int и float), обрабаты-

(** - операция возведения в степень), называется представлением в позиционной системе счисления с основанием В. Например,

257 = 2*10**2 + 5*10**1 + 7*10**0; 110101 = 1*2**5 + 1*2**4 + 0*2**3 + 1*2**2 + 0*2**1 + 1*2**0.

Наряду с основаниями В=2 и В=10 употребляют основания В=8 и В=16. При этом говорят соответственно о числах в двоичной, десятичной, восьмеричной и шестнадцатеричной системах счисления. В качестве цифр используют начальные отрезки алфавита десятичных цифр; в 16-ричной системе используют алфавит {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}. Последние две системы используют для сокращенной записи двоичного числа.

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

легко переведено в шестнадцатеричную форму отдельной перекодировкой четырехразрядных групп (тетрад): EAABD63E. Перекодировка в восьмеричную систему выполняется аналогично, но с использованием трехразрядных групп (триад): 35042353076. Заметим, что восьмеричная система счисления последнее время используется крайне редко.

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

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

Для перевода неправильных дробей необходим раздельный перевод целой и дробной частей.

Для того, чтобы имелась возможность обрабатывать и отрицательные числа, диапазон обрабатываемых положительных чисел ограничивают. Например, один разряд в слове (старший) выделяют для кодирования знака числа: 0 служит кодом положительных чисел, 1 - отрицательных. Другим способом является представление отрицательных чисел дополнительным кодом. -x кодируется числом

t-1

(В**t)-x = 1 + Sum(B - 1 - Ai)*(B**i), i=0

где t - число отводимых разрядов (разрядность слова), Ai - i-ый разряд числа x.

Пример: Записать в дополнительном двоичном коде число -125. Слово состоит из 16 разрядов.

Двоичное представление числа 125 есть 0000000001111101 . По приведенной выше формуле записываем код -125:

1+

(2 - 1 - 1)*2**0 + (2 - 1 - 0)*2**1 + (2 - 1 - 1)*2**2 + (2 - 1 - 1)*2**3 + (2 - 1 - 1)*2**4 + (2 - 1 - 1)*2**5 + (2 - 1 - 1)*2**6 + (2 - 1 - 0)*2**7 + (2 - 1 - 0)*2**8 +

... + (2 - 1 - 0)*2**15 = 1111111110000011 .

Проще говоря, код положительного числа инвертируется (нули заменяются единицами, единицы - нулями) и к младшему разряду прибавляется 1. Обратите внимание на старший разряд - он равен 1.

Для представления вещественных чисел используется кодирование с плавающей точкой (К. Цузе, 1937). Числа переводятся в нормализованную форму

x = m * B**e,

так, чтобы abs(m) < 1. Формат машинного изображения числа с плавающей точкой (real или float) содержит поля для мантиссы m и порядка e длиной соответственно 24 и 8 разрядов. Мантисса и порядок кодируются отдельно и размещаются в собственных полях. Отметим, что нулевая целая часть мантиссы не хранится.

Пример: записать код вещественного числа 98.625 . Как следует из примеров предыдущей лекции, двоичное представление целой и дробной частей числа равно 1100010 и 1010, т.е.

98.625 = 1100010.1010 = 0.11000101010*2**111 (111 - двоичный порядок числа). Таким образом, получаем

000000000000011000101010 00000111 m e

Количество информации в шенноновских сообщениях

Шенноновская теория информации (1948 г.) исходит из элементарного альтернативного выбора между двумя знаками (битами) 0 и

1.Такой выбор соответствует приему сообщения, состоящего из од-

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

Если выбор состоит в том, что некоторый знак выбирается из множества n знаков, где n >= 2, то это можно сделать посредством конечного числа следующих друг за другом альтернативных выборов в форме выборочного каскада: данное множество из n знаков разбивается на два (непустых) подмножества, каждое из которых точно так же разбивается дальше, пока мы не получим одноэлементные подмножества.

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

[a,e,b,d,g,c,f] -> [a,e] -> [a] -> [e]

-> [b,d,g,c,f] -> [b,d,g] -> [b]

-> [d,g] -> [d] -> [g]

-> [c,f] -> [c] -> [f]

чтобы выбрать a или e, нужны два альтернативных выбора (количество информации составляет 2 бита), чтобы выбрать b, c или f, необходимы три альтернативных выбора (количество информации равно 3 бита) и т.д.

Если некоторый знак встречается часто, то, естественно, количество выборов, требующихся для его опознавания, стремятся сделать возможно меньшим. Соответственно для опознавания более редких знаков приходится использовать большее число альтернативных выборов. Другими словами, часто встречающиеся знаки содержат малое, а редкие - большое количество информации. Поэтому представляется разумным разбивать исходное множество знаков не на равновеликие, а на равновероятные подмножества, т.е. так, чтобы при каждом разбиении на два подмножества суммы вероятностей для знаков одного и для знаков другого подмножества были близки друг к другу, насколько это возможно. Ради простоты будем считать сначала, что заданные вероятности позволяют получить точное равенство. Тогда если i-й знак выделяется после Ki альтернативных выборов, то вероятность его появления Pi равна 1/2 в степени Ki. Обратно, для выбора знака, который встречается с вероятностью Pi, требуется

Ki = ld(1/Pi)

альтернативных выборов (ld - логарифм по основанию 2). Исходя из сказанного, мы определим количество информации, содержащейся в знаке, задаваемое частотой появления такого знака, как ld(1/Pi) бит. Тогда среднее количество информации, приходящееся на один произвольный знак, будет равно

n

H = Sum (Pi*ld(1/Pi)) бит. i=1

Величину H называют средним количеством информации на знак или информацией на знак. Понятно, что эта величина связана с энтропией источника сообщений.

Результат одного отдельного альтернативного выбора может

быть представлен как 1 или 0 (TRUE или FALSE). Тогда выбору всякого знака соответствует некоторая последовательность двоичных знаков 0 и 1, т.е. двоичное слово. Назовем это двоичное слово кодировкой знака, а множество кодировок всех знаков источника сообщений - кодированием источника сообщений. Получающиеся двоичные слова имеют, вообще говоря, разную длину: знаку, вероятность которого Pi соответствует слово длины Ni = ld(1/Pi). Таким образом, H является средней длиной двоичных слов, используемых при двоичном кодировании источника сообщений.

Если количество знаков представляет собой степень двойки, n = 2**N, и все знаки равновероятны, Pi = (1/2)**N, то все двоичные слова имеют длину N и

H = N = ld(n) .

Для источника сообщений с n знаками и произвольными значениями Pi

Sum(Pi*ld(1/Pi)) <= ld(n) .

Равенство достигается в случае равновероятных знаков. Выбор из n знаков всегда можно осуществить с помощью N альтернативных выборов, где

N-1 < ld(n) <= N .

Для этого достаточно разбивать всякое множество знаков так, чтобы количества знаков в двух получающихся подмножествах различались не более чем на 1. Таким образом, для источника с n знаками всегда существует кодирование словами длины N.

Если при некотором кодировании источника сообщений i-й знак имеет длину Ni, то средняя длина слов равна

L = Sum(Pi*Ni) . i

Теорема кодирования Шеннона 1. Имеет место неравенство

H <= L.

2. Всякий источник сообщений можно закодировать так, что разность L-H будет сколь угодно мала.

Чтобы получить кодирования, о которых говорится в пункте 2 теоремы, следует не просто кодировать каждый знак по отдельности, а рассматривать вместо этого двоичные кодирования для n**k групп по k знаков. Тогда длина кода i-го знака Zi вычисляется так:

Ni = (средняя длина всех кодовых групп, содержащих Zi)/k. Чем больше берется k, тем точнее можно приблизиться к разбиению на равновероятные подмножества. Часто уже при k=2 или k=3 достигается практически приемлемое приближение.

Сравним, например, кодирование отдельных знаков с кодированием пар символов.

Разность L-H называют избыточностью кода, а 1-(H/L) - относительной избыточностью кода. Избыточность - это мера бесполезно совершаемых альтернативных выборов. Так как в практических случаях отдельные знаки почти никогда не встречаются одинаково часто, то кодирование с постоянной длиной кодовых слов в большинстве случаев избыточно. Несмотря на это, такое кодирование применяют довольно часто, руководствуясь техническими соображениями, в частности возможностью параллельной и мультиплексной передачи.

Важной практической задачей является определение энтропии естественных языков. Для русского языка (из расчета 31 буквы) получаем H = ld(32) = 5 бит/знак. Если же учесть частоты букв, то получим H = 4.35 бит/знак. Однако относительные частоты отдельных букв не являются статистически независимыми: некоторые буквы сильно коррелируют. Относительная избыточность русского языка без учета семантики составляет по меньшей мере 76%.

Пропускная способность канала В курсе технического обеспечения информатики вас, по-видимо-

му, знакомили с методами дискретизации аналоговых сигналов (сообщений) - разверткой и квантованием. Развертка состоит в том, что область определения аналоговой функции разбивается на участки равной длины, а сама функция заменяется другой, которая постоянна на каждом участке - ступенчатой функцией. Значение ступенчатой функции на участке равно среднему по участку значению исходной функции. Чем грубее развертка, тем больше свойств исходного сигнала теряется. Наоборот, чем "тоньше" развертка, тем точнее она воспроизводит все подробности исходной функции. Это правило формулируется в виде теоремы отсчетов:

Пусть F(t) - функция

f

F(t) = S (A(g)*cos(2*PI*g*t) + B(g)*sin(2*PI*g*t)) dg 0

(т.е. F(t) как функция времени составлена из колебаний с частотой, не превышающей некоторой критической частоты f, называемой шириной полосы пропускания). Здесь PI = 3.1415926.

Тогда, если

T <= 1/(2*f),

то F(t) можно представить в виде

(Другими словами, функцию можно восстановить по значениям в точках отсчета (n*T), если частота отсчета 1/T не меньше удвоенной критической частоты).

Если рассматривать теорему отсчетов в свете теории информации Шеннона, то каждые T секунд нужно передавать сообщение, а именно амплитудное значение. Квантование сводит дело к выбору из некоторого конечного числа n амплитудных значений, которые появляются с определенными вероятностями Pi.

H = Sum(Pi*ld(1/Pi)) - это информация на такт времени. Поток информации, т.е. информация, передаваемая в единицу времени, составляет

C = H/T = 2*f*H бит/с.

Если мельчить квантование, то в соответствии с этой формулой будет расти и поток информации - в случае равновероятных амплитуд он равен 2*f*ld(n). Однако, если на передаваемую функцию накладываются шумы, искажающие амплитудные значения, то любое измельчение квантования будет, очевидно, служить не только для передачи информации, но и для точного воспроизведения помех. Таким образом, при наличии шумов поток информации ограничен.

Для специального случая "белого гауссова шума", в котором все частоты представлены с одинаковой интенсивностью, а амплитуды подчиняются нормальному гауссовому распределению, получаем

H <= ld(sqrt(1+Ns/Nr)),

где Ns - средняя мощность сигнала, Nr - средняя мощность шумов. Поэтому максимальный поток информации по передающему каналу, или пропускная способность канала, составляет

Cmax = 2*f*Hmax = f*ld(1+Ns/Nr).

Это подтверждает известное положение техники связи, что пропускная способность канала может быть увеличена только за счет ширины полосы пропускания f и улучшения отношения мощности сигнала к мощности шумов.

АЛГОРИТМЫ СЖАТИЯ И КОДИРОВАНИЯ

Введение

Принципиальная возможность сжатия данных с целью уменьшения их объема имеет три основных практических приложения. Главное применение сжатие данных находит при резервном копировании и хранении информации. Каждому пользователю время от времени приходит-

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

Другое очевидное применение сжатия данных - в возможности записи на диск большего объема информации. Ведь купить утилиту сжатия данных значительно проще и дешевле, чем установить новый жесткий диск большего объема. Однако, в таком решении есть свой недостаток. Работа со сжатыми файлами займет несколько больше времени из-за необходимости их предварительной распаковки и последующего удаления архива.

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

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

Общие принципы работы программ упаковки

Любые методы сжатия данных основаны на поиске в файле избыточной информации и последующем ее кодировании с целью получения минимального объема. Существует несколько основных методов сжатия данных, которые с теми или иными модификациями используются практически всеми упаковщиками. Обычно упаковщики осуществляют сжатие информации сразу несколькими способами. Такой прием применяется для получения наибольшей степени сжатия. Выбор способа зависит от типа данных, и определяется упаковщиком для каждого конкретного случая. Рассмотрим, в каких случаях данные могут содержать избыточную информацию, и как от этого можно было бы избавиться.

Простейший способ сжатия данных основан на анализе требований, предъявляемых к ним со стороны конкретной прикладной задачи, и последующем сохранении только самой необходимой информации. Например, латинский ASCII текст использует 7-битный код, однако каждый символ обычно записывается 8 битами. Этим с самого начала предполагается избыточность старшего бита в байте кода символа. Гарантированный коэффициент сжатия 0.875 может быть получен простым уплотнением.

Другой прием удаления избыточной информации можно найти среди приемов сжатия графических образов. Часто графические образы записываются в виде последовательности байтов, каждый из которых содержит информацию по одному элементу изображения. В действительности для кодирования одного элемента бывает достаточно лишь 4 бит. Мы можем, таким образом, получить гарантированный коэффициент сжатия 0.5 простым заполнением неиспользуемых 4 бит кодом из следующего байта.

Первая задача, которую нужно решить перед выбором метода

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

Сжатие последовательностей одинаковых символов

(Run Length Encoding)

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

Метод основан на представлении последовательности одинаковых байтов в виде двух величин. Одна из них равна количеству повторяющихся символов, а вторая содержит код символа. Например, строка NNNMMMNNNNMMMMMMMM длиной 18 символов может быть записана в виде 3N3M4N8M, что дает значительное сокращение длины. Метод достаточно прост в реализации и лучше всего работает в составе системы, учитывающей типы данных, подлежащих сжатию. Например, двоичный файл может быть записан в виде набора одних только длин битовых строк. Сами элементы могут и не сохраняться, поскольку для двоичных данных существует лишь два возможных варианта состояний. Каждая новая величина в записи будет означать изменение состояния битовой строки. Таким образом, двоичная строка 111100011000001111 будет записана просто пятью числами 43254.

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

Программа, использующая метод сжатия последовательностей одинаковых символов, должна четко отслеживать последовательности единичной длины. Это может быть достигнуто с помощью небольшого увеличения объема сжимаемых данных. Если предположить, что мы работаем со стандартным 7- битным ASCII кодом на 8-битных системах, мы можем достаточно просто реализовать подобный алгоритм.

В случае последовательности длиной в один или два байта нужно просто записывать эти последовательности в выходной файл. Если длина последовательности равна трем байтам и более, следует записывать длину в первом байте, а сам символ -во втором байте выходного кода. Чтобы показать, что текущий байт содержит длину последовательности, нужно установить его старший бит (прибавить 128). Используя такой прием, мы несколько увеличиваем объем кодируемых байтов, однако получаем гарантию, что выходной файл будет меньше, чем входной. При декодировании архивного файла вначале нужно осуществлять проверку старшего бита первого байта каждой пары, затем, если бит установлен, записывать второй байт в выходную строку необходимое количество раз.

Описанный метод является простым и очень эффективным способом сжатия файлов. Однако он не обеспечивает большой экономии объема, если обрабатываемый текст содержит мало последовательнос-

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

Алгоритм Хаффмана

Один из первых алгоритмов эффективного кодирования информации был предложен Д.А.Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину. Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2.Выбираются два свободных узла дерева с наименьшими весами.

3.Создается их родитель с весом, равным их суммарному весу.

4.Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5.Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0.

6.Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Первая задача состоит в подсчете числа повторений каждой буквы алфавита в исходном тексте. Далее из списка удаляются те буквы, которые ни разу не встретились в тексте. Затем строится дерево кодирования. Лучше всего предварительно отсортировать получившийся список в порядке убывания частоты повторений символов. Построение дерева начнется от самого правого символа в списке. Частоты двух наиболее редко встречающихся символов суммируются, и результат записывается в узле дерева. Исходные частоты стали теперь "детьми" новой суммарной частоты. Если имеется более двух символов с минимальной частотой повторений, то нужно просто образовать из них самостоятельные пары. Если имеется нечетное количество наименьших значений частоты, то нужно объединить непарную величину со следующей наименьшей частотой.

По мере продолжения процесса построения "дети" становятся "внуками", "правнуками" - и так до тех пор, пока все дерево не будет закончено. Полное количество символов исходного текста будет представлено в вершине полученного дерева. Таким образом можно осуществлять эффективную проверку правильности построения дерева кодирования. Необходимо сказать, что созданная структура дерева, является оптимальной с точки зрения минимизации кодирования. То есть, с помощью таблицы кодирования (или префиксного ко-

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

Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами - Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5 + 6 == 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви О родителя, узел Д - ветви 1.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис.

Дерево кодирования Хаффмана после второго шага

На следующем шаге <наилегчайшей> парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д - ветви 1.

На последнем шаге в списке свободных осталось только два узла - это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис.

¦0-----------24------------1

Окончательное дерево кодирования Хаффмана

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

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

Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

А0

Б100

В101

Г 110

Д111

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством битов, а наиболее редкий символ Д - наибольшим.

Классический алгоритм Хаффмана имеет один существенный недостаток. Для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался. кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева ), другого для собственно кодирования.

Алгоритм Хаффмана (Huffman Encoding), или кодирование символами переменной длины, предлагает отказаться от обычного представления файлов в виде последовательностей 7- или 8-битных символов. Главный недостаток такого способа записи файлов состоит в том, что в нем не делается различий между кодированием символов, с разной частотой встречающихся в файлах. Так, наиболее частые в английском языке символы E и I, имеют ту же самую длину, что и относительно редкие Z, X или Q. Код переменной длины позволяет записывать наиболее часто встречающиеся символы и фразы всего лишь несколькими битами, в то время как редкие символы и фразы будут записаны более длинными битовыми строками.

Простейший способ кодирования информации символами переменной длины осуществляется при помощи таблицы соответствий (translation table). Например, анализируя любой английский текст, можно установить, что буква E встречается гораздо чаще, чем Z, а X и Q относятся к наиболее редко встречающимся. Таким образом, используя таблицу соответствий, мы можем закодировать каждую букву E меньшим числом бит, используя более длинный код для более редких букв.

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

Арифметическое кодирование

В 70-е годы у алгоритма Хаффмана появился достойный конку-

рент - арифметическое кодирование. Этот метод основан на идее преобразования входного потока данных в одно число с плавающей точкой. Естественно, чем длиннее сообщение, тем длиннее получающееся в результате кодирования число. Итак, на выходе арифметического декодера получается число, меньшее 1 и большее либо равное 0. Из этого числа можно однозначно восстановить последовательность символов, из которых оно было составлено. Эксперименты на различных типах данных показывают, что арифметическое кодирование всегда дает результат не хуже, чем кодирование Хаффмана. В некоторых случаях выигрыш может быть очень существенным. Алгоритм кодирования Хаффмана кодирует каждый символ кодируемого сообщения целым количеством битов. Если частота встречаемости символа в сообщении очень велика, например 90 из 100, то схема кодирования Хаффмана может в лучшем случае закодировать этот символ в 1 бит. При использовании алгоритма арифметического кодирования возможно, в принципе, поставить в соответствие этому символу код длиной в 0.15 бита, что в 6 раз более эффективно.

Рассмотрим работу арифметического компрессора на примере сообщения "BILL_GATES". Поставим в соответствие каждому символу сообщения вероятность его появления в сообщении:

от 0 до 1. Длина интервала для символа равна вероятности его появления в сообщении. Положение интервала вероятности каждого символа не имеет значения. Важно только то, чтобы и кодер, и декодер располагали символы по одинаковым правилам. Распределим интервалы вероятности для символов нашего сообщения:

A1/10 [ 0.10, 0.20 [

B1/10 [ 0.20, 0.30 [

S1/10 [ 0.80, 0.90 [

T1/10 [ 0.90, 1.00 [

В общем виде алгоритм арифметического кодирования можно описать следующим образом (используя условный алгоритмический язык):

НижняяГраница := 0.0; ВерхняяГраница := 1.0;

Пока ((ОчереднойСимвол = ДайОчереднойСимвол) <> Конец) Интервал := ВерхняяГраница - НижняяГраница; ВерхняяГраница := НижняяГраница + Интервал *

ВерхняяГраницаИнтервалаДля(ОчереднойСимвол); НижняяГраница := НижняяГраница + Интервал *

НижняяГраницаИнтервалаДля(ОчереднойСимвол);

КонецПока;

Выдать(НижняяГраница);

Работа этого алгоритма на нашем примере будет выглядеть следующим

Таким образом, согласно нашей схеме, число 0.2572167752 однозначно кодирует сообщение "BILL_GATES".

В общем виде алгоритм арифметического декодирования можно описать следующим образом (используя условный алгоритмический язык):

Число := ПрочитатьЧисло();

Пока (Число <> 0.0)

Символ := НайтиСимволВИнтервалКоторогоПопадает(Число); Выдать(Символ);

Интервал := ВерхняяГраницаИнтервалаДля(Символ) - НижняяГраницаИнтервалаДля(Символ);

Число := Число - НижняяГраницаИнтервалаДля(Символ); Число := Число / Интервал;

КонецПока;

0.0

Таким образом при обработке числа после определения символа, в интервал которого оно попадает, этот символ выдается как раскодированный, а его влияние на число устраняется действиями, обратными действиям при кодировании.

Несмотря на то, что, на первый взгляд, алгоритм арифметического кодирования может работать на компьютерах с математическим сопроцессором, наилучшим образом он может быть реализован на основе стандартной 16 или 32-битовой целочисленной арифметики. Ранее было отмечено, что при работе алгоритм отслеживает верхнюю и нижнюю границы возможного выходного кода. Сразу после старта нижняя граница устанавливается в 0.0, а верхняя - в 1.0; но также отмечалось, что верхняя граница берется не включительно. Поэтому первое упрощение для работы алгоритма с целочисленной арифметикой - это замена 0.0 на 0x0000, а 1.0 - на 0xFFFF. Это заметно упрощает процессы кодирования и декодирования.

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

В процессе работы алгоритма может возникнуть ситуация, когда, например, верхняя граница равна 70000, а нижняя - 69999. Интервал между ними так мал, что все последующие итерации не изменят содержимое границ, а поскольку старшие цифры не совпадают, то алгоритм не будет выдавать цифр кода, то есть зациклится.

Для избежания такой ситуации алгоритм немного корректируется. Если две старшие цифры границ не совпадают, то, если они отличаются на единицу, проверим следующие по значимости цифры границ. Если они равны 0 у верхней границы и 9 у нижней, значит алгоритм на пути к зацикливанию. Сделаем следующее: удалим вторые по значимости цифры границ и остальные менее значимые сдвинем влево. Затем увеличим специальный счетчик, чтобы запомнить то, что мы выбросили цифры.

Эти действия могут выглядеть, например, так:

Эти действия продолжаются до тех пор, пока старшие цифры границ не совпадут. Затем в выходной поток помещается совпавшая старшая цифра, а за ней равное счетчику количество 9 или 0, в зависимости от того, к цифре верхней или нижней границы сошлись старшие цифры.

При декодировании используются три регистра: регистры верхней и нижней границы сообщения, и регистр кода, который содержит очередные цифры декодируемого сообщения. Значение в регистре кода всегда находится между значениями верхней и нижней границ. Верхняя и нижняя границы при инициализации алгоритма и на каждом его шаге имеют абсолютно те же значения, что они имели при кодировании, и обновляются одинаковым образом. Так же осуществляется проверка на зацикливание. Выполняя эту проверку, декодер определяет, когда необходимо помещать очередную цифру и входного потока в регистр кода. На основании содержимого регистров кода и границ декодер принимает решение о раскодируемом символе.

Алгоритм Лемпела - Зива - Уэлча (LZW)

Словарем в данном алгоритме является потенциально бесконечный список уже просмотренных ФРАЗ. И кодер, и декодер начинают работу с почти пустого словаря, содержащего только одну закодированную строку - NULL строку. Когда кодер считывает очередной символ сообщения, символ добавляется к текущей строке. До тех пор пока текущая строка соответствует какой-либо фразе из словаря, процесс продолжается. Но рано или поздно текущая строка перестает соответствовать какой-либо фразе словаря. В этот момент, когда текущая строка представляет собой последнее совпадение со слова-

рем плюс только что считанный символ сообщения, кодер выдает код, состоящий из индекса совпадения и следующего за ним символа, нарушившего совпадение строк. Кроме того, новая фраза, состоящая из индекса совпадения и следующего за ним символа, добавляется в словарь. В следующий раз, когда эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает степень сжатия информации. LZW построен вокруг таблицы фраз (словаря), которая отображает строки символов сжимаемого сообщения в коды фиксированной длины. Таблица обладает так называемым свойством предшествования, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже содержится в словаре. Если ячейки словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).

Кодер LZW никогда не выдает сами символы сжимаемого сообщения - только коды фраз.

Алгоритмы группы LZ (которые послужили основой для алгоритма LZW ) имеют существенный недостаток. Так как они используют в качестве словаря только небольшой фрагмент сообщения, то нет возможности кодировать повторяющиеся подстроки, расстояние между которыми в сообщении больше, чем размер словаря. Кроме того, алгоритмы ограничивают размер подстроки, которую можно закодировать. Очевидно, что указанные факторы снижают эффективность кодирования.

Чисто механический подход к улучшению характеристик кодера LZ за счет увеличения размеров словаря обычно дает обратные желаемым результаты и теоретически более мощный кодер становится практически невозможно использовать.

Алгоритм работы кодера LZW можно описать следующим образом:

Проинициализировать словарь односимвольными фразами, соответствующими символам входного алфавита (обычно это

256 ASCII символов)

Прочитать первый символ сообщения в текущую фразу w;

Шаг алгоритма:

Прочитать очередной символ сообщения К; Если КОНЕЦ_СООБЩЕНИЯ

Выдать код w; ВЫХОД;

Конец Если;

Если фраза wK уже есть в словаре Заменить w на код фразы wK; Повторить Шаг алгоритма

Иначе

Выдать код w; Добавить wK в словарь;

Повторить Шаг алгоритма; Конец Если;

Пример работы кодера LZW приведен в таблице.

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

Очевидно, что декодер LZW использует тот же словарь, что и кодер, строя его по аналогичным правилам при восстановлении сжатого сообщения. Каждый считываемый код разбивается с помощью словаря на предшествующую фразу w и символ К. Затем рекурсия продолжается для предшествующей фразы w до тех пор, пока она не окажется кодом одного символа, что и завершает декомпрессию этого кода. Обновление словаря происходит для каждого декодируемого кода, кроме первого. После завершения декодирования кода его последний символ, соединенный с предыдущей фразой, добавляется в словарь. Новая фраза получает то же значение кода (позицию в словаре), что присвоил ей кодер. Так шаг за шагом декодер восстанавливает тот словарь, который построил кодер.

Алгоритм декодирования LZW может быть описан следующим обра-

зом:

КОД = Прочитать первый код сообщения (); ПредыдущийКОД = КОД; Выдать символ К, у которого код ( К) == КОД;

Следующий код:

КОД = Прочитать очередной код сообщения(); Входной Код = КОД; Если КОНЕЦ_СООБЩЕНИЯ

ВЫХОД; Конец Если;

Следующий символ: Если КОД == код(wK)

Выдать К; КОД = код(w);

Повторить Следующий символ Иначе если КОД == код(К)

Выдать К; Добавить в словарь (ПредыдущийКОД, К);

ПредыдущийКОД = ВходнойКОД; Повторить СледующийКОД;

Конец Если;

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

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

Обработка исключительной ситуации несколько сложнее. Исключительная ситуация складывается тогда, когда кодер пытается закодировать сообщение KwKwK, где фраза Kw уже присутствует в словаре. Кодер выделит Kw, выдаст код (Kw) и добавит KwK в словарь. Затем он выделит KwK и пошлет только что созданный код (KwK ). Декодер при получении кода (KwK) еще не добавил этот код к словарь, потому что еще не знает символ-расширение предыдущей фразы. Тем не менее, когда декодер встречает неизвестный ему код, он может определить, какой символ выдавать первым. Это символ-расшире- ние предыдущей фразы; он был последним раскодированным символом и будет последним символом текущей фразы.

Модифицированный алгоритм декодирования выглядит следующим образом:

КОД = Прочитать первый код сообщения(); ПредыдущийКОД = КОД; Выдать символ К, у которого код(К) == КОД; ПоследнийСимвол = К; Следующий код:

КОД = Прочитать очередной код сообщения(); ВходнойКОД = КОД; Если КОНЕЦ_СООБЩЕНИЯ

ВЫХОД; Конец Если;

Если Неизвестен(КОД) // Обработка исключительной ситуации Выдать (ПоследнийСимвол); КОД = ПредыдущийКОД;

ВходнойКОД = код(ПредыдущийКОД,ПоследнийСимвол); Конец Если;

Следующий символ: Если КОД == код(wK)

В_СТЕК( К ); КОД = код(w);

Повторить Следующий символ Иначе если КОД == код(К)

Выдать К;

ПоследнийСимвол = К; Пока стек не пуст

Выдать ( ИЗ_СТЕКА() ); Конец пока;

Добавить в словарь (Предыдущий КОД, К); ПредыдущийКОД = Входной КОД; Повторить СледующийКОД;

Конец Если;

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

Система шифрования DES

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

Одна из классических задач такого рода - это защита сообщений от несанкционированного доступа. Эта задача может быть решена

спомощью шифрования файлов, предназначенных для пересылки по линии связи.

Наряду с проблемой секретности информации существует проблема достоверности этой информации. Если предположить, что секретный шифр раскрыт было кем-либо прочитано, изменено и отправлено вновь. Тогда до получателя дойдет искаженное сообщение. При получении важно убедиться в том, что:

· Сообщение отправлено вполне определенным лицом (тем, кто его подписал);

· Во время передачи сообщения не произошло никаких искажений текста.

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

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

Одним из наиболее мощных алгоритмов шифрования данных на сегодняшний день является алгоритм DES (Data Encryption Standard), предназначенный для использования в государственных и правительственных учреждениях США для защиты от несанкционированного доступа важной, но несекретной информации. DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации.

Основные достоинства алгоритма DES:

· Используется только один ключ длиной 56 битов; · Зашифровав сообщение с помощью одного пакета, для расшифровки

можно использовать любой другой; · Относительная простота алгоритма обеспечивает высокую скорость

обработки информации; · Достаточно высокая стойкость алгоритма.