Задание 7
тема 2 из 3

Алфавит, бит и объём текста

Символ алфавита из N знаков кодируют i битами, где i — наименьшее целое число, при котором 2i≥N2^i \ge N. Объём текста из K символов равен I=K⋅iI = K \cdot i бит, а в кодировке с кодом постоянной длины i задаёт сама кодировка: 8 бит в однобайтной, 16 бит в UTF-16. В ЕГЭ 1 Кбайт равен 1024 байтам, поэтому степени двойки решают большую часть расчётов в заданиях 7 и 11.

Реже в заданиях711На карте навыков

Алфавитный подход к количеству информации

Каждый символ текста кодируют одинаковым числом бит. Объём текста зависит только от числа символов и длины кода символа.

  • 1 байт — 8 бит. 1 Кбайт — 1024 байта, или 2132^{13} бит. 1 Мбайт — 1024 Кбайт, или 2232^{23} бит.
  • Алфавит из NN символов: на символ нужно наименьшее целое ii, при котором 2i≥N2^i \ge N. Кодом из ii бит можно записать 2i2^i разных символов.
  • Объём текста из KK символов: I=K⋅iI = K \cdot i бит. Пробелы и знаки препинания — тоже символы.
  • Кодировка задаёт ii сама: однобайтная — 8 бит, UTF-16 — 16 бит, UTF-32 — 32 бита. В UTF-8 длина кода от 1 до 4 байт.
  • Равновероятные варианты: формула Хартли i=log⁡2Ni = \log_2 N. Разные вероятности: формула Шеннона.

Бит, байт и кратные единицы

Бит — наименьшая единица количества информации: одна двоичная цифра, 0 или 1. Байт — восемь бит. Кратные единицы в информатике образуют умножением на 1024=2101024 = 2^{10}: 1 Кбайт — 1024 байта, 1 Мбайт — 1024 Кбайт, 1 Гбайт — 1024 Мбайт. Так в ЕГЭ: в инструкции к экзамену сказано, что Кбайт и Мбайт связаны с байтом степенью двойки.

Чтобы перевести объём в меньшую единицу, умножьте его на 1024 (байты в биты — на 8). Чтобы перевести в большую, разделите. Удобно считать в степенях двойки: 1 Кбайт =210⋅23=213= 2^{10} \cdot 2^3 = 2^{13} бит.

Пример

Сколько бит в 5 Кбайт? Сколько Кбайт в 2202^{20} бит?

  1. 1.5 Кбайт =5⋅1024= 5 \cdot 1024 байт =5120= 5120 байт =5120⋅8=40 960= 5120 \cdot 8 = 40\,960 бит.
  2. 2.2202^{20} бит =220:23=217= 2^{20} : 2^3 = 2^{17} байт =217:210=27=128= 2^{17} : 2^{10} = 2^7 = 128 Кбайт.

Ответ: 40 96040\,960 бит и 128 Кбайт

Единицы количества информации

ЕдиницаВ байтахВ битах
1 байт123=82^3 = 8
1 Кбайт210=10242^{10} = 1024213=81922^{13} = 8192
1 Мбайт220=1 048 5762^{20} = 1\,048\,5762232^{23}
1 Гбайт2302^{30}2332^{33}

Мощность алфавита и длина кода символа

Алфавит — набор символов, которыми пишут сообщения. Мощность алфавита NN — число символов в нём. Двоичный код длины ii имеет 2i2^i вариантов, поэтому код из ii бит различает не больше 2i2^i символов. Чтобы закодировать алфавит из NN символов кодом одинаковой длины, нужно наименьшее целое ii, при котором 2i≥N2^i \ge N. Если NN — степень двойки, то i=log⁡2Ni = \log_2 N точно, иначе берут следующую целую степень.

Обратная задача: если на символ отвели ii бит, в алфавите может быть не больше 2i2^i символов. В программе ii находят циклом: пока 2i2^i меньше NN, увеличивайте ii. Для N=33N = 33 программа печатает 6.

Пример

Сколько бит нужно на символ, чтобы закодировать 33 буквы русского алфавита кодом одинаковой длины?

  1. 1.Степени двойки рядом с 33: 25=322^5 = 32 и 26=642^6 = 64.
  2. 2.32<3332 < 33, пяти бит не хватает. 64≥3364 \ge 33, шести бит хватает.

Ответ: 6 бит

Степени двойки

i2 в степени ii2 в степени i
127128
248256
389512
416101024
532112048
664124096

Информационный объём текста

Информационный объём сообщения — число бит, которое занимает его код. Если каждый из KK символов кодируют ii битами, объём равен I=K⋅iI = K \cdot i бит. Считайте все символы: буквы, цифры, пробелы, знаки препинания. Чтобы получить байты, разделите на 8.

Длину кода ii берут из условия. Если дана мощность алфавита, ii находят по длине кода символа. Если дана кодировка, ii задаёт она: в 16-битной кодировке каждый символ занимает 2 байта.

Пример

Сообщение из 120 символов записано алфавитом из 20 символов кодом одинаковой минимальной длины. Найдите его объём в байтах.

  1. 1.24=16<20≤32=252^4 = 16 < 20 \le 32 = 2^5, значит i=5i = 5 бит.
  2. 2.I=120⋅5=600I = 120 \cdot 5 = 600 бит.
  3. 3.600:8=75600 : 8 = 75 байт.

