Анализ текстовых и возвращаемых сходств

Question

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

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

вернется

the.code.r00 

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

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

и вместе с тем, у меня есть следующий basenames тоже из другой URL-адресов

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

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

the.code.r 
the.matrix.r 

после разбора basenames я перечислил выше.

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

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

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

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

Answer 1

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

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

Answer 2

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

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