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


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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

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

Битовые идентификаторы символов алфавита, на которых можно построить нераспознаваемую грамматику, приведены в таблице транслитерации Примера 1.

  • 1

    • Имеется таблица транслитерации в битовый код:

      СимволАБВГДЕ
      Идентификатор00010000010100110

      Грамматика, построенная с помощью подобного способа кодирования, является нераспознаваемой, поскольку идентификатор символа 'А' является началом идентификаторов 'В' и 'Г', а идентификатор символа 'Б' является началом идентификаторов символов 'Д' и 'Е'. Таким образом, символы 'В', 'Г', 'Д' и 'Е' никогда не будут распознаны из строки, содержащей последовательную запись идентификаторов символов предложенного алфавита.

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

  • 2

    • Имеется таблица транслитерации в битовый код:

      СимволНАТШМДП
      Идентификатор101010011100011000000

      Данный способ кодирования позволяет организовать нераспознаваемую грамматику, поскольку начало идентификатора символа 'М' совпадает с идентификатором символа 'П'. Однако строка 'НАТАША', например, кодируется так, что распознаётся однозначно, — только потому, что в ней отсутствует символ 'М'.

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

  • 3

    • Задача. Имеется таблица транслитерации в битовый код:

      СимволНАТШМДП
      Идентификатор101010011100011000000

      С помощью алфавита, указанного в ней, составлены 4 строки, содержащие, соответственно, имена 'НАТАША', 'МАША', 'ДАША' и 'ПАША'. Строки были закодированы с использованием имеющейся таблицы транслитерации. Какую из строк невозможно раскодировать однозначно?


      Решение. Не кодируя данные в условии задачи строки, рассмотрим таблицу транслитерации. Мы видим, что начало идентификатора символа 'М' совпадает с идентификатором символа 'П', поэтому в процессе чтения кода вместо 'М' будет распознаваться 'П'. Таким образом, не будут распознаны верно все строки, в которых имеется символ 'М'. Среди заданных строк символ 'М' содержит только одна, так что невозможно раскодировать однозначно строку 'МАША'.

  • 4

    • Задача. Имеется таблица транслитерации в битовый код:

      СимволАВДНТЯ
      Идентификатор000010100100011

      С помощью алфавита, указанного в ней, составлены 4 строки, содержащие, соответственно, имена 'ЯНА', 'ТАНЯ', 'ВАНЯ' и 'ДАНЯ'. Строки были закодированы с использованием имеющейся таблицы транслитерации. Какую единственную из строк возможно раскодировать однозначно?


      Решение. Не кодируя данные в условии задачи строки, рассмотрим таблицу транслитерации. Мы видим, что начала идентификаторов символов 'В' и 'Т' совпадают с идентификатором символа 'А', а начало идентификатора символа 'Д' совпадает с идентификатором символа 'Н'. Значит, невозможно верно интерпретировать строки, содержащие символы 'В', 'Д' и 'Т', и корректно распознаётся только строка 'ЯНА'.

      Собственно, такой результат следовало ожидать, поскольку все символы, входящие в строку 'ЯНА', встречаются в остальных строках, а по условию задачи распознаваемый код могло повлечь кодирование лишь одной строки из четырёх.

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

  • 5

    • Задача. Имеется таблица транслитерации в кубитовый код:

      СимволАКЛЧШ
      Идентификатор01011202

      С помощью алфавита, указанного в ней, составлены 4 строки, содержащие соответственно слова 'ШАЛАШ', 'КАША', 'ЛАК' и 'ЧАША'. Строки были закодированы с использованием имеющейся таблицы транслитерации. Какую строку из данных невозможно раскодировать однозначно?


      Решение. Не кодируя данные в условии задачи строки, рассмотрим таблицу транслитерации. Мы видим, что начало идентификатора символа 'Ч' совпадает с идентификатором символа 'Ш', значит, невозможно верно интерпретировать все строки, содержащие символ 'Ч'. Такой строкой является только 'ЧАША'.

      В этой задаче тоже нетрудно догадаться, какое слово выбрать в качестве ответа. Дело в том, что каждый символ алфавита встречается хотя бы в двух словах. Кроме 'Ч'…

  • 6

    • Задача. Имеется таблица транслитерации, основанная на кириллическом и латинском (заимствованных) алфавитах:

      СимволВИЙОСХШЫ
      ИдентификаторVIYOSHSHI

      Определить возможность корректного распознавания кода строки, содержащей слово 'ВЫСОХШИЙ'.


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

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

  • 7

    • Для кодирования строки, содержащей слово 'РЕГИСТРАЦИЯ', в битовый код можно использовать следующую грамматику. Пусть её основой будет алфавит идентификаторов, видимый из таблицы транслитерации:

      Согласные буквыСимволРГСТЦ
      Идентификатор10010111011101111
      Гласные буквыСимволИЕАЯ 
      Идентификатор1011011101111

      Кроме того, в грамматике присутствуют следующие правила: 1) непосредственно после гласной буквы может следовать только согласная, а непосредственно после согласной — только гласная; 2) если требуется записать две или более гласных или согласных подряд, между их кодами используется разделитель '0'; 3) разделитель '0' используется только для отделения гласной буквы от гласной и согласной от согласной, и ни в каких других случаях.

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

      При интерпретации кода строки, содержащей слово 'РЕГИСТРАЦИЯ', данные проблемы становятся вполне ощутимы. Вот, собственно, код строки, содержащей слово:
      10011010110110011100100111011111001111.

      А вот этот же код, в котором показано деление на группы по несколько бит, что необходимо для интерпретации:
      10'0'110'101'10'110'0'1110'0'100'1110'1111'10'0'1111.

      Как видно, результат подобного распознавания не очень-то похож на слово 'РЕГИСТРАЦИЯ'.

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

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



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


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

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

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



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