Поиск Настройки. OTUS Цифровые навыки от ведущих экспертов. Время на прочтение 8 мин. Автор оригинала: undefined. В преддверии старта курса «Алгоритмы для разработчиков» подготовили для вас перевод еще одного полезного материала. Кодирование Хаффмана — это алгоритм сжатия данных, который формулирует основную идею сжатия файлов. В этой статье мы будем говорить о кодировании фиксированной и переменной длины, уникально декодируемых кодах, префиксных правилах и построении дерева Хаффмана. Мы знаем, что каждый символ хранится в виде последовательности из 0 и 1 и занимает 8 бит. Это называется кодированием фиксированной длины, поскольку каждый символ использует одинаковое фиксированное количество битов для хранения. Допустим, дан текст. Каким образом мы можем сократить количество места, требуемого для хранения одного символа? Основная идея заключается в кодировании переменной длины. Мы можем использовать тот факт, что некоторые символы в тексте встречаются чаще, чем другие см. При кодировании переменной длины мы присваиваем символам переменное количество битов в зависимости от частоты их появления в данном тексте. В конечном итоге некоторые символы могут занимать всего 1 бит, а другие 2 бита, 3 или больше. Проблема с кодированием переменной длины заключается лишь в последующем декодировании последовательности. Как, зная последовательность битов, декодировать ее однозначно? Рассмотрим строку «aabacdab». В ней 8 символов, и при кодировании фиксированной длины для ее хранения понадобится 64 бита. Заметим, что частота символов «a», «b», «c» и «d» равняется 4, 2, 1, 1 соответственно. Давайте попробуем представить «aabacdab» меньшим количеством битов, используя тот факт, что «a» встречается чаще, чем «b» , а «b» встречается чаще, чем «c» и «d». Начнем мы с того, что закодируем «a» с помощью одного бита, равного 0, «b» мы присвоим двухбитный код 11, а с помощью трех битов и закодируем «c» и «d». В итоге у нас получится: a 0 b 11 c d Теги: алгоритмы сжатие данных. Комментарии 7. Сайт ВКонтакте Telegram. Комментарии Комментарии 7. Лучшие за сутки Похожие. Сайт otus. Ваш аккаунт Войти Регистрация.

.