Энтропия Шеннона и сжатие данных. Часть 1

[mns2012]

Мой учитель говорил: "Когда чего-то не понимаешь, пиши статью". Когда пишешь, всё излагаешь систематически и по порядку, видишь, где у тебя пробелы, и в конце концов всё становится более понятным.

Я давно хотел поподробнее разобраться с одной проблемой в оценке энтропии: почему моя оценка по степени сжатия оказалась лучше того, что выведено в метаданных PNG файлов. Я провёл небольшое исследование с помощью Gemini.

— А мне студентов-практикантов навязали. Учу вот!

Пишу вот!

Энтропия источника данных

Понятие энтропии источника данных связано с теоретическим максимальным коэффициентом сжатия данных без потерь.

В основе теории информации лежат несколько фундаментальных теорем.

1. Теорема Шеннона о кодировании источника (теорема о сжатии данных без потерь). Она устанавливает предел, до которого можно сжать данные, не теряя информации. Этот предел определяется энтропией источника (средним количеством информации на символ).
   
   
   • Суть: Невозможно без потерь сжать данные таким образом, чтобы среднее количество бит на символ было меньше энтропии источника. Однако можно достичь среднего количества бит, сколь угодно близкого к энтропии (приближение сверху), с минимальной вероятностью потери информации.
   
   


2. Теорема Шеннона о кодировании канала (или теорема о пропускной способности канала). Именно эту теорему чаще всего имеют в виду, когда говорят о «теореме Шеннона». Она устанавливает максимальную скорость передачи информации по каналу с шумом с гарантированно низкой вероятностью ошибки.
   
   
   • Суть: Для любого канала с шумом существует максимальная скорость передачи данных (пропускная способность), ниже которой можно передавать информацию почти без ошибок, используя специальные коды. Превышение этой скорости делает передачу с малой вероятностью ошибки невозможной.
   
   


3. Теорема Шеннона — Хартли. Это частный случай теоремы о кодировании канала, применённый к каналу с определённым типом шума — аддитивным белым гауссовским шумом. Она даёт точную формулу для вычисления пропускной способности такого канала в зависимости от его полосы пропускания и отношения сигнал/шум.


4. Теорема о разделении источника и канала. Эта теорема утверждает, что задачи сжатия данных (кодирование источника) и передачи по каналу с шумом (кодирование канала) можно решать по отдельности, не теряя оптимальности. Это позволяет разделить проектирование компрессора и кодера для помехоустойчивости.

Ключевые моменты:

• Энтропия: мера неопределенности или непредсказуемости информации, содержащейся в источнике данных. Она рассчитывается на основе вероятностей появления блоков данных (так называемых символов) в потоке.


• Предел сжатия: Теорема о кодировании источника определяет минимальное среднее число бит на символ, необходимое для представления данных источника без потерь. Эта величина называется энтропией источника.


• Сжатие без потерь: Теорема гарантирует, что существует теоретический предел сжатия, к которому на практике можно асимптотически приближаться сверху, рассматривая возможно бо́льшие блоки данных с использованием всё более сложных алгоритмов.


• Допущение: Теорема Шеннона о кодировании источника исходит из предположения, что символы источника данных являются независимыми случайными величинами.

Энтропия Шеннона и сжатие данных

Энтропия Шеннона H измеряет среднее количество «неожиданности» или непредсказуемости в данных (например, в файле). Энтропия — характеристика распределения и рассчитывается на практике на блок данных, или символ. Чем большие блоки берутся в рассмотренение, тем более сложным должен быть алгоритм, но тем ближе оценка к теоретическому минимуму. В текстовых файлах блоками данных обычно выступают текстовые символы, а в файлах изображений — пиксели, хотя это не обязательно, так как в качестве блоков данных можно рассматривать последовательности текстовых символов или блоки пикселей.

• Низкая энтропия: Данные очень предсказуемы (например, текстовый файл, содержащий одни только буквы «А»). Это означает, что имеется много избыточности, и алгоритм сжатия без потерь (например, ZIP или внутреннее сжатие PNG) может обеспечить высокую степень сжатия (т.е. отношения размеров файла до сжатия и после).


• Высокая энтропия: Данные очень непредсказуемы, практически случайны (например, зашифрованный файл или уже сжатый файл). Это означает, что избыточности мало или нет совсем, то есть что сжатие без потерь если и возможно, то будет характеризоваться очень низкой степенью сжатия (на практике размер файла может даже немного увеличиться из-за накладных расходов на сжатие).

Объяснение формулы Шеннона для информационной энтропии

Формула Шеннона информационной энтропии источника данных x:

H(x) = - Σ p(x_i) log₂p(x_i).

В формуле производится взвешенное усреднение количества информации, ожидаемое при выборе произвольного символа. Таким образом, энтропия H — это средневзвешенная сумма по всем возможным символам, где вес количества информации  I(x_i) = - log₂p(x_i) на символ равен вероятности p(x_i) появления символа.

