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

Условно переменные разделим на входные (то, что дано), выходные (результат: то, что нужно получить) и промежуточные, необходимые в процессе вычислений. Например, для программы вычисления наибольшего общего делителя (алгоритм Евклида), входные переменные m и n, промежуточная переменная r. Выходная переменная тоже n. Эти переменные должны иметь тип «натуральные числа». Но такого типа в Паскале нет. Поэтому придется использовать какой-то целый тип. От размера типа зависит диапазон чисел, для которых можно использовать программу. Если описать переменные так:

то самым большим числом на входе можно взять 32767 = 2 16 – 1.

Важно! Значение переменных, описанных в разделе Var , не определено. Иногда можно встретить определение переменной как ячейки памяти, в которой содержится значение переменной. Подразумевается, что описание переменной связывает адрес этой ячейки с именем переменной, то есть имя используется как адрес ячейки памяти, где содержится значение. Но само значение еще не определено.

В алгоритме Евклида значение остатка r сравнивается с нулем. 0 – целая константа. Можно (но не обязательно) определить константу со значением 0, например, так:

В процессе компиляции в тексте программы идентификатор Zero будет заменен своим числовым значением.

Тип константы Zero не очевиден. Ноль есть в любом целочисленном типе. В разделе констант можно описать типизированную константу, указав и тип и значение:

Zero: integer = 0;

Но теперь Zero стала обычной переменной целого типа, начальное значение которой определено и равно нулю.

Контроль использования переменных осуществляется на этапе компиляции. Компилятор обычно пресекает попытки установить для переменной значение неподходящего типа. Многие языки программирования автоматически приводят значение переменной к нужному типу. Как правило, такое неявное преобразование типа у начинающих программистов является источником трудно обнаруживаемых ошибок. В Паскале неявное преобразование типа можно считать скорее исключением, чем правилом. Исключение сделано только в отношении констант и переменных типа INTEGER (целые), которые разрешается использовать в выражениях типа REAL (действительные). Запрет на автоматическое преобразование типов не означает, что в Паскале нет средств преобразования данных. Они есть, но их нужно использовать явно.

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

Рассмотрим четыре символа и . Если они появляются в последовательности данных с равной вероятностью ( каждая), то мы им просто присвоим четыре двухбитовых кода 00, 01, 10 и 11. Все вероятности равны, и поэтому коды переменной длины не сожмут эти данные. Для каждого символа с коротким кодом найдется символ с длинным кодом и среднее число битов на символ будет не меньше 2. Избыточность данных с равновероятными символами равна нулю, и строку таких символов невозможно сжать с помощью кодов переменной длины (или любым иным методом).

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

Табл. 1.2. Коды переменной длины.

В табл. 1.2 предложен код Code1, который присваивает самому часто встречающемуся символу самый короткий код. Если закодировать данный с помощью Code1, то среднее число бит на символ будет равно . Это число весьма близко к теоретическому минимуму. Рассмотрим последовательность из 20 символов

в которой четыре символа появляются, примерно, с указанными частотами. Этой строке будет соответствовать кодовая строка кода Code1 длины 37 бит

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

Однако, если мы теперь попробуем декодировать эту двоичную последовательность, то немедленно обнаружим, что Code1 совершенно не годен. Первый бит последовательности равен 1, поэтому первым символом может быть только , так как никакой другой код в таблице для Code1 не начинается с 1. Следующий бит равен 0, но коды для и все начинаются с 0, поэтому декодер должен читать следующий бит. Он равен 1, однако коды для и оба имеют в начале 01. Декодер не знает, как ему поступить. То ли декодировать строку как , то есть, , то ли как , то есть . Причем заметим, что дальнейшие биты последовательности уже не помогут исправить положение. Код Code1 является двусмысленным. В отличие от него, код Code2 из табл. 1.2 дает при декодировании всегда однозначный результат.

Code2 имеет одно важное свойство, которое делает его лучше, чем Code1, которое называется свойством префикса. Это свойство можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-то символа, то ни один код другого символа не должен иметь в начале эту последовательность (не может быть префиксом, то есть, приставкой). Раз строка «1» уже выбрана в качестве целого кода для , то ни один другой код не может начинаться с 1 (то есть, они все должны начинаться на 0). Раз строка «01» является кодом для , то другие коды не должны начинаться с 01. Вот почему коды для и должны начинаться с 00. Естественно, они будут «000» и «001».

