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


Новости сайта

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

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


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




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

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

  • 1

    • Легко распознаваемая грамматика может быть основана, например, на таком алфавите:

      0000000100100011010001010110011110001111

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

      Или на таком:

      000102101112

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

      И даже на таком:

      AEAHCHFHIEORSHWH

      Здесь заимствованным алфавитом явно является латинский.

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

  • 2

    • Вот так может выглядеть собственный алфавит легко распознаваемой грамматики:

      Обратите внимание, что '' — это один знак, и '' — это тоже один знак! Мы никогда не спутаем символы, находящиеся в строке, потому что в алфавите нет знака '' и нет знака '', заимствованного алфавита также нет. В данном алфавите каждый знак занимает одно знакоместо (что, впрочем, вполне естественно), даже если один шире другого!

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

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

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

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

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

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

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

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

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

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

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



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика