Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Энтропия

Основы теории информации были заложены Клодом Шеноном в 1948 году в лаборатории Белла. Эта теория оказалась настоящим сюрпризом, поскольку все привыкли воспринимать информацию лишь качественно. Для наших целей сжатия данных нам необходимо освоить только одно теоретико-информационное понятие, а именно, энтропию. Под энтропией символа а, имеющего вероятность Р, подразумевается количество информации, содержащейся в а, которая равна — Р log2P. Например, если вероятность Расимвола а равна 0.5, то его энтропия — Раlog2Ра = 0.5.

Если символы некоторого алфавита с символами от а\ до апимеют вероятности от Р\ до Рп, то энтропия всего алфавита равна сумме 5^nPi log2P{. Если задана строка символов этого алфавита, то для нее энтропия определяется аналогично.

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

Продемонстрируем это на простом примере. Для последовательности символов «ABCDE» с вероятностями 0.5, 0.2, 0.1, 0.1 и 0.1, соответственно, вероятность строки «AAAAABBCDE» равна Р = = 0.55 х 0.22 х 0.13 = 1.25 х Ю-6. Логарифм по основанию 2 этого числа log2P — —19.6096. Тогда наименьшее в среднем число требуемых бит для кодирования этой строки равно — flog2P~\ , то есть, 20. Кодер, достигающий этого сжатия называется энтропийным кодером. Пример: Проанализируем энтропию алфавита, состоящего всего из двух символов Oi и й2 с вероятностями Pi и P<i. Поскольку Pi + Pi — 1, то энтропия этого алфавита выражается числом —Pi log2 Pi — (1 — Pi) log2(l — Pi). В табл. 1.1 приведены различные значения величин Pi и Р2 вместе с соответствующей энтропией. Когда Pi = P2, необходим по крайней мере один бит для кодирования каждого символа. Это означает, что энтропия достигла своего максимума, избыточность равна нулю, и данные невозможно сжать. Однако, если вероятности символов сильно отличаются, то минимальное число требуемых бит на символ снижается. Мы, скорее всего, не сможем непосредственно предъявить метод сжатия, который использует 0.08 бит на символ, но мы точно знаем, что при Pi = 0.99 такой алгоритм теоретически возможен.

Pi

Р2

Энтропия

0.99

0.01

0.08

0.90

0.10

0.47

0.80

0.20

0.72

0.70

0.30

0.88

0.60

0.40

0.97

0.50

0.50

1.00

Табл. 1.1. Вероятности и энтропии двух символов.