Связь энтропии со скоростью сжатия без потерь

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

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

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

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

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

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

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

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

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

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