Несжимаемая строка

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденный материал может быть оспорен и удален. Найти источники:  «Несжимаемая строка» – новости  · газеты  · книги  · ученый  · JSTOR ( июль 2019 г. ) ( Узнайте, как и когда удалять это сообщение )

Несжимаемая строка — это строка со сложностью Колмогорова , равной ее длине, так что она не имеет более коротких кодировок. ^[1] Принцип ящика можно использовать для доказательства того, что для любого алгоритма сжатия без потерь должно существовать много несжимаемых строк.

Предположим, у нас есть строка 12349999123499991234, и мы используем метод сжатия , который работает путем помещения специального символа в строку (например, @), за которым следует значение, указывающее на запись в таблице поиска (или словаре) повторяющихся значений. Представим, что у нас есть алгоритм, который проверяет строку на 4 символьных фрагмента. Глядя на нашу строку, наш алгоритм может выбрать значения 1234 и 9999 для помещения в свой словарь. Допустим, что 1234 — это запись 0, а 9999 — это запись 1. Теперь строка может стать:

@0@1@0@1@0

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

Однако наш алгоритм может работать лучше, если он может просматривать строку частями, превышающими 4 символа. Тогда он может поместить 12349999 и 1234 в словарь, что даст нам:

@0@0@1

Эта строка еще короче. Теперь рассмотрим другую строку:

1234999988884321

Эта строка не сжимается нашим алгоритмом. Единственные повторы, которые встречаются, это 88 и 99. Если бы мы сохранили 88 и 99 в нашем словаре, мы бы создали:

1234@1@1@0@04321

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