Конечно. Вам нужно сопоставить все 256 значений чему-либо. Это может быть код переменной битовой длины, обычно код префикса, чтобы его можно было уникально декодировать. Таким образом, я мог бы сопоставить 256 возможных значений байтов с битовыми последовательностями 0, 10, 110, 1110, ..., (255 1) 0. Первые семь имеют длину менее восьми битов. Так что, если один байт для сжатия равен 0, то я могу сжать его до 1 бита. Я могу послать этот бит, и декомпрессор распознает его и распакует в 0 байт. Вуаля! Я сжал один байт без потерь.
(Кстати, я беру вопрос «возможно сжимать», чтобы обозначить также возможность распаковки без потерь до исходного ввода. Если вам не требуется распаковка, то при «удалении» всегда возможно 100% сжатие. команда.)
Однако вы заметите, что в этом случае я не могу сжать всех возможных однобайтовых входов до менее чем восьми битов. Только некоторые из них. И другие из них расширятся до более чем восьми битов. То есть всегда - случай сжатия без потерь. Если некоторые входы сжаты, то должно быть другими расширенными входами.
Почему? Например, нет способа сжать все 256 восьмибитных значений до всех семибитных значений, поскольку существует только 128 семибитных значений. Следовательно, должно быть не менее двух байтовых значений, которые соответствуют одному семибитному значению. Если декомпрессор получает это семибитное значение, он не может узнать, какое из двух восьмибитных значений привело к этому семибитному значению.
Просто подсчитав, сколько возможных входов имеется, вы можете показать, что для того, чтобы иметь достаточно уникальных возможных выходов, чтобы охватить все эти входы, при сжатии должно быть расширение.