Вопрос здесь не совсем ясен относительно предполагаемого применения решения самой длинной общей проблемы подстрок. Распространенное приложение, с которым я сталкиваюсь, - это сопоставление имен в разных наборах данных. В пакете stringdist есть полезная функция amatch(), которая мне подходит для этой задачи.
Вкратце , amatch() будет принимать в качестве входных данных два вектора, первый - x вектор строк, из которых вы хотите найти совпадения (это также может быть просто одна строка), второй - table, который представляет собой вектор строк, с которыми вы хотите провести сравнение и выбрать совпадение с самой длинной общей подстрокой. amatch() вернет вектор, длина которого равна длине x - каждый элемент этого результата будет индексом в table, который содержит наилучшее совпадение.
Подробности : amatch() принимает аргумент method, который вы указываете равным lcs, если вы хотите сопоставить самую длинную общую подстроку. Есть много других вариантов для различных методов сопоставления строк (например, расстояние Левенштейна). Существует также обязательный аргумент maxDist. Если все строки в table находятся на большем «расстоянии» от заданной строки в x, то amatch() вернет NA для этого элемента своего вывода. «расстояние» определяется по-разному в зависимости от выбранного вами алгоритма сопоставления строк. Для lcs это (более или менее) просто означает, сколько существует различных (не совпадающих) символов. Подробности смотрите в документации.
Распараллеливание : еще одна приятная особенность amatch() заключается в том, что он автоматически распараллеливает операцию для вас, делая разумные предположения относительно использования системных ресурсов. Если вы хотите больше контроля над этим, вы можете переключить аргумент nthread.
Пример приложения :
library(stringdist)
Names1 = c(
"SILVER EAGLE REFINING, INC. (SW)",
"ANTELOPE REFINING",
"ANTELOPE REFINING (DOUGLAS FACILITY)"
)
Names2 = c(
"Mobile Concrete, Inc.",
"Antelope Refining, LLC. ",
"Silver Eagle Refining Inc."
)
Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)
Match_Idx
# [1] 3 2 2
Matches = data.frame(Names1, Names2[Match_Idx])
Matches
# Names1 Names2.Match_Idx.
# 1 silver eagle refining, inc. (sw) silver eagle refining inc.
# 2 antelope refining antelope refining, llc.
# 3 antelope refining (douglas facility) antelope refining, llc.
### Compare Matches:
Matches$Distance = stringdist(Matches$Names1, Matches$Match, method = 'lcs')
Кроме того, в отличие от таких функций, как LCS из qualV, здесь не учитываются совпадения «подпоследовательности», которые включают игнорирование промежуточных символов для формирования соответствия (как обсуждено здесь ). Например, посмотрите это:
Names1 = c(
"hello"
)
Names2 = c(
"hel123l5678o",
"hell"
)
Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)
Matches = data.frame(Names1, Match = Names2[Match_Idx])
Matches
# 1 hello hell