Несжимаемая строка - Incompressible string
 | Эта статья нужны дополнительные цитаты для проверка. (Июль 2019) (Узнайте, как и когда удалить этот шаблон сообщения) |
An несжимаемый нить это строка с Колмогоровская сложность равной его длине, поэтому он не имеет более коротких кодировок.[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 символа, а элементы, которые они заменяют, имеют такую же длину. Следовательно, эта строка несжимаема нашим алгоритмом.
Рекомендации
- ^ В. Чандру и М. Р. Рао, Справочник по алгоритмам и теории вычислений, CRC Press 1999, стр. 29-30.