Но Хаффман был хитер. Он посмотрел на эти семь бит и сказал: «Конечно, должен быть способ сжимать данные». Друзья отговаривали его. «Нет, Хаффман, – говорили они. – Этого нельзя сделать. Ты слишком многого хочешь. Не рвись в герои». Но Хаффман не слушал их. Он был готов броситься с головой в неизвестность, чтобы изобрести другое бинарное представление набора символов.
Вместо использования бинарных кодов с фиксированной длиной Хаффман стал применять бинарные коды разной длины. Он опирался на факт, что некоторые символы встречаются в письменной речи чаще, чем другие, поэтому он присвоил этим часто встречающимся буквам меньшие величины. Соответственно они имели более короткий бинарный код, а реже встречающиеся символы – более длинный.
Например, для нашего набора данных частота встречаемости символов распределяется так, как показано на таблице слева.
Буква «е» встречается нам 705 раз, буква «а» – 605 раз и так далее. Заметьте, что символы отсортированы сверху вниз в порядке убывания частоты. Согласно подходу Хаффмана, нужно взять пару символов с наименьшей частотой встречаемости, сложить их значения, сохраняя результат в новом вре́менном символе, а затем отсортировать набор. Процесс повторяется, пока у нас больше не останется пар символов.
В конечном итоге получается дерево, где каждый узел (символ) соединен с парой узлов, на основе которых он образовался, с двумя краями. Если мы произведем такую операцию с приведенным выше набором данных, то в конечном итоге получим что-то вроде схемы, где мы сначала соединяли «f» и «j», затем результат этого действия совмещали с «l» и так далее. Каждая колонка, начиная со второй, представляет собой один шаг алгоритма.
Когда мы преобразуем схему в дерево, все становится яснее. Оптимизированный двоичный код символа – это цепочка, которую мы получаем, считывая биты с самого верхнего, или корневого,[31] узла и двигаясь ниже к узлу символа. Каждый раз, когда мы двигаем дерево влево, мы прибавляем ноль к двоичному коду символа, а при движении вправо добавляем единицу. Поэтому буква «е» заканчивается двухбитным двоичным кодом 11, а буква «f» представляет собой пятибитный код 10001. Приписывание 1 или 0 к дочернему узлу дерева Хаффмана производится факультативно, то есть литера «е» может быть закодирована как «01», а не как 11. Несмотря на то что двоичные коды не всегда уникальны, они считаются наиболее оптимальными. В любом случае дерево Хаффмана отсылается адресату вместе с сообщением, чтобы получатель знал, как его раскодировать.
Вот список оптимизированных двоичных кодов. Заметьте, что самые частые буквы имеют наиболее короткие коды.
Как же будет выглядеть слово «hans» в двоичном коде?
001 01 101 000
Для такой записи нам понадобилось 11 бит, а не 28. Это открытие заставляет вспомнить историю почти столетней давности о том, как передавали сообщения по телеграфу. Способ Самюэля Морзе кодировать буквы также был основан на том, насколько часто эти буквы встречались в английском языке. Морзе определял частоту различных букв не в ходе бесед с учеными или анализа данных – он просто считал литеры в шрифтовой каретке наборщика в типографии. Так что в следующий раз, когда какой-нибудь умник начнет критиковать ваши методы исследования, не отступайте.
Техники компрессии данных, подобные кодированию методом Хаффмана, чрезвычайно важны в современном мире. Оптимальное использование пространства означает, что вебсайты будут загружаться быстрее, веб-серверы могут сжимать файлы, прежде чем рассылать их по сети, а современные браузеры сумеют легко распаковывать их. Если место ограниченно, любое увеличение скорости имеет значение.
Компрессия также означает, что фильмы (то есть файлы формата MPEG-2), изображения (файлы формата JPEG) и песни (файлы формата МРЗ) могут занимать меньше пространства, что позволит сэкономить деньги на их хранении и пересылке. Аудиофайлы типа МРЗ интересны в том плане, что их сжатие основано на удалении того диапазона аудиосигналов, который человеческое ухо не может услышать из-за особенностей своего анатомического строения. Например, оно не воспринимает частоту свыше 20 000 Гц.
В следующий раз, когда вы будете разговаривать по голосовой или видеосвязи с высоким качеством звука и изображения, подумайте о том, что ваша беседа стала возможной благодаря конверсии. Технология достигла такого уровня, что вашему приложению нужно всего лишь послать данные по сети, а потом либо догадаться о содержании, либо реконструировать оставшуюся часть на другом конце. На самом деле компрессия помогает снизить барьер использования технологий.
Все это хорошо. Но что там с Дуэйном и его читателями? Останутся ли они довольны? К счастью, да. Парень удачно выкрутился из ситуации и успешно описал сцену – событие, его юмор и важное сообщение, предназначенное для тех, кто хотел его услышать. Сила написанного слова – вот за что был сожжен на костре Уильям Тиндейл.[32] Парень обновляет свой статус, и сотни нетерпеливых пользователей получают долгожданный хит.
«В фантастическом походе с самого рассвета. Лучшее: утки устроили бесплатное шоу».
Остается надеяться, что умение Дуэйна сжимать сообщения без потери важной информации всегда будет приводить к такому же успешному результату. Если нет, уткам придется его научить.
8Как все успеть?
Кви Ноа работает в Сент-Луисе, в фирме сельскохозяйственных технологий, которая специализируется на продаже генетически модифицированных семян. Она всего лишь скромная секретарша, и ее босс дал ей кучу заданий, которые нужно закончить к концу недели. Отчетный день – пятница. Осталось всего два дня. Если Кви не выполнит все задания вовремя, ей не разрешат пойти на ежегодный корпоратив в субботу. Этот банкет – единственное мероприятие в жизни фирмы, во время которого начальники и подчиненные общаются на равных. Для Кви это шанс «на людей посмотреть и себя показать». Если ей повезет, то она получит повышение, на которое так давно надеется. Что же ей делать?
Справляться с растущим потоком задач – одно из самых важных умений в жизни взрослого человека. Только подумайте, как много книг и статей вам нужно будет прочитать по теме эффективного планирования рабочего времени, чтобы умело распределять рабочую нагрузку. Кви хорошо знает, что успеть все вовремя – задача непростая, которая потребует напряжения всех сил. Давайте рассмотрим для нее несколько способов достичь цели.
ЦЕЛЬ: ВЫПОЛНИТЬ ВСЕ ЗАДАНИЯ К КОНЦУ НЕДЕЛИ.
МЕТОД 1: ПОРАБОТАТЬ НЕМНОГО НАД ОДНИМ ЗАДАНИЕМ. ПЕРЕКЛЮЧИТЬСЯ НА ДРУГОЕ. ПОРАБОТАТЬ НЕМНОГО. ПЕРЕКЛЮЧИТЬСЯ НА СЛЕДУЮЩЕЕ. И ТАК ДАЛЕЕ.
МЕТОД 2: ОТСОРТИРОВАТЬ ЗАДАНИЯ ОТ САМОГО ПРОСТОГО ДО САМОГО СЛОЖНОГО. НАЧАТЬ С ПРОСТОГО. КОГДА ОНО БУДЕТ СДЕЛАНО, ПЕРЕЙТИ КО ВТОРОМУ ПРОСТОМУ. И ТАК ДАЛЕЕ.
МЕТОД 3: РАССОРТИРОВАТЬ ЗАДАНИЯ ПО ПРИОРИТЕТНОСТИ. НАЧАТЬ С САМОГО ВАЖНОГО. КОГДА ОНО БУДЕТ ЗАКОНЧЕНО, ПЕРЕЙТИ К СЛЕДУЮЩЕМУ ПО ВАЖНОСТИ. И ТАК ДАЛЕЕ.
Все эти методы наверняка знакомы. Применяя метод 1, мы используем единицы времени, чтобы определять, когда переключиться с одного задания на другое. Например, у нас три набора заданий по трем различным предметам в школе, и все нужно сдать до конца недели. Можно посвятить утро одному предмету, день – второму, а вечером заняться третьим. На следующий день повторяем эту схему и так далее, пока не будут готовы все задания. Этот метод распределения времени – хороший пример того, как современные операционные системы справляются с многочисленными приложениями, и его иногда называют контекстным переключением. Диспетчер следит за текущими процессами,[33] отводит им определенное время, а потом контролирует, чтобы каждый процесс умещался в предписанный ему хронометраж.
Переключение между процессами происходит так плавно, что при наблюдении за операционной системой создается впечатление, будто они протекают параллельно. Сегодня при наличии многоядерных процессоров так оно и есть. Четырехъядерный процессор может одновременно вести четыре процесса, и контекстуальное переключение ему требуется только тогда, когда процессов запускается больше, чем у него ядер.
Это напоминает приложение параллельной обработки, которое имеет аналог в реальной жизни и называется конвейерной обработкой. Набор взаимосвязанных заданий распределяется и выполняется так, чтобы оптимизировать имеющиеся в наличии ресурсы. Например, вы с двумя вашими друзьями вдруг вспомнили, что забыли приготовить мешки с подарками для гостей, а вечеринка вот-вот закончится. Чтобы сделать как можно больше мешков в единицу времени, эффективно применить что-то вроде конвейерного метода: вы пишете поздравления на мешке, один друг складывает в него подарки, а второй – завязывает мешки лентой. Это лучше других подходов, когда один или оба ваших друга будут ждать, пока вы подпишете все мешки. Распределение заданий важно, но до определенной степени: как однажды написал Фред Брукс, девять женщин не родят ребенка за один месяц.
При современных характеристиках «железа» мы не замечаем границ возможностей контекстуального переключения. Между тем каждый раз, когда система его выполняет, ей нужно придержать состояние последнего процесса, очистить регистры и удалить передаваемые данные, а затем загрузить новое состояние процесса.[34]
Для человека когнитивная нагрузка, которая сопровождает этот тип переключения, может быть довольно серьезной. Одно из препятствий на пути обеспечения продуктивности – необходимость прервать текущее занятие, переключиться на что-то срочное, а затем вернуться к предыдущему делу. Операционная система работает подобным образом, запуская так называемый обработчик прерываний