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


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

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

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

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

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

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

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

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

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

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

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

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


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


Сеть творческих учителей

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

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

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

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

  • 1

    • Задача. Имеется следующий алфавит: 'У', 'С', 'Н', 'Л', 'Д'. Присвоить его символам битовые коды, построенные по принципу неравномерного кодирования в рамках распознаваемой грамматики.


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

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

      Заметим также, что код 11 нельзя присвоить третьему символу ('Н'), иначе не останется вариантов для трёхбитового кодирования. Разрешённым кодом для него можно считать 110.

      Останется два четырёхбитовых кода для оставшихся символов: 1110 (символ 'Л') и 1111 (символ 'Д'). Вот такая таблица транслитерации у нас получилась:

      СимволУСНЛД
      Идентификатор01011011101111

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

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

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

  • 4

    • Задача. Информационное сообщение содержит единственное слово 'БАРАНИНА'. Закодировать это сообщение с использованием распознаваемой грамматики так, чтобы его битовый код имел наименьшую длину (или: чтобы сообщение имело наименьшую информационную ёмкость).


      Решение. Для решения такой задачи используем алгоритм Хаффмана. Для начала выделим использованные в сообщении символы кириллического алфавита. Вот они:

      АБИНР

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

      СимволАНИБР
      Встречаемость32111

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

      Объединим два наиболее редко встречаемых символа (из правой части таблицы) в один символ и обозначим этот символ как '➊' (ему при необходимости можно определить любое изображение). Получается, что исходное сообщение выглядело бы с этим символом как '➊А➊АНИНА', т. е. этот вновь определённый символ встречается в исходном сообщении уже 2 раза:

      СимволАНИБР
      Встречаемость32111
      Новый символАНИ
      Встречаемость3212

      В полученном алфавите вновь поменяем порядок следования символов:

      СимволАНИ
      Встречаемость3221

      Этот символ можно было бы поставить на второе место, а не на третье, но будем действовать всё же так, как уже определили.

      Во вновь полученном алфавите снова выделим два последних символа и объединим в один '➋', после этого преобразования наше исходное сообщение выглядело было как '➋А➋АН➋НА':

      СимволАНИ
      Встречаемость3221
      Новый символАН
      Встречаемость323

      Последний раз пересортируем символы по их встречаемости в порядке убывания.

      СимволАН
      Встречаемость332

      И также последний раз объединим два последних символа в один '➌'.

      СимволАН
      Встречаемость332
      Новый символА
      Встречаемость35

      Мы получили, наконец-то, алфавит, состоящий только из двух символов, что и требовалось сделать при определении битовых кодов символов исходного алфавита: поскольку бит принимает только два значения, то и символов в алфавите должно быть два. Здесь символы разрешается не сортировать по частоте употребления. Теперь можно начать присвоение битовых кодов всем символам во всех алфавитах, которые у нас есть. Пусть во всех случаях код левого символа получает (или добавляет к существующей битовой последовательности) бит 0, а код правого символа — 1. В этом случае в промежуточной таблице транслитерации символ 'А' сразу получает свой постоянный код 0, а символ '➌' — код 1:

      СимволА
      Код01

      Введённый нами "искусственный" символ '➌' как бы "распадается" на два символа при переходе к предыдущему, трёхсимвольному, алфавиту: на '➋' и 'Н'. Назначим символу '➋' код по правилу: 1 возьмём от "производящего" его '➌' и, поскольку он находится в таблице левее 'Н', то допишем к единице 0. Для формирования кода символа 'Н' возьмём 1 от "производящего" его '➌' и, поскольку он находится в таблице правее, добавим к единице ещё одну единицу. Вот что получилось:

      СимволАН
      Код01011
      Производящий символА
      Код01

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

      Вот следующий шаг (и очередная промежуточная таблица транслитерации):

      СимволАИН
      Код010010111
      Производящий символАН
      Код01011

      Последний шаг — и мы приходим к исходному алфавиту сообщения, окончательно достраиваем искомую таблицу транслитерации:

      СимволАБРИН
      Код01000100110111
      Производящий символАИН
      Код010010111

      Коды символов получены, и теперь мы можем закодировать сообщение. Вот его код: 100001001011101110.

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

      Алфавит 1 СимволАНИБР
      Встречаемость32111
      Код01110110001001
      Алфавит 2 Символ
      (до сортировки)
      АНИ
      Встречаемость
      (до сортировки)
      3212
      Код011101100
      Символ
      (после сортировки)
      АНИ
      Встречаемость
      (после сортировки)
      3221
      Код011100101
      Алфавит 3 Символ
      (до сортировки)
      АН
      Встречаемость
      (до сортировки)
      323
      Код01110
      Символ
      (после сортировки)
      АН
      Встречаемость
      (после сортировки)
      332
      Код01011
      Алфавит 4 СимволА
      Встречаемость35
      Код01

      Попробуйте закодировать короче!

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

  • 5

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


      Решение. Мы видим, что в исходной строке 2 раза повторяется фрагмент (подстрока) 'что такое ' (обратите внимание — на конце подстроки имеется пробел). Также можно не рассматривать по-отдельности пробелы и символ 'и', кроме того, если мы их объединим, то во всей строке больше не останется пробелов! И последнее: пусть сочетание символов 'пл' считается одним символом. После подобных допущений получится следующий алфавит (в целях сокращения описания решения введём дополнительные идентификаторы, которые будут обозначать ту или иную часть исходной строки):

      Часть строки'что такое ''х''о''р''ш'' и ''пл'
      Идентификатор1234567
      Встречаемость2251111

      Итак, мы теперь полагаем, что в исходной строке всего 7 различных символов! Отметим, кстати, что символ 'о' входит в исходную строку только 5 раз, а не 9, поскольку двум фрагментам строки, содержащим 'о', мы уже присвоили отдельные идентификаторы. Осталось только произвести сортировку по убыванию встречаемости указанных символов и применить алгоритм Хаффмана.

      Алфавит 1 Идентификатор3124567
      Встречаемость5221111
      Код01101111010101110001001
      Алфавит 2 Идентификатор
      (до сортировки)
      312458
      Встречаемость
      (до сортировки)
      522112
      Код011011110101011100
      Идентификатор
      (после сортировки)
      312845
      Встречаемость
      (после сортировки)
      522211
      Код011011110010101011
      Алфавит 3 Идентификатор31289
      Встречаемость52222
      Код0110111100101
      Алфавит 4 Идентификатор
      (до сортировки)
      31210
      Встречаемость
      (до сортировки)
      5224
      Код011011110
      Идентификатор
      (после сортировки)
      31012
      Встречаемость
      (после сортировки)
      5422
      Код010110111
      Алфавит 5 Идентификатор31011
      Встречаемость544
      Код01011
      Алфавит 6 Идентификатор312
      Встречаемость58
      Код01

      Вот так в таблице транслитерации битовые коды соответствуют частям строки:

      Часть строки'о''что такое ''х''р''ш'' и ''пл'
      Идентификатор3124567
      Встречаемость5221111
      Код01101111010101110001001

      А вот какой короткий битовый код строки, содержащей фразу, получился: 11011101010010111000110100101110 (всего 32 бита).

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

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

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

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