Количество информации, содержащейся в появлении конкретного символа I(x_i) = -log₂p(x_i). Эта величина измеряется в битах. Логарифм с отрицательным знаком означает, что чем ниже вероятность p(x_i) (т.е., чем более неожиданно событие), тем выше количество информации I(x_i) оно несёт.

Среднее взвешенное по множеству {i = 1..N} значений дискретной переменной = Σ вес_i * значение_i.

Поэтому энтропия:

H(x) = Σ p(x_i) I(x_i) = - Σ p(x_i) log₂p(x_i)

представляет собой математическое ожидание (средневзвешенную сумму) количества информации по всем возможным символам текста.

Максимальная энтропия (случайные данные)

Покажем, что если при расчёте энтропии Шеннона в качестве символа (токена) в потоке данных рассматривается байт, максимально возможная энтропия для 8-битного источника данных (например, файла) составляет 8 бит на байт. В файлах средствами операционной системы данные обычно организуются в 8-битные блоки, то есть байты. 8-битный байт может представлять (кодировать) 2⁸ = 256 различных уникальных значений (от 0 до 255).

Прежде, чем вывести максимальное значение энтропии, отметим, что за единицу измерения энтропии графических файлов удобнее взять не 1 бит на байт, а 1 бит на пиксель.

• Для файлов с 8-битной глубиной (то есть с 2⁸ = 256 возможными значениями цветов или оттенков серого на пиксель) 1 бит на байт тривиально равен 1 биту на пиксель.


• Однако если цветовая гамма включает 24-бита на пиксель, разница между единицами измерения будет существенной: максимальное значение энтропии на 1 пиксель составит 24 бита, тогда как максимальное значение энтропии в расчёте на 1 байт останется равным 8 битам.

Энтропия Шеннона максимальна, когда все возможные символы равновероятны и независимы друг от друга. Это соответствует состоянию полной непредсказуемости, или цифровому шуму:

Пример изображения со значением энтропии, близкой к максимуму (цифровой, графический шум).
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей.
Сгенерировано Gemini

Как мы видели, для 8-битного файла существует n = 256 возможных байтовых значений. Максимальное значение энтропии Шеннона соответствует вероятности появления любого отдельного байтового значения, равной P(xᵢ) = 1/256. Вспомним формулу энтропии Шеннона:

H = − Σ P(xᵢ) * log₂(P(xᵢ)),

Здесь xᵢ, по смыслу энтропии, представляют собой символы в потоке данных (в графических файлах символами выступают пиксели).

Далее, поскольку все P(xᵢ) одинаковы и равны 1/256, формулу можно упростить:

H_max = − 256 * (1/256) * log₂(1/256) = − log₂(1/256) = log₂(256) = log₂(2⁸) = 8 [бит/пиксель].

Максимальная энтропия совпадает с так называемой глубиной изображения B, то есть с числом бит на символ (или бит на пиксель для графических файлов):

B = 8 [бит/пиксель] = H_max.

Оценка энтропии по коэффициенту сжатия

Поскольку, по теореме о кодировании источника, энтропия H представляет собой теоретический предел сжатия без потерь, сжатие, достигаемое высокоэффективным алгоритмом (например, zlib, который используется в PNG), может дать хорошую практическую оценку энтропии. Эта оценка энтропии источника всегда будет оценкой сверху.

• Когда я разбирался с конкретным примером (о чём пойдёт речь в следующей записи), я заметил, что эта оценка была по величине меньше, чем значение энтропии, которое я выцепил из метаданных моего PNG файла. Дело в том, что значение энтропии, указанное в файле, тоже представляет собой практическую оценку теоретического значения энтропии, выведенную из расчёта на пиксель. Теоретическое значение представляет собой предел, то есть минимум размера, до которого можно сжать исходный файл без потерь. К этому минимуму на практике мы можем лишь асимптотически приближаться сверху.

Если известны:

1. Размер S_raw исходных несжатых данных;


2. Размер S_comp сжатых данных без потерь;

то можно вычислить эмпирический коэффициент сжатия С_R, связанный с энтропией:

C_R = S_raw / S_comp.

Тогда энтропия H:

H = H_max / C_R = B / C_R,

поскольку В = H_max. Теперь мы можем посмотреть на тот факт, что глубина изображения равна максимуму энтропии, немного с другой стороны. В случае, если C_R = 1, размер файла до и после сжатия один и тот же, то есть сжатие без потерь невозможно. А это соответствует максимальной энтропии источника данных. Энтропия источника данных достигает максимума в случае, когда каждый символ (пиксель) является случайным. В этом случае никакой структурной избыточности в данных нет, соответственно, нет и возможности сжать данные без потерь. Пример изображения с максимальной энтропией мы видели выше.

В следующей записи я рассмотрю конкретный пример оценки энтропии для файла изображения в формате PNG.