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