Алгоритм Хаффмана: как студент MIT нашёл способ сжатия, который работает 75 лет
В 1951 году аспирант Массачусетского технологического института Дэвид Хаффман получил задачу, над которой прежде безуспешно трудились даже Клод Шеннон и его преподаватель Роберт Фано. Ему предстояло найти наиболее эффективный способ двоичного кодирования с переменной длиной кода, учитывающий частоту встречаемости каждого символа.
На протяжении нескольких месяцев Хаффман испытывал один подход за другим, но решение всё не находилось. В конце концов он уже собирался выбросить свои записи и приступить к подготовке к выпускному экзамену, когда его неожиданно осенила мысль.
Вместо того чтобы строить дерево кодирования сверху вниз, он решил пойти обратным путём: начать с нижнего уровня и последовательно объединять два символа с наименьшей частотой встречаемости.
Так появился алгоритм Хаффмана, позволяющий получить минимальную среднюю длину кодового слова среди всех двоичных префиксных кодов при заданных частотах символов.
Прошло 75 лет, но этот алгоритм и по сей день применяется в форматах ZIP, GZIP, JPEG и MP3.
Почему это важно
АналитикаАлгоритм Хаффмана — классический пример того, как смена направления поиска может решить задачу, которая долго оставалась открытой. Его использование в популярных форматах показывает, что простые и изящные алгоритмические идеи могут оставаться актуальными десятилетиями.
Обсудить в сообществе
Делитесь опытом и мыслями с ИИ-разработчиками
Связанные материалы экосистемы
Практические гайды, терминология и агентские скиллы
Поиск по дереву решений Монте-Карло для агентов (MCTS)
Алгоритмический подход к планированию действий ИИ-агентов, который сочетает эвристический поиск, оценку промежуточных состояний и бэктрекинг для нахождения оптимальных решений в пространстве высокой сложности.
Тест Тюринга и почему он устарел (Turing Test)
Исторический тест искусственного интеллекта, предложенный Аланом Тюриングом в 1950 году. Проверяет способность машины вести текстовый диалог настолько правдоподобно, чтобы человек не отличил ее от другой живой личности. Объясняет, почему с появлением языковых моделей этот тест утратил научную актуальность.
JetBrains открыла исходный код IDE, способной самостоятельно совершенствоваться
Среда разработки изучает особенности проекта, его задачи и потребности, а затем создаёт новые функции, подстраиваясь под них.
В опенсорсе нашли способ почти вдвое увеличить вычислительную мощность RTX 3090
Проект gpu-unlock обходит программное ограничение Nvidia на тензорных ядрах GeForce 30-й серии, почти удваивает пропускную способность FP16/BF16 и ускоряет префилл LLM без патча драйвера.
50 стилей визуального дизайна: фундаментальное руководство для дизайн-систем, UI/UX и арт-дирекшена
Полный визуальный словарь из 50 стилей дизайна: анализ эстетики, цветовые палитры, шрифтовые пары, правила для дизайн-систем и точное управление ИИ.
Jev и System One AI: полное практическое руководство по модели решений от TypeSafe
Глубокий инженерный разбор флагманской модели Jev: архитектура System One против LLM, примитивы Choice/Score/Noul, параллелизм запросов, математика уверенности, видео-кейсы, код и обзор локальных open-weight альтернатив (Laya, GLiNER2.5, CLM-8B).