Публикации
Печников А.А., Прусский Д.А.
Программы-архиваторы для вычисления колмогоровской сложности
// Международный журнал прикладных и фундаментальных исследований. № 7. 2019. C. 118–123
Ключевые слова: Колмогоровская сложность, нормализованное расстояние сжатия, программа-архиватор, веб-сайт, кластерный анализ
В предыдущих работах одного из авторов был предложен подход к исследованию схожести веб-сайтов с использованием Колмогоровской сложности и нормализованного расстояния сжатия, показывающий определенный потенциал такого подхода. При этом сформулирован ряд вопросов, на которые требуется ответить, прежде чем автоматизировать проведение больших исследований. Один из этих вопросов относится к программам-архиваторам, используемым на практике в качестве так называемого способа описания, и заключается он в том, можно ли выбрать наилучший архиватор. Этот вопрос подробно исследуется в данной статье. Авторами была проведена серия экспериментов с девятью наиболее популярными и доступными архиваторами, позволившая на практике проверить выполнение свойств идемпотентности, монотонности, симметричности и дистрибутивности для этих программ. Четыре наилучших архиватора были экспериментально проверены на выполнение аксиом расстояния для нормализованного расстояния сжатия, вычисляемого с их использованием, и показано их выполнение. Все этапы экспериментов были автоматизированы с помощью разработанных вспомогательных программ для скачивания первых страниц сайтов в формате html, создания конкатенаций файлов, сжатия файлов различными архиваторами и вычисления нормализованного расстояния сжатия. Авторы остановились на программе RAR, как наиболее удобной в использовании, и с её помощью на конкретном примере провели иерархическую кластеризацию заданного множества сайтов, практически полностью соответствующую компаниям – разработчикам сайтов, что свидетельствует о выявлении стиля разработки сайтов, присущего каждой компании, с помощью предложенного подхода и «наилучшего» архиватора.
Индексируется в РИНЦ
Последние изменения: 4 июня 2021