Почему текстовое представление pi может быть сжато?

Question

Случайная строка должна быть несжимаемой.

pi = "31415..."
pi.size  # => 10000
XZ.compress(pi).size  # => 4540

Случайная шестнадцатеричная строка также значительно сжимается. Однако случайная строка байтов не сжимается.

Строка pi содержит только байты с 48 по 57. С префиксным кодом на целых числах эта строка может быть сильно сжата. По сути, я теряю пространство, представляя мои 9 различных символов в байтах (или 16, в случае шестнадцатеричной строки). Это то, что происходит?

Может кто-нибудь объяснить мне, что является основным методом, или указать мне на некоторые источники?

Answer 1

Это вопрос плотности информации. Сжатие - это удаление лишней информации.

В строке "314159"каждый символ занимает 8 битов и поэтому может иметь любое из²⁸ или 256 различных значений, но фактически используются только 10 из этих значений. Даже болезненно наивная схема сжатия может представлять ту же информацию, используя 4 бита на цифру; это известно как двоичное кодированное десятичное число. Более сложные схемы сжатия могут работать лучше, чем это (десятичная цифра - это log₂10, или около 3,32, бит), но за счет хранения некоторой дополнительной информации, которая допускает декомпрессию.

В случайной шестнадцатеричной строке каждый 8-битный символ имеет 4 значащих бита, поэтому должно быть возможно сжатие почти на 50%. Чем длиннее струна, тем ближе можно добраться до 50%. Если вы заранее знаете, что строка содержит только шестнадцатеричные цифры, вы можете сжать ее ровно на 50%, но, конечно, это теряет способность сжимать что-либо еще.

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

Объяснение деталей того, как работает сжатие, выходит за рамки этого ответа и моего опыта.

Answer 2

В дополнение к отличному ответу Кейта Томпсона, есть еще один момент, относящийся к LZMA (это алгоритм сжатия, используемый в формате XZ). Число pi не состоит из одной повторяющейся цепочки цифр, но и не является абсолютно случайным. Он содержит подстроки цифр, которые повторяются в большей последовательности. LZMA может обнаружить их и сохранить только одну копию повторяющейся подстроки, уменьшая размер сжатых данных.