Значит, выбирая множество кодов переменной длины, необходимо соблюдать два принципа: (1) следует назначать более короткие коды чаще встречающимся символам, и (2) коды должны удовлетворять свойству префикса. Следуя эти принципам, можно построить короткие, однозначно декодируемые коды, но не обязательно наилучшие (то есть, самые короткие) коды. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество самых коротких кодов (которые в среднем имеют наименьшую длину). Исходными данными этого алгоритма должны быть частоты (или вероятности) символов алфавита. К счастью, такой простой алгоритм существует. Он был придуман Давидом Хаффманом и называется его именем. Этот алгоритм будет описан в § 1.4.

Следует отметить, что не только статистические методы компрессии используют коды переменной длины при кодировании индивидуальных символов. Замечательным примером служат арифметические коды, о которых будет рассказано в § 1.7.

Коды переменной длины

КОДИРОВАНИЕ И СЖАТИЕ ИНФОРМАЦИ

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

Коды переменной длины

Первое правило построения кодов переменной длины, состоит в том, что короткие коды следует присваивать часто встречающимся символам, а длинные – редко встречающимся. При этом коды следует назначать так, чтобы из можно было декодировать однозначно, а не двусмысленно. Например, рассмотрим четыре символа a 1 , a 2 , a 3 , a 4 . Если они появляются в сообщении с равной вероятностью (p = 0,25), то присвоим им четыре двухбитовых кода: 00, 01, 10, 11. Все вероятности равны, поэтому коды переменной длины не сожмут данные. Для каждого символа с коротким кодом найдётся символ с длинным кодом и среднее число битов на символ будет не меньше 2. Избыточность данных равновероятными символами равна 0, и строку таких символов невозможно сжать с помощью кодов переменной длины (или какого-либо другого метода).

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

В таблице 12.1 предложен код Код_ 1, который присваивает самому часто встречающемуся символу самый короткий код. Среднее число бит на символ равно 1,77. Это число близко к теоретическому минимуму.

Таблица 12.1

Рассмотрим последовательность из 20 символов

a 1 a 3 a 2 a 1 a 3 a 3 a 4 a 2 a 1 a 1 a 2 a 2 a 1 a 1 a 3 a 1 a 1 a 3 a 1 ,

в которой четыре символа появляются, примерно, с одинаковыми частотами. Этой строке будет соответствовать кодовое слово длины 37 бит:

1|010|01|1|010|010|001|01|1|1|01|01|1|1|010|1|1|01|010|1.

Среднее число бит на символ составляет 1,85, что не слишком далеко от вычисленной минимальной средней длины. Однако если попытаться декодировать последовательность, то окажется, что Код _1 имеет существенный недостаток. Первый бит кодового слова равен 1, поэтому первым символом последовательности может быть только a 1 , так как код никакого другого символа не начинается с 1. Следующий символ равен 0, но коды для символов a 2 , a 3 , a 4 все начинаются с 0, поэтому декодер должен считать следующий символ. Он равен 1, но коды для a 2 и a 3 оба имеют в начале 01. Поэтому декодер не знает, как действовать дальше: декодировать строку как 1|010|01…, то есть a 1 a 3 a 2 …, или как 1|01|001…, то есть a 1 a 2 a 4 .... Дальнейшие биты последовательности не могут исправить положения. Поэтому Код­ _1 является двусмысленным. От этого недостатка свободен Код _2.

Код _2 обладает так называемым префиксным свойством, которое можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-либо символа, то ни один код какого-либо другого символа не должен иметь в начале эту последовательность (код символа не может быть префиксом кода другого символа). Если строка 01 является кодом для a 2 , то другие коды не должны начинаться с 01. Поэтому коды для a 3 и a 4 должны начинаться с 00. Естественно для этого выбрать 000 и 001.

Следовательно, выбирая множество кодов переменной длины необходимо соблюдать два принципа: 1) следует назначать более короткие кодовые последовательности часто встречающимся символам; 2) полученные коды должны обладать префиксным свойством. Следуя этим принципам можно построить короткие, однозначно декодируемые коды, но необязательно наилучшие (то есть самые короткие) коды. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество самых коротких кодов (имеющих наименьшую среднюю длину). Исходными данными этого алгоритма должны быть частоты (или вероятности) символов алфавита. Таким алгоритмом является кодирование по методу Хаффмана.

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

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

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

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

