Код символа и память для записи
Почему число бит определяется степенями двойки, где округляется объём записи и как восстановить длину номера или мощность алфавита.
Двоичный код заменяет каждый разрешённый символ последовательностью нулей и единиц. Для расчёта памяти важны два разных ограничения: код должен различать все символы, а выделенная память должна вмещать запись целиком. Первое определяет число бит на символ, второе — число байт на запись.
Сколько символов различает код
Один бит принимает два значения: 0 или 1. Из двух битов получаются четыре кода: 00,01,10,11. Каждый следующий бит удваивает количество вариантов. Поэтому код длиной i бит даёт 2^i различных последовательностей.
Набор разрешённых символов называется алфавитом, а их количество — мощностью алфавита. Обозначим его A. Каждому символу нужен свой код, поэтому при одинаковой длине всех кодов необходимо A\le2^i. Для минимального числа бит и алфавита хотя бы из двух символов выполняется:
2^{i-1}<A\le2^i.
Правая граница говорит, что кодов достаточно. Левая — что на один бит меньше уже не хватило бы.
| Символов в алфавите | Минимум бит на символ |
|---|---|
| 2 | 1 |
| 3–4 | 2 |
| 5–8 | 3 |
| 9–16 | 4 |
| 17–32 | 5 |
| 33–64 | 6 |
| 65–128 | 7 |
Алфавиты из 33 и 64 символов требуют одинаково по 6 бит на символ. Добавление 65-го символа увеличивает код до 7 бит. Размер кода меняется ступенями, поэтому пропорция между мощностью алфавита и числом бит не работает.
Это правило описывает равномерное посимвольное кодирование. Ограничения на состав пароля, например наличие хотя бы одной цифры, не разрешают уменьшать код отдельных символов. Сначала учитывается весь разрешённый алфавит.
От битов к целым байтам
Пусть номер содержит L символов по i бит. Для его кода нужно Li бит. Байт вмещает 8 бит. Если под каждый номер выделяется целое число байт, должно выполняться 8B\ge Li, где B — число выделенных байт.
Наименьшее подходящее значение:
B=\left\lceil\frac{Li}{8}\right\rceil.
Знак «потолок» нужен, потому что даже один лишний бит требует ещё одного байта. Например, 16 бит занимают 2 байта, а 17 бит — уже 3.
Округляется именно тот объект, которому условие выделяет целые байты. Учебный пример: два номера содержат по 9 бит. Каждому нужно 2 байта, вместе — 4. Общая длина кодов равна 18 битам, которые можно было бы упаковать в 3 байта, но тогда номера делили бы один байт между собой. Это уже другой способ хранения.
По той же причине символ размером 3 бита не занимает целый байт сам по себе. Три таких символа образуют 9 бит и требуют 2 байта на весь номер, а не 3 байта.
Запись с дополнительными полями
Запись может включать номер и дополнительные сведения, например параметры пользователя. Если номер занимает B байт, а дополнительные сведения — D байт, одна запись занимает B+D байт. Для n одинаковых записей общий объём:
V=n(B+D).
Здесь V, B и D измеряются в байтах. Если известен общий объём, дополнительные сведения находятся так: D=V/n-B. Сначала выделяется одна запись, затем из неё вычитается номер.
Когда число байт дополнительных сведений целое, результат их прибавления не требует нового округления. Если условие задаёт отдельное правило хранения каждого поля, применяется именно это правило.
Что меняется в обратных задачах
При известном алфавите фиксировано число бит на символ. Рост длины номера увеличивает число бит, но не обязательно сразу меняет выделенные байты. Например, при 3 битах на символ номера длиной 3, 4 и 5 символов занимают по 2 байта: их коды содержат 9, 12 и 15 бит.
Известное количество байт поэтому задаёт диапазон длин. Ровно B байт необходимо тогда, когда 8(B-1)<Li\le8B. Код не помещается в B-1 байт, но помещается в B байт. В этом диапазоне выбирается целое L, которое требуется условием.
При неизвестном алфавите сначала определяется подходящее число бит i, затем — граница алфавита. Если минимальный код имеет длину i, то:
- наименьшая мощность алфавита равна 2^{i-1}+1;
- наибольшая — 2^i.
Например, 5 бит позволяют различить до 32 символов. Минимальный алфавит, которому нужны именно 6 бит, содержит 33 символа. Алфавит из 64 символов тоже укладывается в 6 бит, но это верхняя граница.
Границы объёма
| Фраза в условии | Ограничение |
|---|---|
| Более T | V>T |
| Не менее T | V\ge T |
| Менее T | V<T |
| Не более T | V\le T |
Объём V и граница T должны быть в одинаковых единицах. Проверка в целых байтах сохраняет точность: равенство границе не теряется из-за округления десятичного частного.
Для минимального ответа проверяются найденное значение и предыдущее допустимое целое; для максимального — найденное и следующее. Такая проверка достаточна здесь, потому что при фиксированных остальных данных увеличение длины номера или числа бит на символ не уменьшает объём памяти.
Применение в заданиях
Как по общему объёму отделить пароль от дополнительных сведений? Как определить минимальную длину номера или минимальный алфавит, сохранив округление и строгую границу?
Эти переходы показаны на реальных условиях в статье «Задание №11. Идентификаторы и объём памяти».