§26. Кодирование с использованием распознаваемой грамматики

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

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

Для кодирования символов некоторого алфавита с помощью непрерывного неравномерного кода по правилам распознаваемой грамматики требуется соблюдать простое правило: начало кода (идентификатора) любого символа не должно совпадать ни с каким другим кодом (идентификатором) из той же таблицы транслитерации. Например, если мы начали битовое кодирование символов алфавита и присвоили его первому символу битовый код (идентификатор) 0, то ни один код (идентификатор) другого символа не может начинаться с 0. Это относится не только к битовому кодированию. Для того, чтобы увидеть, как составляются битовые коды для символов алфавита, см. Пример 1. Читаются (распознаются, декодируются) битовые коды так, как это описано в §24.

Обратите внимание, что порядок следования символов в исходном алфавите в случае применения неравномерного кодирования очень часто бывает не слишком-то важен!

«Хороша экономия!» — скажете вы, посмотрев предыдущий пример, — «если в сообщении часто повторяется первый или второй символ алфавита, то такая кодировка, может, ещё и оправдана. Но мы знаем, что с помощью равномерного кодирования каждый символ алфавита, состоящего из пяти символов, можно кодировать тремя битами. Во многих случаях сообщение в подобной кодировке может иметь гораздо бо́льшую информационную ёмкость, чем могло бы!» И в этом вы, безусловно, правы. Тогда можно предложить иную кодировку, которая будет более экономичной — она описана в Примере 2.

 

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

 

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

 

Наиболее оптимальный способ неравномерного кодирования, основанный на принципах распознаваемой грамматики, предлагает метод, который называется деревом Хаффмана (кодом, алгоритмом Хаффмана). В чём состоит этот алгоритм при переходе к битовой кодировке, можно увидеть на Примере 4.

 

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

 

Если кодировать слова, в которых буквы не повторяются, по алгоритму Хаффмана, то код больше будет напоминать равномерный. Попробуйте, например, создать битовый код для строки ‘снег’.

 

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

 

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

 

Существует формула, которая позволяет оценить среднюю длину кода одного символа из строки, в которой употреблены разные символы и, возможно, некоторые из них повторяются. Наряду с обозначениями, введёнными в предыдущем параграфе, мы используем дополнительные. Пусть Iср — средняя информационная ёмкость одного символа, N — мощность алфавита, использованного для создания строки, l — количество всех символов в строке, li — встречаемость i-го (конкретного) символа алфавита, использованного для создания этой строки, где i меняется от 1 до N. Средняя длина битового кода (битового идентификатора) любого символа (его средняя информационная ёмкость, измеряемая в битах) определяется равенством (26.1):

(26.1)
Формула Шеннона
(26.1)

Соотношение (26.1) называется формулой Шеннона.

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

 

(26.2)
Примерная информационная ёмкость сообщения в битах
(26.2)
Подробнее о математической операции x = ⌈y⌉ можно прочитать в предыдущем параграфе.

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

 

(26.3)
Примерное число бит на конкретный символ в зависимости от частоты его упоминаний
(26.3)

Некоторые вычисления, связанные с формулой Шеннона и её следствиями, можно видеть на Примере 6.

 

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

 

(26.4)
Формула Шеннона
(26.4)
(26.5)
Примерная информационная ёмкость сообщения, выраженная в любых единицах информации
(26.5)
(26.6)
Примерная информационная ёмкость одного конкретного символа в любых единицах информации
(26.6)

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

 

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

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

Построенный подобным способом код читается для его последующей интерпретации несколько по-иному. Символ не считается распознанным до тех пор, пока не прочитан разделитель «конец символа».

Как можно осуществить кодирование с разделителями, видно из Примера 7.

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

В одной и той же грамматике разделителей может быть несколько, и они могут использоваться для разных целей. Можно создать такую грамматику некоторого языка, в которой присутствуют следующие понятия о разделителях: «конец символа» и «конец слова». При этом обычно предполагается, что разделитель «конец слова» должен следовать только и сразу после какого-либо разделителя «конец символа». В любом случае ни одна битовая последовательность, представляющая разделитель, не может быть частью кода никакого символа. Описание возможности применения нескольких разделителей одновременно можно увидеть из Примеров 8 — 10.

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

 

Грамматика языка может содержать и дополнительные правила, определяющие порядок чтения кода. Подобное можно наблюдать на Примере 10.