В восьмиразрядной таблице символьной кодировки (например, ASCII) каждый символ кодируется восемью битами и, следовательно, занимает в памяти 1 байт. В разделе 1.3 нашего учебника рассказывалось о том, что частота встречаемости разных букв (знаков) в тексте разная. Там же было показано, что информационный вес символов тем больше, чем меньше его частота встре­чаемости. С этим обстоятельством и связана идея сжа­тия текста в компьютерной памяти: отказаться от коди­рования всех символов кодами одинаковой длины. Сим­волы с меньшим информационным весом, т.е. часто встречающиеся, кодировать более коротким кодом по сравнению с реже встречающимися символами. При таком подходе можно существенно сократить объем общего кода текста и, соответственно, места, занимае­мого им в памяти компьютера.

Такой подход известен давно. Он используется в ши­роко известной азбуке Морзе, несколько кодов которой приведены в табл. 3.1, где "точка" кодируется нулем, а "тире" - единицей.

Таблица 3.1

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

В отличие от кодов равной длины, которые использу­ются в стандарте ASCII, в этом случае возникает про­блема разделения между кодами отдельных букв. В аз­буке Морзе эта проблема решается с помощью "паузы" (пробела), которая, по сути, является третьим симво­лом алфавита Морзе, т.е. алфавит Морзе не двух-, а трех-символьный.

А как быть с компьютерной кодировкой, где исполь­зуется двоичный алфавит? Одним из простейших, но весьма эффективных способов построения кодов разной длины, не требующих специального разделителя, явля­ется алгоритм Д.Хаффмена (D.A. Huffman, 1952 г.). С помощью этого алгоритма строится двоичное дерево, которое позволяет однозначно декодировать двоичный код, состоящий из символьных кодов различной длины. Двоичным называется дерево, из каждой вершины ко­торого выходят две ветви. На рис. 3.2 приведен при­мер такого дерева, постро­енного для алфавита англий­ского языка с учетом часто­ты встречаемости его букв. Полученные, таким обра­зом, коды можно свести в таблицу.

Таблица 3.2

С помощью табл. 3.2 легко кодировать текст. Так, например, строка из 29 знаков

WENEEDMOR ESNOWFORBE TTERSKIING преобразуется в код: 011101 100 1100 100 100 110110001111101011100 ОНО 1100 1110 011101 01001 1110 1011 011100 100 001001 100 10110110 110100011 1010 1010 1100 00001, который при размещении его в памяти побайтно при­мет вид:

01110110 01100100 10011011 00011111 01011100 01101100 11100111 01010011 11010110 1110010000100110 01011011 01101000 11101010 10110000 001

Таким образом, текст, занимающий в кодировке ASCII 29 байт, в кодировке Хаффмена займет только 16 байт.

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

Нетрудно догадаться, что изображенное дерево пред­ставляет собой сокращенный вариант кода Хаффмена. В полном объеме в нем должны быть учтены все возмож­ные символы, встречающиеся в тексте: пробелы, знаки препинания, скобки и др.

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

Коротко о главном

Сжатием информации называют такое ее преобразо­вание, которое ведет к сокращению объема занимаемой памяти при сохранении закодированного содержания.

Идея способа сжатия текста: длина кода символа уменьшается с уменьшением его информационного веса, т.е. с увеличением частоты встречаемости в тексте.

Алгоритм сжатия по Хаффмену представляется в виде двоичного дерева.

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

Вопросы и задания

В чем различие кодов постоянной и переменной длины?

За счет чего коды переменной длины позволяют "сжимать" текст?

Закодируйте с помощью ASCII-кодов и кодов Хафф­мена следующий текст: HAPPYNEWYEAR. Подсчитай­те в обоих случаях требуемый объем памяти.

4. Раскодируйте с помощью двоичного дерева (см.рисунок) следующий код:

11110111 10111100 00011100 00101100 10010011 01110100 11001111 11101101 001100

Двоичное дерево алфавита английского языка, используемое для кодирования методом Хаффмена