Из Кириллицы в {0,1}

Мы рассматриваем представление текста, записанного в алфавите P текстом в алфавите Q. Когда алфавиты P и Q имеют одинаковое количество символов, то задача решается достаточно просто, - между алфавитами можно установить взаимно однозначное соответствие. Каждому символу из алфавита P ставится в соответствие символ алфавита Q. Конечно, даже в этом случае могут возникать проблемы, поскольку различных способов установления соответствия много. Нетрудно понять, что если в алфавиты содержат n символов, то существует n! различных способов установления соответствия – первому из символов алфавита P можно поставить в соответствие любой из n символов алфавита, для второго таких способов будет n-1, а всего – n!. Принятый способ кодирования можно записать в виде таблицы кодировки, состоящей из двух строк одинаковой длины. В первой из них символы алфавита P, во второй – соответствующие символы алфавита Q.

Задача: даны два алфавита P = {а, и, м, н, п} и { α, γ, ε, π, ω}. Дана таблица кодировки T₁ =<s₁, s₂>, где s₁ = "аимнп", s₂ = "?????". Тогда текст "мама и папа" будет закодирован следующим образом "απαπ ε γπγπ", полагая, что символ пробела не кодируется, сохраняя свое значение в обоих алфавитах.

Закодированный текст может быть однозначно декодирован, если известна таблица кодировки.

Рассмотрим теперь ситуацию, когда алфавиты P и Q имеют разную длину и символов в алфавите Q меньше чем символов алфавита P. Нас, прежде всего, будет интересовать ситуация, когда Q – алфавит компьютера, содержащий всего два символа {0, 1}.

Как представить текст в алфавите P мощности k > 2 текстом в алфавите Q = {0, 1}?

Решение простое. Нужно от алфавита Q перейти к алфавиту, символами которого будут слова длины n алфавита Q. Длина слов зависит от числа символов в алфавите P. Пусть алфавит P содержит k символов. Тогда, чтобы обеспечить возможность кодирования должно выполняться условие:

2ⁿ >= k

Эффективное кодирование предполагает минимальное значение n, удовлетворяющее этому условию.

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

Пусть мощность алфавита P равна k. Пусть N – число слов длины n в этом алфавите, M – число слов длины меньше n. Справедливы следующие соотношения:

Задача: Какова минимальная длина двоичного слова для кодировки строчных и прописных букв кириллицы.

Решение: Мощность алфавита k = 66. Кодирование возможно, когда n = 7. Это минимальное значение, при котором 2ⁿ > 66. Заметьте, словами длины 7 можно кодировать алфавит, содержащий 128 символов. При таком кодировании исходный алфавит помимо символов кириллицы может содержать и другие символы, используемые при записи текста – пробел, цифры, знаки препинания, знаки арифметических операций и другие полезные символы.

Какая же кодировка используется сегодня в реальной работе с текстами на компьютере. Тексты, обрабатываемые на компьютерах в разных странах, принадлежат разным естественным языкам – русскому и китайскому, английскому и индийскому – языков достаточно много, у каждого свой алфавит. Как справиться с задачей представления и обработки таких текстов? Долгое время для работы с текстами использовался 8-и битный код ASCII (American Standard Code Interchange Information). В этой кодировке каждый символ алфавита кодируется двоичным словом длины 8 – одним байтом. В этом случае исходный алфавит может включать 256 символов. Для представления текста одного языка такого алфавита вполне хватает. Для множества различных естественных языков мощности алфавита не хватает. Решение этой проблемы состояло в том, что алфавит разбивался на две половины (две страницы). Первая половина из 128 символов была постоянной и содержала символы латиницы, цифры и другие общие для всех языков символы. Другая кодовая страница была сменной, своя для каждого естественного языка – русского, немецкого и других языков. Долгое время такое решение проблемы устраивало пользователей компьютера. Код ASCII применяется и сегодня в некоторых ситуациях. Но с удешевлением и возрастанием объема доступной памяти компьютера стало ясно, что следует поступиться объемом памяти при кодировании текстов ради удобства работы с текстами, записанными на разных естественных языках, не используя никаких сменных таблиц.

Произошел переход к универсальной кодировке Unicode. Эта кодировка предполагает использование слов длиной 4 байта – то есть 32-х разрядных двоичных слов для хранения одного символа текста. Понятно, что при таком способе кодирования исходный алфавит может включать более 4-х миллиардов символов, что заведомо больше числа символов, используемых сегодня человечеством. Поэтому на практике такой мощный зарезервированный алфавит не применяется, а используется в Unicode – 2-х байтная кодировка. В этом случае алфавит включает 65536 символов, что хватает для алфавитов всех используемых языков, включая иероглифы.

Задача: Текст содержит 120 символов. При переходе от кодировки ASCII к двухбайтной кодировке Unicode насколько увеличится память, необходимая для хранения текста в памяти компьютера.

Решение: В кодировке ASCII текст занимает 120 байтов, в новой кодировке – в два раза больше. Ответ: 120 байтов.

Задача: Текст школьного учебника в среднем содержит 200 страниц, на каждой из которых в среднем 2000 символов. Какой объем памяти требуется для хранения текста в кодировке Unicode?

Решение: Объем учебника составляет 4*10⁵ символов, что требует для хранения в кодировке Unicode 8 * 10⁵ байтов. Поскольку 1 килобайт составляет 2¹⁰ = 1024 байта, то для хранения текста достаточно 800 Кб памяти.

Задача: Сколько текстов школьных учебников можно сохранить на флешке объемом 8 Гб?

Решение. Не будем мелочными при оценке количества учебников. Будем пренебрегать той небольшой положительной разницей между 210 и 1000, составляющей менее трех процентов. В дальнейшем при расчетах будем полагать, что килобайт примерно равен 1000 байтов, мегабайт равен 1000 килобайтов, а гигабайт равен 1000 мегабайтов. Поскольку для хранения текста одного учебника достаточно 0,8 Мб. (смотри предыдущую задачу), то в 8-и гигабайтах памяти можно сохранить тексты N учебников, где

N = 8000 /0, 8 = 10000

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

Задачи

Задача 1. Закодируйте текст, используя следующую таблицу кодировки

Задача 2. Декодируйте текст, закодированный с использованием следующей таблицы кодировки.

Задача 3. Текст был закодирован с использованием таблицы кодировки T₁. При передаче закодированного текста он был еще раз закодирован с использованием таблицы T₂. Какой текст получит получатель сообщения.

Задача 4. Декодируйте текст, дважды закодированный с использованием таблиц кодировки T₁ и T₂.

Задача 5. Сколько слов длины n в алфавите мощности k

Задача 6. Сколько слов длины меньше чем n в алфавите мощности k

Задача 7. Код кириллической строчной буквы "а" равен 1074 (в десятичной системе). Кодировка символов алфавита плотная. Это означает, что код символа алфавита на единицу больше кода предыдущего символа (алфавит упорядочен). В кириллице единственным исключением является буква ё, у которой особый код. Зная код буквы а, запишите в двоичной системе двухбайтовый код буквы м.

Задача 8. Оцените объем памяти, достаточный для хранения документа (Выбрать один из 4-х вариантов ответа)

Задача 9. Сколько документов можно сохранить в памяти заданного объема

Задача 10. Дан алфавит (цифры, греческий) Какова длина слова в двоичном алфавите