Код Хаффмана — это метод оптимального префиксного кодирования, который минимизирует среднюю длину кодового слова для набора символов. Он используется в различных областях, в том числе для сжатия данных.
Информационная энтропия, введенная Клодом Шенноном, измеряет неопределённость или «среднее количество информации», которое несёт случайное сообщение. Энтропия характеризуется формулой:
$$H(X) = - \sum_{i=1}^{n} P(x_i) \log_2 P(x_i)$$
где $P(x_i)$ — вероятность появления символа $x_i$. Чем выше энтропия, тем больше вероятность, что сообщение будет содержать уникальные символы, и тем более информация рассеяна по всему объему данных.
Код Хаффмана строит двоичное дерево и использует его для кодирования символов так, чтобы более вероятные символы имели более короткие кодовые слова. Это делает кодирование более эффективным при низкой энтропии, позволяя оптимизировать сжатие данных.
Таким образом, код Хаффмана тесно связан с энтропией: чем меньше энтропия сообщения, тем сильнее можно его сжать с использованием этого метода. Хаффмановское кодирование стремится достичь энтропийной границы, представляя наиболее часто встречающиеся символы менее затратными с точки зрения длины кодов, приближаясь к оптимальной эффективности, предсказанной энтропией.
Категория: Теория информации
Теги: кодирование, энтропия, сжатие данных