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

Несжимаема строкой является строка с сложностью Колмогоровой равна его длиной, так что он не имеет более короткие кодировки.

пример

Предположим, у нас есть строка 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 символа, а элементы, которые они заменяют, имеют такую ​​же длину. Следовательно, эта строка несжимаема нашим алгоритмом.

Рекомендации