Дэвид Альберт Хаффман — американский инженер и учёный, чьё имя сегодня прежде всего связано с одним из самых известных алгоритмов сжатия данных. Кроме этого он работал над принципами построения цифровых схем.
Хаффман получил образование электротехника в Университете штата Огайо, а после Второй мировой войны служил в ВМС США офицером по обслуживанию радаров. Позже он поступил в MIT, где и появилась работа, сделавшая его знаменитым.
Кодирование Хаффмана
В 1951 году на курсе по теории информации в MIT профессор Роберт Фано предложил студентам выбор: сдавать экзамен или решить задачу построения максимально эффективного двоичного кода.
Хаффман выбрал задачу и придумал метод, при котором часто встречающиеся символы получают короткие двоичные коды, а редкие — более длинные. Получившийся префиксный код позволял однозначно восстановить исходные данные и при заданных вероятностях символов минимизировал среднюю длину кодового слова.
В сентябре 1952 года Хаффман опубликовал результат в статье A Method for the Construction of Minimum-Redundancy Codes.
Алгоритм оказался невероятно живучим. На протяжении нескольких десятилетий и даже сегодня алгоритм Хаффмана используется в самых устройствах и программах. Он стал очень полезным в эпоху раннего Интернета, когда связь была долгой и дорогой. Современные пользователи опосредованно пользуются алгоритмом Хаффмана, когда используют MP3 или JPEG.
Цифровые схемы
Хаффман был специалистом не только по сжатию данных. Его докторская диссертация в MIT называлась Синтез последовательных переключательных схем. Очень грубо говоря — это схемы с сохранением состояния (памятью). Именно за докторскую работу по последовательным схемам Хаффман получил медаль Louis E. Levy Medal Института Франклина.
Радары и системы связи
Хаффман также работал над проектированием сигналов для радарных и коммуникационных систем.
Эта область была ему знакома ещё со времён службы во флоте: после окончания Университета штата Огайо он служил офицером по обслуживанию радаров на эсминце ВМС США. В дальнейшем проектирование сигналов для радаров и связи стало одним из направлений его научной работы.
Компьютерное зрение
Хаффман приложил свою руку к компьютерному зрению.
В 1971 году он опубликовал работу Impossible Objects as Nonsense Sentences (Невозможные объекты как бессмысленные предложения). Хаффман исследовал, как по двумерному изображению линий определить структуру трёхмерного объекта и, в частности, понять, когда рисунок описывает геометрически невозможный объект.
Эта работа относится к ранней истории компьютерного зрения — попыткам научить компьютер понимать геометрические отношения между объектами на нём.
Оригами
В последние десятилетия своей карьеры Хаффман заинтересовался эффективным математическим представлением поверхностей. Исследования поверхностей с нулевой гауссовой кривизной привели его к довольно неожиданной области — оригами.
Хаффман разрабатывал собственные методы складывания бумаги и создавал сложные геометрические формы, в том числе используя не только прямые, но и криволинейные сгибы.
Это было не просто хобби. С помощью оригами Хаффман разрабатывал методы представления объектов трёхмерного мира с помощью двумерных конструкций.