Jump to content

Несжимаемая струна

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

  1. ^ В. Чандру и М.Р.Рао, Справочник по алгоритмам и теории вычислений , CRC Press 1999, стр. 29-30.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: d72f6bf0ea827a80e6d523938f2f3e3a__1700563980
URL1:https://arc.ask3.ru/arc/aa/d7/3a/d72f6bf0ea827a80e6d523938f2f3e3a.html
Заголовок, (Title) документа по адресу, URL1:
Incompressible string - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)