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


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

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

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

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

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

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

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

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

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

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

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

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


§23. Кодирование в знаковые системы


doPDF

§23. Кодирование в знаковые системы

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

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

    • Известно, что радиоактивное излучение распадается в магнитном поле на три составляющих — потоки ядер гелия, электронов и электромагнитные волны с очень малой длиной. Каждому типу излучения соответствует свой символ, заимствованный из греческого алфавита: α, β и γ. Эти символы используются и при записи ядерных реакций, т. е. в условиях формального языка.

Остановимся для более подробного определения знака и символа в графической интерпретации.

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

В естественных языках используются понятия буквы и цифры.

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

  • 1

    • Имеется алфавит, содержащий всего 2 знака:

      a¨

      Обращаем внимание на то обстоятельство, что в данном примере умлаут не существует в качестве самостоятельно используемого знака (только диакритический), так что из символов этого алфавита можно составить 2 используемых символа: 'a' и 'ä'. При этом символ 'a' можно считать знаком, а вот символ 'ä' знаком считать нельзя. Мощность представленного алфавита равна 2.

  • 2

    • Имеется алфавит, содержащий 4 знака:

      auö¨

      В данном примере умлаут является диакритическим знаком, так что из символов этого алфавита можно составить 5 используемых символов: 'a', 'u', 'ö', 'ä' и 'ü'. При этом символы 'a', 'u' и 'ö' можно считать знаком (заметьте, что самостоятельного символа 'o' в алфавите нет), а символы 'ä' и 'ü' знаками считать нельзя. Мощность представленного алфавита равна 5.

  • 3

    • Имеется алфавит, содержащий 4 знака:

      auü¨

      В данном примере умлаут является диакритическим знаком, так что из символов этого алфавита можно составить 4 используемых символа: 'a', 'u', 'ü' и 'ä'. При этом символы 'a' и 'u' можно считать знаком. Символ 'ü' можно считать знаком, только если он использован как самостоятельный знак алфавита. В противном случае он, так же как и символ 'ä', является составным, потому знаками эти два символа уже считаться не будут. Мощность представленного алфавита равна 4.

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

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

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

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

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

Строки как совокупности символов в традиционном понимании, например, для русского или любого европейского языка, прежде всего характеризуются тем, что читаются они (и, самое главное, образуются, т. е. последовательно составляются из символов) слева направо, и по тому же принципу сортируются. Это означает, что в процессе расположения двух слов в алфавитном порядке мы смотрим на их буквы слева направо до тех пор, пока они не перестанут совпадать, и когда находим такие несовпадающие буквы в n-ой позиции, то можем расставить слова согласно порядку букв в алфавите в n-ой позиции слов (см. Пример 6). Первая строка считается больше второй, если при расположении этих строк в алфавитном порядке она занимает место после второй.

Если слово, представленное первой строкой, целиком является частью другого слова, представленного второй строкой, и вторая строка длиннее первой, то считается, что второе слово больше первого. Располагается оно, соответственно, после первого при создании последовательности в алфавитном порядке (Пример 7).

Заметим, что нулевой (т. е. отсутствующий) символ можно вставить в любое место строки и в любом количестве, и от этого строка нисколько не изменит своего представления. Но пользоваться этим символом следует лишь при необходимости, когда его наличие обретает некий смысл (как было показано в Примере 7). К тому же нужно помнить, что нулевой символ используется преимущественно техническими средствами, выполняющими анализ строковых выражений, для которых он может иметь ещё один смысл: "конец чтения строки"… По этой причине не сто́ит перегружать этими символами строки без необходимости.

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

Чтобы принцип сравнения чисел стал таким же, как принцип сравнения строк, т. е. их сравнение осуществлялось бы слева направо, требуется выровнять числа относительно десятичной запятой вправо нулями так, чтобы в их целых частях оказалось одинаковое количество разрядов, т. е. дописать необходимое количество лидирующих нулей (см. Пример 8). Дробные же их части анализируются точно так же, как и строки.

  • 8

    • Задача. Сравнить числа 12,05 и 111,7.


      Решение. Выровним нулями вправо первое число так, чтобы в его целой части содержалось столько же цифр, сколько в целой части второго числа. Получим 012,05. Рассматривая теперь цифры чисел попарно слева направо, находим, что первая цифра первого числа меньше первой цифры второго числа (0 < 1), значит, 12,05 < 111,7.

Если выравнивание вправо нулями не сделать, а просто воспользоваться принципом сравнения строк применительно к числам, то мы можем получить, что, например, 17 > 1597! Кстати, если рассматривать данные числа как строки, то мы придём как раз к такому выводу: действительно, '17' > '1597'.

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

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

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

  • 9

    • Задача. Дана таблица транслитерации:

      Символам
      Идентификатор01010

      Закодировать с её помощью слово 'мама'.


      Решение. Подставляя вместо каждого символа исходной строки его идентификатор, получаем 1001010010.

      Несмотря на то, что все идентификаторы интерпретируются как числа, мы не можем сказать о новом порядке следования символов алфавита, поскольку неясно, какое из "чисел" больше: 10 или 010. Но, если идентификаторы интерпретировать как строки, то '010' < '10', так что по-прежнему 'а' < 'м'.

  • 10

    • Задача. Дана таблица транслитерации:

      Символам
      Идентификатор10001

      Закодировать с её помощью слово 'мама'.


      Решение. Подставляя вместо каждого символа исходной строки его идентификатор, получаем 0011000110.

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

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

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

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

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

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

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

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



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


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

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

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



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