Задачи на кодирование текста
Задачи на кодирование текста сводятся к нескольким величинам: числу символов, размеру алфавита, числу бит на один символ и общему объёму сообщения. Перед решением полезно повторить кодировку символов и размер текстового файла, а затем внимательно определить, что именно требуется найти.
Основные понятия и единицы измерения
Алфавит — множество символов, которые используются для записи сообщений. В алфавит могут входить буквы, цифры, знаки препинания, пробел и специальные символы. Размер алфавита обозначают буквой \(N\) и измеряют количеством символов.
Алфавит — набор допустимых символов. Его мощность, или размер, \(N\) — число символов в этом наборе. Например, у двоичного алфавита мощность равна \(2\), а у русского алфавита без учёта регистра — обычно \(33\).
Информация в компьютере измеряется в битах и байтах. Один байт содержит 8 бит. При переводе единиц важно не смешивать количество символов и объём текста: 100 символов — это не обязательно 100 байт, потому что один символ может занимать несколько бит или байт.
Таблица кодировки символов связывает символы с их кодами. Кодировка задаёт, какие двоичные последовательности соответствуют буквам, цифрам и знакам. В простых экзаменационных задачах обычно сказано, сколько бит отводится на один символ, либо дана мощность алфавита.
Сколько бит нужно для одного символа
Если все символы кодируются двоичными последовательностями одинаковой длины \(i\) бит, то всего можно получить \(2^i\) различных кодов. Поэтому для алфавита из \(N\) символов должно выполняться \(2^i\ge N\).
Минимальное целое число бит на символ определяется условием \(2^i\ge N\). Поэтому \(i=\lceil\log_2N\rceil\). Если \(N\) является степенью двойки, логарифм получается целым.
Например, для алфавита из 16 символов нужно \(4\) бита, так как \(2^4=16\). Для алфавита из alfabet? 20 символов требуется уже \(5\) бит: \(2^4=16<20\), а \(2^5=32\ge20\). Символы могут использовать не все возможные комбинации, но длина кода должна позволять закодировать каждый символ.
Сколько бит нужно минимум для кодирования одного символа алфавита из 50 символов?
Размер сообщения по числу символов
Если сообщение содержит \(K\) символов, а каждый символ занимает \(i\) бит, то общий объём информации равен произведению \(K\) и \(i\). В условии может быть указано, учитывать ли пробелы, знаки препинания, перевод строки и регистр букв. Обычно каждый такой знак считается отдельным символом.
Если ответ требуется в байтах, сначала переводят биты в байты. Когда \(I\) не делится на 8, в реальном файле объём часто округляют вверх до целого числа байтов, если условие говорит о хранении файла. В учебных задачах иногда спрашивают именно информационный объём в битах — тогда округление не выполняют.
Для сообщения из \(K\) символов, закодированного по \(i\) бит на символ, \(I=K\cdot i\) бит. В байтах: \(I_{байт}=\frac{K\cdot i}{8}\), а для целого размера файла — \(\left\lceil\frac{K\cdot i}{8}\right\rceil\) байт.
При известном размере сообщения можно использовать обратные формулы:
Если найденное число символов не является целым, значит, в условии либо пропущена дополнительная информация, либо объём относится не только к тексту, либо используется округление.
Разобранный пример: алфавит и объём текста
В сообщении 120 символов. Используется алфавит из 100 символов. Найдите минимальный объём сообщения в байтах.
Ответ: 105 байт. Обратите внимание: нельзя использовать \(\log_2 100\) как число бит без округления. Получится примерно \(6{,}64\), но длина равномерного кода должна быть целым числом — 7 бит.
Как читать условие и выбирать формулу
- Определите, что считается символом: буква, цифра, пробел и знак препинания могут учитываться отдельно.
- Найдите мощность алфавита \(N\) или длину кода одного символа \(i\).
- Если дана мощность алфавита, подберите минимальное целое \(i\) по условию \(2^i\ge N\).
- Умножьте число символов на число бит на символ.
- Переведите результат в требуемые единицы: \(8\) бит = 1 байт, \(1024\) байта = 1 Кбайт, если в задаче используются двоичные единицы.
- Проверьте, не требуется ли округление размера файла вверх.
В задачах о готовой кодировке число бит на символ может быть задано напрямую: например, «каждый символ кодируется 2 байтами». Тогда размер алфавита вычислять не нужно. Если сказано, что используется 256 различных символов, минимальный код имеет 8 бит, потому что \(2^8=256\).
Составьте короткую таблицу величин: \(K\) — число символов, \(N\) — размер алфавита, \(i\) — бит на символ, \(I\) — объём сообщения. Это помогает не перепутать размер алфавита с количеством символов в сообщении.
Связь с системами счисления и кодировками
Двоичный код использует две цифры: 0 и 1. Поэтому последовательность длины \(i\) содержит \(2^i\) вариантов. Этот принцип связан с понятием цифры системы счисления и с правилом значения разряда числа. В задачах иногда встречаются коды, записанные не в двоичной, а в восьмеричной системе счисления. Тогда одна восьмеричная цифра соответствует трём битам, поскольку \(8=2^3\).
Современная кодировка UTF-8 использует переменное число байтов для разных символов. Поэтому формула «число символов умножить на постоянное число байт» применима к UTF-8 только тогда, когда в условии отдельно указано одинаковое представление символов или состав текста позволяет это определить. В школьных задачах чаще используется фиксированная длина кода.
1. Забывают учитывать пробелы и знаки препинания. 2. При \(N=20\) берут 4 бита, хотя \(2^4=16\) недостаточно. 3. Путают биты и байты: делить на 8 нужно только при переходе от битов к байтам. 4. Округляют число бит на символ вниз. 5. Для размера файла забывают округлить неполный байт вверх, если это требуется условием. 6. Считают символы глазами и пропускают повторяющиеся знаки или перевод строки.
Quick-test
Проверьте себя
Главное
- Мощность алфавита \(N\) — число допустимых символов.
- Минимальное число бит на символ: \(i=\lceil\log_2N\rceil\), то есть \(2^i\ge N\).
- Для сообщения из \(K\) символов объём равен \(I=K\cdot i\) бит.
- Один байт содержит 8 бит; при хранении файла неполный байт обычно округляют вверх.
- Всегда уточняйте, какие знаки считаются символами и задана ли кодировка напрямую.