Ответ: 75 байт

Закон аддитивности информации

Закон аддитивности: если выбор состоит из двух независимых шагов, количество информации о результате равно сумме количеств информации о каждом шаге. Число вариантов при этом перемножается: N=N1⋅N2N = N_1 \cdot N_2, а длины кодов складываются: log⁡2(N1⋅N2)=log⁡2N1+log⁡2N2\log_2 (N_1 \cdot N_2) = \log_2 N_1 + \log_2 N_2.

Поэтому объём текста — сумма объёмов его символов, а код слова из KK символов алфавита мощности 2i2^i имеет длину K⋅iK \cdot i и различает 2K⋅i2^{K \cdot i} слов.

Пример

Место в зале задают номером ряда (8 рядов) и номером кресла в ряду (16 кресел). Сколько бит информации в сообщении о месте?

  1. 1.Ряд: log⁡28=3\log_2 8 = 3 бита. Кресло: log⁡216=4\log_2 16 = 4 бита.
  2. 2.По закону аддитивности 3+4=73 + 4 = 7 бит.
  3. 3.Проверка: мест 8⋅16=128=278 \cdot 16 = 128 = 2^7.

Ответ: 7 бит

Информация и вероятность: формулы Хартли и Шеннона

Формула Хартли: сообщение о том, что произошло одно из NN равновероятных событий, несёт i=log⁡2Ni = \log_2 N бит. Сообщение о событии с вероятностью pp несёт i=log⁡21pi = \log_2 \dfrac{1}{p} бит: чем меньше вероятность, тем больше информации.

Формула Шеннона даёт среднее количество информации на одно сообщение, когда вероятности событий разные: H=−(p1log⁡2p1+p2log⁡2p2+…+pNlog⁡2pN)H = -(p_1 \log_2 p_1 + p_2 \log_2 p_2 + \ldots + p_N \log_2 p_N), где p1,…,pNp_1, \ldots, p_N — вероятности NN событий. Если все pk=1Np_k = \dfrac{1}{N}, формула Шеннона даёт log⁡2N\log_2 N, то есть формулу Хартли.

Пример

В коробке 4 белых, 2 красных и 2 синих шара. Достают один шар. Сколько информации в сообщении «достали красный шар»? Сколько информации в среднем несёт сообщение о цвете?

  1. 1.Вероятности: белый 48=12\dfrac{4}{8} = \dfrac{1}{2}, красный 14\dfrac{1}{4}, синий 14\dfrac{1}{4}.
  2. 2.«Красный»: log⁡24=2\log_2 4 = 2 бита.
  3. 3.Среднее по Шеннону: 12⋅1+14⋅2+14⋅2=1,5\dfrac{1}{2} \cdot 1 + \dfrac{1}{4} \cdot 2 + \dfrac{1}{4} \cdot 2 = 1{,}5 бита.

Ответ: 2 бита и 1,51{,}5 бита

Кодировки текста: ASCII, однобайтные, Unicode

Кодировка — таблица, в которой каждому символу соответствует числовой код. ASCII — 7-битная кодировка из 128 символов: латинские буквы, цифры, знаки препинания, управляющие символы. Однобайтные кодировки (Windows-1251, КОИ-8) отводят на символ 8 бит, то есть 256 символов: первые 128 совпадают с ASCII, остальные отданы национальному алфавиту, например кириллице.

Unicode — стандарт, который даёт номер каждому символу всех письменностей. Номера записывают кодом разной формы: в UTF-16 символы основных алфавитов занимают 16 бит, в UTF-32 каждый символ — 32 бита. В задачах ЕГЭ фраза «в кодировке, где каждый символ кодируется 16 битами» задаёт i=16i = 16. В Python номер символа даёт ord('A'): 65, а ord('Я') — 1071.

Пример

Строку «Я помню чудное мгновенье» записали в кодировке, где каждый символ занимает 16 бит. Найдите объём строки в байтах.

  1. 1.Считаем символы вместе с пробелами: «Я», «помню», «чудное», «мгновенье» — 1+5+6+9=211 + 5 + 6 + 9 = 21 буква и 3 пробела, всего 24 символа.
  2. 2.I=24⋅16=384I = 24 \cdot 16 = 384 бита.
  3. 3.384:8=48384 : 8 = 48 байт.

Ответ: 48 байт

Длина кода символа в кодировках

КодировкаБит на символСимволов
ASCII7 (хранят в байте)128
Windows-1251, КОИ-88256
UTF-8от 8 до 32все символы Unicode
UTF-1616 для основных алфавитов, иначе 32все символы Unicode
UTF-3232все символы 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. 1.Кириллица: «Привет» и «мир» — 6+3=96 + 3 = 9 букв по 2 байта, всего 18 байт.
  2. 2.ASCII: запятая, пробел и знак «!» — 3 символа по 1 байту.
  3. 3.18+3=2118 + 3 = 21 байт.

Ответ: 21 байт

Проверьте себя

00

Потренируйте навык

Все задания на этот навык

Решать