Сравнение html кода страниц на схожесть %

134

25 августа 2019, 19:10

Есть некий парсер на php который собирает данные с сайтов. Задача сравнить исходные коды анализируемых сайтов на схожесть в %, для поиска сайтов сделанных по одному шаблону.

В данный момент реализовал так:
Сохраняю в базу исходный код каждой каждого сайта и сравниваю со всеми имеющимися с помощью стандартной функции similar_text. С задачей она справляется и точность достаточно высокая, НО! ввиду сложности алгоритма этой функции она очень долго работает и "отжирает" весь процессор, соответственно когда сайтов стало больше 1000, время работы и нагрузка на сервер сильно увеличились.

Вопрос:
Существуют ли упрощенные реализации similar_text() на php или какие-то другие методы, или есть ли возможность сделать такое сравнение сразу в mysql?
Спасибо!

Answer 1

В документации говорится, что similar_text работает за O(n3).

Расстояние Левенштейна (levenshtein) работает за O(n2), что существенно быстрее, но может быть по-прежнему недостаточно быстро. Думаю, гораздо эффективнее будет применить расстояние Левенштейна не на символах, а на токенах, только это придётся реализовать самостоятельно. Возможно даже, что это будет уже достаточно быстро, а может и нет.