Алфавит, бит и объём текста
Символ алфавита из N знаков кодируют i битами, где i — наименьшее целое число, при котором . Объём текста из K символов равен бит, а в кодировке с кодом постоянной длины i задаёт сама кодировка: 8 бит в однобайтной, 16 бит в UTF-16. В ЕГЭ 1 Кбайт равен 1024 байтам, поэтому степени двойки решают большую часть расчётов в заданиях 7 и 11.
Алфавитный подход к количеству информации
Каждый символ текста кодируют одинаковым числом бит. Объём текста зависит только от числа символов и длины кода символа.
- 1 байт — 8 бит. 1 Кбайт — 1024 байта, или бит. 1 Мбайт — 1024 Кбайт, или бит.
- Алфавит из символов: на символ нужно наименьшее целое , при котором . Кодом из бит можно записать разных символов.
- Объём текста из символов: бит. Пробелы и знаки препинания — тоже символы.
- Кодировка задаёт сама: однобайтная — 8 бит, UTF-16 — 16 бит, UTF-32 — 32 бита. В UTF-8 длина кода от 1 до 4 байт.
- Равновероятные варианты: формула Хартли . Разные вероятности: формула Шеннона.
Бит, байт и кратные единицы
Бит — наименьшая единица количества информации: одна двоичная цифра, 0 или 1. Байт — восемь бит. Кратные единицы в информатике образуют умножением на : 1 Кбайт — 1024 байта, 1 Мбайт — 1024 Кбайт, 1 Гбайт — 1024 Мбайт. Так в ЕГЭ: в инструкции к экзамену сказано, что Кбайт и Мбайт связаны с байтом степенью двойки.
Чтобы перевести объём в меньшую единицу, умножьте его на 1024 (байты в биты — на 8). Чтобы перевести в большую, разделите. Удобно считать в степенях двойки: 1 Кбайт бит.
Пример
Сколько бит в 5 Кбайт? Сколько Кбайт в бит?
- 1.5 Кбайт байт байт бит.
- 2. бит байт Кбайт.
Ответ: бит и 128 Кбайт
Единицы количества информации
| Единица | В байтах | В битах |
|---|---|---|
| 1 байт | 1 | |
| 1 Кбайт | ||
| 1 Мбайт | ||
| 1 Гбайт |
Мощность алфавита и длина кода символа
Алфавит — набор символов, которыми пишут сообщения. Мощность алфавита — число символов в нём. Двоичный код длины имеет вариантов, поэтому код из бит различает не больше символов. Чтобы закодировать алфавит из символов кодом одинаковой длины, нужно наименьшее целое , при котором . Если — степень двойки, то точно, иначе берут следующую целую степень.
Обратная задача: если на символ отвели бит, в алфавите может быть не больше символов. В программе находят циклом: пока меньше , увеличивайте . Для программа печатает 6.
Пример
Сколько бит нужно на символ, чтобы закодировать 33 буквы русского алфавита кодом одинаковой длины?
- 1.Степени двойки рядом с 33: и .
- 2., пяти бит не хватает. , шести бит хватает.
Ответ: 6 бит
Степени двойки
| i | 2 в степени i | i | 2 в степени i |
|---|---|---|---|
| 1 | 2 | 7 | 128 |
| 2 | 4 | 8 | 256 |
| 3 | 8 | 9 | 512 |
| 4 | 16 | 10 | 1024 |
| 5 | 32 | 11 | 2048 |
| 6 | 64 | 12 | 4096 |
| 13 | 8192 | 16 | 65 536 |
| 14 | 16 384 | 20 | 1 048 576 |
| 15 | 32 768 | 24 | 16 777 216 |
Информационный объём текста
Информационный объём сообщения — число бит, которое занимает его код. Если каждый из символов кодируют битами, объём равен бит. Считайте все символы: буквы, цифры, пробелы, знаки препинания. Чтобы получить байты, разделите на 8.
Длину кода берут из условия. Если дана мощность алфавита, находят по длине кода символа. Если дана кодировка, задаёт она: в 16-битной кодировке каждый символ занимает 2 байта.
Пример
Сообщение из 120 символов записано алфавитом из 20 символов кодом одинаковой минимальной длины. Найдите его объём в байтах.
- 1., значит бит.
- 2. бит.
- 3. байт.
Ответ: 75 байт
Закон аддитивности информации
Закон аддитивности: если выбор состоит из двух независимых шагов, количество информации о результате равно сумме количеств информации о каждом шаге. Число вариантов при этом перемножается: , а длины кодов складываются: .
Поэтому объём текста — сумма объёмов его символов, а код слова из символов алфавита мощности имеет длину и различает слов.
Пример
Место в зале задают номером ряда (8 рядов) и номером кресла в ряду (16 кресел). Сколько бит информации в сообщении о месте?
- 1.Ряд: бита. Кресло: бита.
- 2.По закону аддитивности бит.
- 3.Проверка: мест .
Ответ: 7 бит
Информация и вероятность: формулы Хартли и Шеннона
Формула Хартли: сообщение о том, что произошло одно из равновероятных событий, несёт бит. Сообщение о событии с вероятностью несёт бит: чем меньше вероятность, тем больше информации.
Формула Шеннона даёт среднее количество информации на одно сообщение, когда вероятности событий разные: , где — вероятности событий. Если все , формула Шеннона даёт , то есть формулу Хартли.
Пример
В коробке 4 белых, 2 красных и 2 синих шара. Достают один шар. Сколько информации в сообщении «достали красный шар»? Сколько информации в среднем несёт сообщение о цвете?
- 1.Вероятности: белый , красный , синий .
- 2.«Красный»: бита.
- 3.Среднее по Шеннону: бита.
Ответ: 2 бита и бита
Кодировки текста: ASCII, однобайтные, Unicode
Кодировка — таблица, в которой каждому символу соответствует числовой код. ASCII — 7-битная кодировка из 128 символов: латинские буквы, цифры, знаки препинания, управляющие символы. Однобайтные кодировки (Windows-1251, КОИ-8) отводят на символ 8 бит, то есть 256 символов: первые 128 совпадают с ASCII, остальные отданы национальному алфавиту, например кириллице.
Unicode — стандарт, который даёт номер каждому символу всех письменностей. Номера записывают кодом разной формы: в UTF-16 символы основных алфавитов занимают 16 бит, в UTF-32 каждый символ — 32 бита. В задачах ЕГЭ фраза «в кодировке, где каждый символ кодируется 16 битами» задаёт . В Python номер символа даёт ord('A'): 65, а ord('Я') — 1071.
Пример
Строку «Я помню чудное мгновенье» записали в кодировке, где каждый символ занимает 16 бит. Найдите объём строки в байтах.
- 1.Считаем символы вместе с пробелами: «Я», «помню», «чудное», «мгновенье» — буква и 3 пробела, всего 24 символа.
- 2. бита.
- 3. байт.
Ответ: 48 байт
Длина кода символа в кодировках
| Кодировка | Бит на символ | Символов |
|---|---|---|
| ASCII | 7 (хранят в байте) | 128 |
| Windows-1251, КОИ-8 | 8 | 256 |
| UTF-8 | от 8 до 32 | все символы Unicode |
| UTF-16 | 16 для основных алфавитов, иначе 32 | все символы Unicode |
| UTF-32 | 32 | все символы Unicode |
Код переменной длины в UTF-8
В UTF-8 длина кода символа зависит от его номера в Unicode. Символ ASCII (латинская буква, цифра, пробел, знак препинания) занимает 1 байт. Буква кириллицы — 2 байта. Большинство других символов, например иероглифы, — 3 байта, а редкие символы и эмодзи — 4 байта. Поэтому объём текста в UTF-8 считают по группам символов и складывают.
В Python объём строки в байтах даёт len(s.encode('utf-8')), а число символов — len(s). Программа ниже печатает 12 и 21.
Пример
Сколько байт занимает строка «Привет, мир!» в кодировке UTF-8?
- 1.Кириллица: «Привет» и «мир» — букв по 2 байта, всего 18 байт.
- 2.ASCII: запятая, пробел и знак «!» — 3 символа по 1 байту.
- 3. байт.
Ответ: 21 байт
Проверьте себя
00