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

Question

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

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

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

Answer 3

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

Answer 4

Да!Я думаю Эта бумага укажет вам правильное направление.

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