Отношение энтропии к скорости сжатия без потерь

Question

Из Исходной теоремы Шеннона о кодировании мы знаем, что энтропия сжатой строки ограничена энтропией исходной строки следующим образом:

H(X) <= L < H(X) + 1/N 

где H (X) - энтропия исходной строки, N - длина исходной строки, а L - ожидаемая длина сжатой строки.

Это обязательно означает, что есть предел сжатия без потерь.

Я хотел бы знать:

• Можем ли мы напрямую связать энтропию с некоторой ожидаемой степенью сжатия?

• Можем ли мы использовать энтропию, чтобы найти некоторую верхнюю границу для степени сжатия?

Answer 1

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

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

Учитывая любую случайную строку, я могу легко написать алгоритм сжатия, который сжимает эту строку до 1 бита, но мой алгоритм обязательно увеличит длину некоторых других строк. Мой алгоритм сжатия работает следующим образом:

1. Если входная строка равна некоторой предварительно выбранной случайной строке , на выходе получается 1-битная строка "0"
2. В противном случае на выходе получается N + 1-битная строка «1», за которой следует строка ввода

Соответствующий алгоритм распаковки:

1. Если на входе «0», на выходе будет наша предыдущая предварительно выбранная случайная строка
2. В противном случае выводом является все, кроме первого входного бита

Ключевым моментом здесь является то, что мы не можем записать один алгоритм, который для всех строк из данного распределения сжимает их все с высокой скоростью в среднем. Там слишком много строк.

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

Answer 2

Да. коэффициент энтропии английского языка часто цитируется как 1,5 бита на символ (давать или брать). Типичные кодировки используют 8 бит на символ. Таким образом, максимально сжатый текст должен быть в 1,5 / 8 (~ 19%) размера оригинала. Фактические результаты для простой текстовой версии «Гордости и предубеждения Джейн Остин»: orig = 701K, bzip2 = 178K, на ~ 25%.

Answer 3

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

Итак, да. Вы можете использовать энтропию, чтобы найти теоретическую максимальную степень сжатия без потерь, но нет, вы не можете использовать ее для определения ожидаемой степени сжатия для любого данного алгоритма сжатия.

Answer 4

Да! Я думаю эта статья укажет вам правильное направление.

ETA Похоже, вам нужно быть членом IEEE, чтобы прочитать реальную статью. Если бы кто-то мог найти общедоступный ресурс (или объяснить здесь математику), это было бы намного лучше, конечно!