Схожесть пути URL / алгоритм схожести строк

Question

Моя проблема в том, что мне нужно сравнить пути URL-адресов и сделать вывод, если они похожи. Ниже приведен пример данных для обработки:

# GROUP 1
/robots.txt

# GROUP 2
/bot.html

# GROUP 3
/phpMyAdmin-2.5.6-rc1/scripts/setup.php
/phpMyAdmin-2.5.6-rc2/scripts/setup.php
/phpMyAdmin-2.5.6/scripts/setup.php
/phpMyAdmin-2.5.7-pl1/scripts/setup.php
/phpMyAdmin-2.5.7/scripts/setup.php
/phpMyAdmin-2.6.0-alpha/scripts/setup.php
/phpMyAdmin-2.6.0-alpha2/scripts/setup.php

# GROUP 4
//phpMyAdmin/

Я пытался сравнить расстояние Левенштейна, но для меня это недостаточно точно. Мне не нужен 100% точный алгоритм, но я думаю, что 90% и выше - это необходимость.

Я думаю, что мне нужен какой-то классификатор, но проблема в том, что каждая часть новых данных может содержать путь, который следует классифицировать для нового неизвестного класса.

Не могли бы вы, пожалуйста, направить меня в нужное место?

Спасибо

Answer 1

Расстояние Левенштейна - лучший вариант, но настроенное расстояние.Вы должны использовать взвешенное расстояние редактирования и, возможно, разделить путь на токены - слова и числа.Так, например, такие версии, как «2.5.6-rc2 и 2.5.6», можно рассматривать как разницу в 0 весов, а токены имен, такие как phpMyAdmin и javaMyAdmin, дают разницу в 1 вес.

Answer 2

При проверке предложения @ jakub.gieryluk я случайно нашел решение, которое меня устраивает - «Алгоритм кластеризации Хобома, изначально разработанный для уменьшения избыточности наборов данных биологических последовательностей».

Тесты библиотеки PERL реализованы Bruno Vecchi дал мне действительно хорошие результаты.Единственная проблема заключается в том, что мне нужна реализация Python, но я верю, что могу найти ее в Интернете или переопределить код самостоятельно.

Следующим шагом является то, что я еще не проверял способность этого алгоритма к активному обучению;)

Answer 3

Я знаю, что это не точный ответ на ваш вопрос, но вы знакомы с алгоритмом k-means ?

Я думаю, что даже Левенштейн может работать здесь, однако трудность заключается в том, какдля вычисления центроидов с таким подходом.

Возможно, вы можете разделить входной набор на непересекающиеся подмножества, а затем для каждого URL-адреса в каждом подмножестве вычислить расстояние до всех других URL-адресов в том же подмножестве и URL-адрес с наименьшей суммойрасстояний, должен быть центром тяжести (конечно, это зависит от того, насколько велик входной набор; для больших наборов это может быть не очень хорошей идеей).

Хорошая вещь о k-средних состоит в том, чточто вы можете начать с абсолютно случайного деления, а затем итеративно сделать его лучше.

Плохая вещь в k-означает, что вам нужно уточнить k перед началом.Тем не менее, во время выполнения (возможно, когда ситуация стабилизировалась после первых нескольких итераций), вы можете измерить внутрисходство каждого набора, а если оно низкое, вы можете разделить набор на два подмножества и продолжить работу по одному и тому же алгоритму.