Измерение информации
Количество информации измеряют в битах и байтах. Чтобы решить задачу, нужно понять, что именно дано: число возможных символов, длина сообщения, размер файла или число равновероятных вариантов.
Что измеряют и в каких единицах
Единица информации — бит. Один бит хранит один из двух нұсқа: 0 или 1. Восьми битам соответствует один байт. На практике также используют килобайты, мегабайты и другие единицы, но их перевод нужно выполнять по условию задачи: иногда используются степени 2, а иногда — степени 10.
Количество информации — числовая характеристика сведений, полученных при выборе одного варианта из нескольких возможных. Чем больше число возможных вариантов, тем больше информации содержит сообщение о выбранном варианте.
В задачах встречаются три основные величины: \(N\) — число символов алфавита или возможных сообщений, \(K\) — число символов в сообщении, \(I\) — количество информации. Если речь идёт о файле, дополнительно могут быть указаны размер в байтах, число символов и длина кода одного символа.
Количество информации в одном символе
Если все символы алфавита кодируются одинаковым числом бит и алфавит содержит \(N\) символов, то количество информации в одном символе равно двоичному логарифму числа символов. Это связано с тем, что \(i\) бит позволяют закодировать \(2^i\) различных комбинаций.
Если \(N=2^i\), то один символ алфавита несёт \(i\) бит информации. Для равномерного двоичного кода длина кода символа равна \(i=\log_2 N\).
- Алфавит из 2 символов: \(i=1\) бит.
- Алфавит из 4 символов: \(i=2\) бита.
- Алфавит из 8 символов: \(i=3\) бита.
- Алфавит из 256 символов: \(i=8\) бит, то есть 1 байт.
Для вычислений полезно помнить степени двойки: \(2^0=1\), \(2^1=2\), \(2^2=4\), \(2^3=8\), \(2^4=16\), \(2^5=32\), \(2^6=64\), \(2^7=128\), \(2^8=256\), \(2^{10}=1024\).
В школьных задачах обычно дают число символов, равное степени двойки. Если \(N\) не является степенью двойки, равномерный код фиксированной длины должен иметь длину \(\lceil\log_2 N\rceil\) бит, потому что комбинаций должно хватить для всех символов. Например, для 5 символов нужны 3 бита: 2 бит дают только 4 комбинации.
Сообщение из нескольких символов
Если сообщение состоит из \(K\) символов, а каждый символ кодируется \(i\) битами, то общее количество информации равно произведению длины сообщения на количество информации в одном символе.
Эта формула применяется, когда символы кодируются независимо и одинаковым числом бит. Если известны только \(I\) и \(K\), можно найти длину кода бір символа: \(i=I/K\). Если известны \(I\) и \(i\), число символов в сообщении: \(K=I/i\).
Алфавит содержит 32 символа. Сколько бит нужно для кодирования бір символа?
Файлы, текст и кодировка
Текстовый файл можно рассматривать как последовательность символов. Если в кодировке символов каждый символ занимает \(i\) бит, а текст содержит \(K\) символов, то размер текста в битах вычисляется по формуле \(I=K\cdot i\). Затем результат при необходимости переводят в байты и более крупные единицы.
Например, в ASCII обычно используется 8 бит на символ, поэтому один символ занимает 1 байт. В Юникоде размер символа зависит от конкретной кодировки и условия задачи; нельзя автоматически считать любой Unicode-символ равным одному байту.
Не путайте число символов и количество информации. Сообщение из 100 символов не обязательно содержит 100 бит. Сначала найдите длину кода одного символа. Также не забывайте переводить биты в байты делением на 8, а байты в биты умножением на 8. Если в условии сказано, что пробелы и знаки препинания входят в текст, их тоже нужно считать символами.
Разобранный пример
Алфавит содержит 64 символа. Сообщение состоит из 120 символов. Определите информационный объём сообщения в битах и байтах.
Ответ: сообщение содержит 720 бит, или 90 байт. Важно не использовать число 64 как количество бит: 64 — это число возможных символов, а не длина их кода.
Количество информации по числу равновероятных нұсқа
Иногда задача описывает не символ, а событие: например, выбор одного файла из каталога, одной карточки или одного номера. Если имеется \(N\) равновероятных нұсқа, то информация о выборе бір нұсқа вычисляется так же:
Если выполняется несколько независимых выборов, число комбинаций перемножается. Поэтому логарифм произведения превращается в сумму, а количество информации складывается. Для двух независимых выборов с \(N_1\) и \(N_2\) вариантами получаем \(I=\log_2(N_1N_2)\).
Если сообщение задаётся последовательностью независимых выборов, число возможных сообщений равно произведению числа вариантов на каждом шаге: \(N=N_1\cdot N_2\cdot\ldots\cdot N_K\). Количество информации равно \(I=\log_2 N\).
Это правило связано с формулой количества информации и двоичным логарифмом. При решении можно либо сначала перемножить варианты, либо сразу сложить известные количества бит.
Как решать тапсырма о размере данных
- Выписать, что означает каждая величина: \(N\), \(K\), \(i\), \(I\) или размер файла.
- Определить число нұсқа или символов в алфавите.
- Іздеу длину кода символа: \(i=\log_2N\), если код равномерный.
- Умножить \(i\) на число символов \(K\).
- Перевести результат в требуемые единицы: биты, байты, килобайты.
- Тексеру ответ: размер в байтах должен быть в 8 раз меньше размера в битах.
Если число вариантов уже записано как степень двойки, логарифм считать не нужно: показатель степени и есть число бит. Например, \(N=2^{12}\) сразу даёт \(i=12\) бит.
Проверка знаний
Quick-test
Главное
- Количество информации в одном символе алфавита из \(N\) равновероятных символов: \(i=\log_2N\).
- Для сообщения из \(K\) символов: \(I=K\cdot i=K\cdot\log_2N\).
- Восемь бит составляют один байт; при переводе битов в байты делят на 8.
- В текстовом файле нужно учитывать все символы, включая пробелы и знаки препинания, если это указано в условии.
- Если число нұсқа не является степенью двойки, для фиксированного равномерного кода берут \(\lceil\log_2N\rceil\) бит.