Разбор текста и возврат сходства

Question

Допустим, у меня есть несколько URL-адресов, и я возвращаю базовое имя для каждого URL-адреса, например,

http://www.test.com/the.code.r00

вернется

the.code.r00

и у меня есть несколько базовых имен, которые я извлек из нескольких URL для работы на

the.code.r00
the.code.r01
..
...
the.code.r12

и вместе с ними у меня есть следующие базовые имена с других URL

the.matrix.r00
the.matrix.r01
..
...
the.matrix.r14

Я хотел бы знать, есть ли известный алгоритм, который был проверен и доказал, что он возвращает

the.code.r
the.matrix.r

после разбора базовых имен, которые я перечислил выше.

Также, если вместо этого есть какой-нибудь * nix инструмент, который делает то же самое, что было бы супер.

Обратите внимание, что формат не всегда такой, как выше, иначе я мог бы сделать простую подстроку. Числа не всегда перечислены в определенном месте строки. Некоторые другие примеры;

the.code.part01.rar
the.code.001
..
....

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

Answer 1

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

Как только вы это сделаете, делайте то же самое со строками LCS, пока не достигнете некоторого порога.

Answer 2

Посмотрите на каждую пару строк в вашем списке и вычислите Расстояние Левенштейна (он же расстояние редактирования строки) между ними. Это даст вам минимальное количество изменений, необходимых для замены одной строки на другую.

Теперь получим из реализации Левенштейна фактический набор изменений между строками (следуя обратным указателям в динамической программе). Если этот набор изменений состоит только из замены чисел другими числами, то вы нашли шаблон. Скопируйте одну из строк, удалите эти числа, сохраните ее в наборе шаблонов и продолжите работу с другими парами строк.