Оценки практического сжатия и колмогоровской сложности - PullRequest
Новая
       27

Оценки практического сжатия и колмогоровской сложности

3 голосов
/ 13 января 2011

Я пытаюсь использовать сжатие как способ измерения отношения документа к совокупности документов. При этом я нашел странный результат при использовании bzip2; len (сжимать (корпус))> len (сжимать (корпус + новый_документ)). Должно ли это быть в случае с практическим алгоритмом сжатия, и возможно ли это теоретически при рассмотрении колмогоровской сложности данных? (идея состоит в том, чтобы использовать алгоритм сжатия, чтобы приблизить сложность данных)

Ответы [ 2 ]

4 голосов
/ 13 января 2011

Да, так должно быть в случае с практическим алгоритмом сжатия, и теоретически это возможно при сложности Колмогорова . Самый простой способ объяснить, почему на примере.

Предположим следующее:

  • символ разделителя вашего документа ,
  • корпус - это документы abc, def, abc, def, abc, def, abc,
  • новый документ - def
  • ваш алгоритм сжатия (или язык описания колмогоров) просто позволяет повторение путем добавления префикса с числом повторений, за которым следует | (это вариант кодирование длины серии )

Тогда:

  • compress (corpus) = "3 | abc, def, 1 | abc"
  • compress (corpus + new_document) = "4 | abc, def,"

То есть compress(corpus) длиннее compress(corpus+new_document). Это немного надумано, но, надеюсь, объясняет, как результат теоретически может выглядеть с помощью простой схемы. Я не говорю, что так происходит с bzip2, просто показываю, как это теоретически возможно.

Редактировать В другом ответе было упомянуто, что кодирование длин серий не является полным по Тьюрингу и поэтому не может использоваться для колмогоровской сложности. Хотя это действительно так, используя язык Тьюринга, вы можете реализовать кодировку длины выполнения на любом языке описания, который вы выберете, с тем же результатом, поэтому пример все еще остается действительным.

1 голос
/ 14 января 2011

Реальные алгоритмы сжатия имеют такие причуды, но в любом случае они дают только очень грубое приближение.

А что касается того, может ли это произойти в теории, возможно, но разница не значительна.

Предположим, у вас есть две строки, x и y, где x - это префикс y. Скажем, например, что

x = "asdfasdfasdfasdfasdfasdfasdfasdfasdf"

y = "asdfasdfasdfasdfasdfasdfasdfasdfasdf23452345234523452344523452452345234524345234"

Предположим также, что D - кратчайшее описание y. (Т.е. K (y) = | D |)

В этом случае x можно описать как | «число, описываемое D минус 46 символов» |, что длиннее, чем D, но только на небольшую константу и логарифмический коэффициент (количество символов в остальных инструкция в основном).

Может быть даже более короткое описание x, но мы знаем, что в худшем случае K (x) <= K (y) + log (| y | - | x |) </p>

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

(Примечание: приведенный выше пример RLE недопустим, поскольку RLE не является полным языком Тьюринга, поэтому его нельзя использовать в качестве языка описания для сложности Колмогорова.)

...