(26.2)
Примерная информационная ёмкость сообщения в битах
(26.2)

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

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

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

  • 6

    • Задача. Даны две строки, содержащие, соответственно, слова 'ОБОРОТЕНЬ' и 'ОБОРОТ'. Произвести для этих строк по-отдельности расчёты, связанные с определением средней длины битового идентификатора для каждого символа, длин битовых идентификаторов для конкретных символов, общей длины битовой последовательности для всей строки целиком при условии кодирования по правилам распознаваемой грамматики. Проверить результаты кодированием с помощью алгоритма Хаффмана.


      Решение. Разделим страницу пополам, в левой части будет содержаться решение поставленной задачи для первого слова, а в правой — для второго.

      'ОБОРОТЕНЬ''ОБОРОТ'

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

      СимволОБРТЕНЬ
      Номер, i1234567
      Встречаемость, li3111111

      N = 7

      l = 9

      СимволОБРТ
      Номер, i1234
      Встречаемость, li3111

      N = 4

      l = 6

      Определим прогнозируемую среднюю длину битовой последовательности, соответствующей одному любому символу без учёта количества его упоминаний в строках, по формуле (26.1):

      Iср = –1/3 log2 ( 1/3 ) – 2/3 log2 ( 1/9 ) =
      5/3 log2 3 ≈ 2,65 (бит).

      Iср = –1/2 log2 ( 1/2 ) – 1/2 log2 ( 1/6 ) =
      1/2 ( 1 + log2 6) ≈ 1,79 (бит).

      Определим прогнозируемую длину битового кода для строк, содержащих соответствующие слова, умножением ⌈Iср × N⌉ (можно было бы и по формуле (26.2), но в данном случае это менее удобно):

      Iстроки = ⌈2,65 × 9⌉ = ⌈23,85⌉ = 24 (бита).

      Iстроки = ⌈1,79 × 6⌉ = ⌈10,74⌉ = 11 (бит).

      Определим примерные длины битовых кодов для некоторых символов алфавита, для которых это возможно, в зависимости от частоты упоминаний этих символов в строках, — по формуле (26.3):

      I1 = ⌈log2 ( 9/3 )⌉ = ⌈log2 3⌉ = ⌈1,58⌉ = 2 (бита).

      Для остальных символов формула (26.3) не позволяет произвести расчёт информационной ёмкости.

      I1 = ⌈log2 ( 6/3 )⌉ = ⌈log2 2⌉ = 1 (бит).

      Для остальных символов формула (26.3) не позволяет произвести расчёт информационной ёмкости.

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

      СимволОБРТЕНЬ
      Номер1234567
      Код00110111100101010011

      Iстроки = 24 (бита).

      Iср = 24/9 ≈ 2,67 (бит).

      I1 = 2 (бита),

      I2 = I3 = I4 = I5 = I6 = I7 = 3 (бита).

      СимволОБРТ
      Номер1234
      Код011100101

      Iстроки = 11 (бит).

      Iср = 11/6 ≈ 1,83 (бит).

      I1 = 1 (бит),

      I2 = 2 (бита),

      I3 = I4 = 3 (бита).

      Процесс завершён. Сравните величины на этапе вычислений (прогноза) и те же величины после осуществления кодирования.

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

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

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

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

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

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

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

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

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

  • 10

    • Задача. Возьмём за основу текст задачи из Примера 8 (или Примера 9), но добавим в него следующее утверждение как правило грамматики: битовый идентификатор любого символа должен начинаться нулём.


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

      СимволАОСМХБВКЛТ
      Идентификатор000010000010100000000100100100

      Теперь практически не важно, чем оканчивается идентификатор символа, ведь он может начинаться только нулём! Здесь придётся исключить лишь окончание 11 (попробуйте объяснить, почему). По-прежнему нельзя делать последовательности 111 и 110 частью идентификаторов символов. Всего перечисленного, собственно, в таблице и не наблюдается.

      Выполним кодирование нашей фразы согласно таблице транслитерации:
      0111100111010111011100011110111110 _
      0001110111001111011100101110111110 _
      00111100001110011101111010011100111000111110.

      При распознавании битового кода нужно заканчивать интерпретацию очередного символа не тогда, когда встретится идентификатор "конец символа", а когда начнёт распознаваться следующий символ или когда встретится идентификатор конца слова сразу после прочтения идентификатора "конец символа". Для распознавания разобьём наш код на части, как это показано ниже:
      01111'00111'010111'0111'0001111'0111'110 _
      000111'0111'001111'0111'0010111'0111'110 _
      001111'0000111'00111'01111'0100111'00111'000111'110.

      Заметьте, что очередная часть кода начинается нулём или содержит идентификатор конца слова.



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


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

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

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



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