Ознакомительная версия. Доступно 18 страниц из 90
Во всех англоязычных текстах чаще всего встречается буква е, на которую приходится 12,7 % текста. Следом за ней идет буква t (9,1 % текста), а реже всего встречается z, которая не только стоит последней в алфавите, но и довольствуется всего 0,074 % всех текстов. Именно поэтому при игре в Scrabble за использование z присуждается больше очков, чем за использование е. Шеннон показал, что знание этой статистики может сократить количество битов, необходимых для передачи сообщения.
Чтобы понять почему, представьте, что алфавит Алисы и Боба отражает статистическую вероятность использования каждой буквы. Такой “статистически точный” алфавит выглядит следующим образом: etaoinshrdlcumwfgypbvkjxqz. Теперь изменим этот алфавит, включив в него больше копий распространенных букв и отразив частоту их встречаемости в английском языке: в нем будет 172 буквы е, 122 t, 110 а, 101 о, 94 I, 91 п и так далее до 2 х, i q и i z. Всего в него войдет 1351 буква, и выглядеть он будет так:
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeettttttttttttttttttttttttttt
ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt
ttttttttttaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaoooooooooooooooooooooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooooooooooooooooooooooooo
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiinnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnsss
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
ssshhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrddddddddddddd
ddddddddddddddddddddddddddddddddddddddddddddllllllllll
llllllllllllllllllllllllllllllllllllllllllllcccccccccccccccccccccccccccccccccccc
ccuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuummmmmmm
mmmmmmmmmmmmmmmmmmmmmmmmmmmwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwffffffffffffffffffffffff
ffffffgggggggggggggggggggggggggggyyyyyyyyyyyyyyyyyyyyyyyyyyyp
pppppppppppppppppppppppppbbbbbbbbbbbbbbbbbbbbvvvvvvvv
vvvvvkkkkkkkkkkjjxxqz
Теперь, используя такую же систему “да” и “нет”, как раньше, Алиса увидит, что чем распространеннее буква, тем меньшее количество битов необходимо для ее передачи. Например, для передачи буквы е понадобится всего три бита, 111.
Первая единица сократит статистически точный алфавит до первой половины из 675 букв, куда теперь входят только е, t, а, о, i и n.
Вторая единица сузит выбор первыми 337 буквами, среди которых теперь остались лишь е, t и а.
Третья единица сократит алфавит до первых 168 букв, и все это — буквы е.
Итак, 111 соответствует е.
Мы можем применить статистический принцип, чтобы сократить сообщение help. Букву h, которая в английском языке встречается в 6 % случаев, нельзя назвать ни особенно распространенной, ни особенно редкой, поэтому для ее передачи все равно потребуется пять битов. Для передачи буквы е, как мы увидели, достаточно будет трех битов, 111. Для буквы /, как и для А, потребуется пять битов, а для передачи относительно редкой буквы р, которая встречается в 1,9 % случаев, необходимо шесть битов. Таким образом, общее число битов, необходимых для передачи сообщения help, составляет 5 (для h) + 3 (для е) + 5 (для /) + 6 (для p) = 19 битов.
Приняв в расчет статистику встречаемости букв, мы сократили сообщение help на один бит. Для передачи редких букв таким методом действительно нужно больше битов, чем в прошлой системе, однако, поскольку для передачи распространенных букв требуется меньше битов, общее количество необходимых битов снижается. Для передачи такого слова, как heat (“теплота”), содержащего три распространенные буквы (е, а и t), понадобится всего 16 битов. При передаче длинных сообщений этот метод позволит Алисе и Бобу использовать примерно на 10 % меньше битов, чем если бы они считали, что частота встречаемости всех букв одинакова.
Как отметил Шеннон, частотой встречаемости отдельных букв статистические закономерности англоязычного текста не ограничиваются. Многие пары букв — например, th, he, in и er — встречаются чаще других. Многие другие пары, например gx, не встречаются никогда. Порой одна буква определяет следующую, как в случае с q, за которой всегда идет и. С учетом всех этих закономерностей среднее количество битов, необходимое для передачи англоязычного сообщения, можно сократить примерно до 1,6 бита на букву. (Использование нецелого числа битов может показаться странным, однако наличие шести десятых бита не значит существование шести десятых ответа “да” или “нет” или шести десятых значения 1 или о. Оно значит, что, например, для передачи сообщения длиной в 100 букв понадобится в среднем 160 битов.)
В своей статье Шеннон объяснял многие идеи, обращаясь к примеру с письменным английским языком, но проиллюстрированные таким образом принципы применимы гораздо шире. Суть в том, что чем больше закономерностей можно найти в любой единице информации, тем меньше битов необходимо для ее шифрования.
Довольно просто, например, увидеть, как это применимо к изображениям. Интуитивно понятно, что для передачи изображения, состоящего из раскрашенных случайным образом точек, требуется гораздо больше битов информации — гораздо больше ответов “да” и “нет”, — чем для передачи изображения с повторяющимся узором, например в виде горизонтальных полосок. В первом случае необходимо определить цвет и яркость каждой точки изображения. Во втором — достаточно определить лишь два цвета и частоту их повторения.
В реальном мире изображения редко представляют собой случайный набор цветных точек или узор из ровных полос, но все же содержат закономерности. Инженеры используют это, чтобы сократить количество битов, необходимых для хранения и передачи видео и неподвижных изображений.
Эта методология применима также к устной речи, которая состоит из алфавита звуков: одни звуки в ней сливаются, а другие всегда остаются отделенными друг от друга. Выявив статистические закономерности, можно сократить число битов, необходимых для передачи разборчивой человеческой речи.
Ознакомительная версия. Доступно 18 страниц из 90
