§24. Математические модели кодирования информации

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

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

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

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

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

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

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

Продемонстрированный в Примерах 1 и 2 способ транслитерации является только одной из возможностей для кодирования символов алфавитов в битовый код.

Из рассмотренных примеров следует, что совокупность из десяти произвольных символов, взятых из алфавита Примера 1, несёт в себе меньше информации, чем совокупность из десяти произвольных символов, взятых из алфавита Примера 2 (20 и 30 бит соответственно).

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

Равномерное кодирование — способ кодирования, при котором знаковая длина всех идентификаторов символов некоторого алфавита совпадает.

Тогда понятно, что такое, напротив, неравномерное кодирование.

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

В Примерах 1 и 2 было применено как раз равномерное кодирование. А вот как можно выполнить неравномерное кодирование, видно из Примера 3.

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

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

Покажем, что бывает, если при создании битовой последовательности использована нераспознаваемая грамматика (Пример 5).

А как вы думаете, какая строка символов закодирована последовательностью бит, предложенной в Примере 5? Какие правила грамматики русского языка помогли вам разобраться с этим вопросом?

Часто можно прочитать нераспознаваемый битовый код, в отличие от того, который был предложен в Примере 5. Но соответствующая ему символьная последовательность, скорее всего, не будет совпадать с той, которую кодировали, т. е. эта символьная последовательность не является единственной. Ознакомьтесь с Примером 6, чтобы увидеть такие случаи кодирования.

Однако не надо думать, что неравномерное кодирование является основой только лишь для нераспознаваемой грамматики. Подробнее оно описано в §26 и §27. Пока же поясним, как вообще грамматики можно классифицировать по признаку распознаваемости.

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

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

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

Слово интерпретация, встречаемое в определениях, буквально означает декодирование, а качественное значение — это символьная последовательность на некотором отвлечённом языке.

Данные определения относятся не только к кодированию в битовые последовательности.

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

Обратите внимание: неполное, или недостаточное знание образует нераспознаваемую грамматику! То же можно сказать о любой неполной информации.