Я изучил кое-что о сложности Колмогорова , прочитал некоторые статьи и книги Витани и Ли и использовал концепцию нормализованного расстояния сжатия для проверки стилометрии авторов (определите, как каждый автор пишет некоторые текстовые и групповые документы по их сходству).
В этом случае компрессоры данных использовались для аппроксимации сложности Колмогорова, поскольку компрессор данных можно было использовать в качестве машины Тьюринга.
Помимо языков сжатия данных и языков программирования (на которых вы бы написали какой-нибудь компрессор), что еще можно использовать для аппроксимации колмогоровской сложности? Есть ли другие подходы, которые можно использовать?
Ответы:
Я предполагаю , что один возможный ответ на ваш вопрос заключается в следующем: Возьмите псевдослучайных чисел генератор . Попробуйте выбрать генератор, который имеет несколько мощных атак против него: атака генератора случайных чисел для G - это (для наших целей) алгоритм A, который при заданной строке s определяет начальное число A ( s ) , такое что G ( A ( s ) ) = s . Затем приблизьте KC s :грамм грамм A s A ( s ) G ( A ( s ) ) = s s
Где это длина программы, которая вычисляет G ( s ) (часто довольно короткая, как для линейных генераторов).| G | G ( s )
Обратите внимание, что на практике атаки генератора случайных чисел выполняются не так, как описано: они могут дать сбой или привести к неполным результатам. В этом случае вы можете адаптировать алгоритм так, чтобы он возвращал когда результат атаки неудовлетворительный. То же самое относится и к алгоритмам сжатия.| с |
Предостережение в этом подходе в отличие от алгоритмов сжатия заключается в том, что алгоритмы сжатия в целом гораздо больше подходят для вычисления KC, поскольку они приспособлены для работы с любой строкой, тогда как атака может работать, только если оказывается в образе G ( очень маловероятно ).s грамм
источник
Вот почему сложность Колмогорова так интересна не потому, что это лучший алгоритм сжатия (который все равно заботится о сжатии), а потому, что это лучший алгоритм обучения . Сжатие и обучение - это одно и то же: поиск шаблонов в ваших данных. Статистическая структура, построенная на этой идее, называется «Минимальная длина описания», и она была непосредственно вдохновлена колмогоровской сложностью.
Смотрите также этот вопрос в разделе StackExchange.
источник
грамматическое кодирование является менее часто используемой версией алгоритма сжатия и может рассматриваться как «грубая» оценка колмогоровской сложности. Грамматическое кодирование не так часто используется в качестве алгоритма сжатия, как другие более распространенные подходы, возможно, в основном потому, что оно не сильно улучшает сжатие, например, из Lempel-Ziv в текстовых корпусах, но оно может хорошо работать с другими видами данных. идея состоит в том, чтобы «сжать» строку, используя правила грамматики. вывод грамматики может привести к созданию DAG (по сравнению с менее сложным деревом), поэтому возможна существенная сложность представления.
Другой вариант - найти наименьшие / минимальные схемы, представляющие строку, но известно, что это имеет очень высокую сложность вычислений и может быть успешным только для небольших строк.
Существуют также другие методы алгоритма сжатия, кроме подходов типа «кодирование длины серий» Лемпеля-Зива, например, векторная алгебра и SVD могут использоваться в качестве алгоритма сжатия. также преобразования Фурье часто используются для сжатия изображений, например, в стандарте JPG.
источник