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

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

Если же для алфавита легко распознаваемой грамматики другой алфавит не заимствуется, то всё становится ещё проще (см. Пример 2).

На Примере 2 мы видим прототип классической троичной грамматики, как бы внешне ни выглядели символы её алфавита.

Последний пример может показаться более тяжёлым для понимания. Однако обратимся в этой связи к простому «жизненному» опыту. Все согласятся, что грамматика, основанная на кириллическом алфавите, может считаться легко распознаваемой. Однако кто же на самом деле пишет кириллические символы так, чтобы ширина всех была абсолютно равной? Или кто пишет кириллические символы хотя бы с одинаковым расстоянием между ними? Даже во многих шрифтах, которыми пользуются компьютерные программы, ширина символов намеренно закладывается различающейся, а расстояние между разными символами допускается изменять, делая его неодинаковым. Всё дело — в изображении символа… А ещё — в его порядковом номере в алфавите.

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

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

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

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

Чтобы каждый символ алфавита, применяемого в условиях легко распознаваемой грамматики, состоял из одинакового количества знаков битового кода, поступают следующим образом. Сначала создают битовые коды для первых двух символов, и оба этих кода имеют длину в один бит: 0 и 1. Затем следующим двум символам назначают двухбитовый код, начинающийся с единицы. Потом следующие 4 символа кодируются трёхбитовым кодом, также начинающимся с единицы, и т. д. Когда всем символам подобным образом назначены битовые последовательности, видно, какая из всех битовых последовательностей самая длинная. Именно столько бит должны кодировать каждый символ: более коротким битовым последовательностям нужно приписать слева недостающее количество нулей (выровнять нулями вправо).

Можно проще и сразу определить количество бит, которым требуется закодировать каждый символ, образованный на основе алфавита легко распознаваемой грамматики. Если мощность алфавита обозначить буквой N, а количество бит — буквой I (информационная ёмкость), то эти две величины связываются формулой I = log2 N. В случае, когда в результате расчётов получается дробное число, необходимо округлить значение I до целого с избытком (т. к. не бывает дробных битов). Для этого используется математическая операция, записываемая как x = ⌈y⌉. Данная запись означает, что x является минимальным целым числом не менее y. Другими словами, если получается, что I = 5,3, то придётся округлить это значение до 6 (а не до 5).

Конечная запись формулы представлена в виде (25.1).

Есть и другая математическая операция, позволяющая находить максимальное целое число, не превосходящее указанного. Она записывается как x = ⌊y⌋, где x ≤ yx ∈ Zy ∈ R.

Итак, количество бит, которое необходимо для кодирования каждого символа легко распознаваемой грамматики, можно определить по формуле (25.1):

(25.1)
Формула Хартли
(25.1)

Равенство (25.1) называется формулой Хартли.

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

Пусть количество возможных состояний единицы информации обозначено буквой s. Тогда формула Хартли (25.1) приобретает вид (25.2):

(25.2)
Формула Хартли
(25.2)

Что означает дробное выражение, полученное по формулам (25.1) или (25.2) без осуществления требуемого в них приведения к целому числу? Только то, что анализ одного из битов (если речь идёт именно о битах) снижает неопределённость знания не в два раза (если речь идёт именно о битах), а меньше, к примеру, в полтора раза (примените формулу (25.1) без приведения к целому значению для Примера 2 из предыдущего параграфа).

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

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

То же можно сказать и в случае кодирования в кубитовый код (см. Пример 4)