Сколько BPS (бит на символ) достаточно, чтобы назвать алгоритм сжатия хорошим по отношению к энтропии?

Question

Рассмотрим алгоритм сжатия данных общего назначения без потерь. Он сжимает файл с энтропией E (измеряется в битах в секунду (бит на символ)) в другой файл, в котором каждый символ представлен X бит, то есть BPS = X .

Так, что X - E = 0,4xxxxx .

СейчасВопрос: это хороший, лучший, лучший или худший алгоритм?

Answer 1

Мы знаем, что арифметическое кодирование достигает энтропии (при условии информации о вероятности).С другой стороны, можно показать, что кодирование Хаффмана достигает скорости X, которая не более чем на 1 бит / с выше, чем энтропия.этот порог может быть улучшен путем объединения n символов вместе, поэтому для исходных символов у нас будет максимум 1 / n BPS выше, чем энтропия.Я бы сказал, что кодировщик, который у вас есть, находится посередине.