Приближение равной вероятности символов в тексте

Если допустить, что все символы алфавита в любом тексте появляются с одинаковой частотой, то информационный вес всех символов будет одинаковым. Пусть N – мощность алфавита. Тогда доля любого символа в тексте составляет 1/ N -ю часть текста. По определению вероятности эта величина равна вероятности появления символа в каждой позиции текста:

p = 1/ N

Согласно формуле К. Шеннона, количество информации, которое несет символ, вычисляется следующим образом:

i = log2(1/ p) = log2 N (бит) (2)

Следовательно, информационный вес символа (i) и мощность алфавита (N) связаны между собой по формуле Хартли 2 ⁱ = N.

Зная информационный вес одного символа (i) и размер текста, выраженный количеством символов (K), можно вычислить информационный объем текста по формуле:

I = K · i (3)

Эта формула есть частный вариант формулы (1), в случае, когда все символы имеют одинаковый информационный вес.

Из формулы (2) следует, что при N = 2 (двоичный алфавит) информационный вес одного символа равен 1 биту.

С позиции алфавитного подхода к измерению информации 1 бит – это информационный вес символа из двоичного алфавита.

Более крупной единицей измерения информации является байт.

1 байт – это информационный вес символа из алфавита мощностью 256.

Поскольку 256 = 2⁸, то из формулы Хартли следует связь между битом и байтом:

2 ⁱ = 256 = 2⁸

Отсюда: i = 8 бит = 1 байт

Для представления текстов, хранимых и обрабатываемых в компьютере, чаще всего используется алфавит мощностью 256 символов. Следовательно, 1 символ такого текста “весит” 1 байт.

 

Пример 1. Сколько различных символов, закодированных байтами, содержится в сообщении:

1101001100011100110100110001110001010111?

Решение: Разбиваем сообщение на восьмёрки битов (то есть, на байты):

11010011 00011100 11010011 00011100 01010111.

Сравнивая байты между собой, видим, что первый и третий, а также второй и четвёртый байты одинаковые. Следова­тельно, различных символов всего три.

 

Пример 2. Для записи письма был использован алфавит мощностью в 16 символов. Письмо состояло из 25 строк. В каждой строке вместе с пробелами было 64 символа. Сколько байт информации содержало письмо?

Решение: М = 16

i = lоg₂16 = 4 (бит)

К = 25*64= 1600

I = К*i = 1600 * 4 бит = 6400 бит = 800 байт

Ответ: 800 байт.

 

Пример 3. Письмо состояло из 30 строк. В каждой строке вместе с пробелами по 48 символов. Письмо содержало 900 байт ин­формации. Какова мощность алфавита (количество символов), которым было написано письмо?

Решение:

К = 30*48 =1440

I = 900 байт = 7200 бит

i = I/К = 5 бит

N = 2⁵ = 32 символа

Ответ: 32 символа.

 

Пример 4. Даны два текста, содержащих одинаковое количество символов. Первый текст состоит из алфавита мощностью 16 символов, а второй текст - из 256 символов. Во сколько раз информации во втором тексте больше, чем в первом?

Решение:

К₁ = К₂

N₁ = 16, N₂ = 256

i₁ = lоg₂16 = 4 (бит)

i₂ = lоg₂256 = 8(бит)

I₁=К₁* i_1, I₂=К₂* i₂

I₂/I₁= (К₂*i₂) / (К1* i₁) = (К₂*8) / (К₂*4) =8/4 = 2

Ответ: в 2 раза.

Пример 5. Каждый символ в Unicode закодирован двухбайтным словом. Оцените информационный объем следующего предложения в той кодировке:

«Без труда не вытащишь рыбку из пруда.»

1)37 бит 2) 592 бита 3) 37 байт 4) 592 байта

Решение:

Длина фразы составляет примерно 40 символов. Следовательно, ее объем можно приблизительно оценить в 40 ´ 2 =80 байт. Такого варианта ответа нет, попробуем перевести результат в биты: 80 байт ´ 8 = 640 бит. Наиболее близкое значение из предложенных — 592 бита. Заметим, что разница между 640 и 592 составляет всего 48/16 = 3 символа в заданной кодировке и его можно считать несущественным по сравнению с длиной строки.

Ответ: 2.

Замечание: Подсчетом символов в строке можно убедиться, что их ровно 37 (включая точку и пробелы), поэтому оценка 592 бита = 74 байта, что соответствует ровно 37 символам в двухбайтовой кодировке, является точной.

Пример 6. Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100%, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.

1) 80 бит 2) 70 байт 3) 80 байт 4) 560 байт

Решение:

Способ 1

Воспользуемся формулой алфавитного подхода к измерению количества информации I = M log₂N, где N — количество символов (мощность) алфавита, в котором записано сообщение, М — количество символов в записи сообщения (длина сообщения), I — количество бит информации, содержащееся в сообщении.

Алфавитом в данном случае является множество целочисленных значений влажности от 0 до 100. Таких значений 101. Поэтому информационный объем результатов одного измерения I=log₂101. Это значение не будет целочисленным. Не вычисляя его, сразу найдем округленное в большую сторону целое значение. Заметим, что ближайшая к 101 целая степень двойки, большая 101, есть число 128 = 2⁷. Поэтому принимаем 7=log₂128 = 7 бит. Учитывая, что станция сделала 80 измерений, общий информационный объем равен 80 ´ 7=560 бит =70 байт.

Ответ: 2.

Способ 2

Воспользуемся следствием из формулы. Заметим, что 2⁶< 101 < 2⁷, поэтому минимально необходимое количество двоичных разрядов (бит) равно 7. Далее аналогично получаем, что общий информационный объем равен 80 ´ 7 = 560 бит = 70 байт.

Ответ: 2.

Пример 7. Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (регистр буквы имеет значение!).

Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.

Определите объём памяти, который занимает хранение 60 паролей.

1) 540 байт 2) 600 байт 3) 660 байт 4) 720 байт

Решение:

1) согласно условию, в пароле можно использовать 10 цифр (0..9) + 12 заглавных букв местного алфавита + 12 строчных букв, всего 10 + 12 + 12 = 34 символа

2) для кодирования 34 символов нужно выделить 6 бит памяти (5 бит не хватает, они позволяют закодировать только 2⁵ = 32 варианта)

3) для хранения всех 11 символов пароля нужно 11 × 6 = 66 бит

4) поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 72 = 9 × 8; то есть один пароль занимает 9 байт

5) тогда 60 паролей занимают 9 × 60 = 540 байт

Ответ: 1.