Можно ли сжать один байт без потерь?

Один байт - это минимальная единица для представления 256 уникальных значений. Сжатие возможно только в том случае, если у вас есть домен, который является подмножеством, например, только 16 значений [0,15]. В этом случае вы можете сжать 2 «байта» в 1 байт, используя 2 полубайта (полубайта). Как правило, для этого нужны битовые маски. (Растровые изображения являются расширением битовых масок.) Как правило, для сжатия необходимо уменьшить домен.

Конечно. Вам нужно сопоставить все 256 значений с чем-то. Это что-то может быть кодом переменной длины в битах, обычно это префиксный код, чтобы его можно было однозначно декодировать. Таким образом, я мог сопоставить 256 возможных значений байтов с последовательностями битов 0, 10, 110, 1110, ..., (255 единиц) 0. Первые семь меньше восьми битов в длину. Итак, если одиночный байт для сжатия равен 0, я могу сжать его до 1 бита. Я могу отправить этот один бит, и декомпрессор распознает его и распакует до нулевого байта. Вуаля! Я сжал один байт без потерь.

(Между прочим, я беру вопрос «можно сжать», чтобы также означать возможность распаковки без потерь до исходного ввода. Если вам не требуется распаковка, то 100% сжатие всегда возможно с помощью команды «удалить».)

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

Почему? Например, невозможно сжать все 256 восьмибитных значений до всех семибитных значений, поскольку существует только 128 семибитных значений. Следовательно, должно быть по крайней мере два байтовых значения, которые соответствуют одному семибитному значению. Если декомпрессор получает это семибитное значение, он не может узнать, какое из двух восьмибитовых значений привело к этому семибитному значению.

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

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

Это приводит к интересному вопросу: каков наименьший средний размер сжатия, достижимый при условии равномерно случайного ввода и длины ввода фиксированной на уровне одного байта, сохраняя 3 бита для указания длины менее 8 бит? Пример, указанный в другом ответе, потребует (1 + 2 + ... + 255 + 256) / 256 бит, что составляет 257 × 128/256 = 257/2 = 128,5 бит. Это намного хуже, чем 8 бит. Насколько мне известно, нет никаких доказательств для этого? Однако, учитывая, что длина вывода сама по себе кодирует информацию, должно быть, что 0 бит может быть допустимым значением, 1 бит дает еще 2, 2 бита еще 4 и т. д., Поэтому 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255 плюс одно полное оставшееся 8-битное значение будет отображаться на 256 уникальных значений.

Следовательно (0 + 1 × 2 + 2 × 4 + 3 × 8 + 4 × 16 + 5 × 32 + 6 × 64 + 7 × 128 + 8) /256=1546/256=6.0390625.
Таким образом, для 8 бит, если это ваша общая фиксированная длина данных, должна быть в среднем сжимаема до чуть более 6 бит. Однако сложность кода, который может его распаковать, может быть значительно больше, чем у простой схемы со средним значением 128,5 бит.

Этот компромисс между размером сжатых данных и размером данных кода, используемого для распаковки, является частью того, что колмогоровская сложность используется для представления. Чем больше алгоритм распаковки, тем более сжатыми могут быть данные, поскольку сам алгоритм распаковки содержит много информации. Это не учитывает практическую эффективность алгоритма декомпрессии, что практически важно. Теоретически лучший алгоритм с точки зрения чистых данных - это тот, у которого средний размер сжатия плюс размер кода, необходимого для его распаковки, являются наименьшими. Ради математической общности, все данные и алгоритм декомпрессии должны быть закодированы на универсальной машине Тьюринга (UTM), чтобы провести корректное сравнение.

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

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

Но это достаточное доказательство того, что это действительно возможно.