R - самая длинная общая подстрока

Question

Кто-нибудь знает о пакете R, который решает проблему самой длинной распространенной подстроки ? Я ищу что-то быстрое, что могло бы работать на векторах.

Answer 1

Проверьте " Rlibstree " пакет на тему омегахата: http://www.omegahat.org/Rlibstree/ .

Для этого используется http://www.icir.org/christian/libstree/ .

Answer 2

Посмотрите на функцию LCS пакета qualV . Он реализован на C, поэтому достаточно эффективен.

Answer 3

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

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

Подробности : amatch () принимает аргумент method , который вы можете указать как lcs , если хотите сопоставление на самой длинной общей подстроке. Есть много других вариантов для различных методов сопоставления строк (например, расстояние Левенштейна). Существует также обязательный аргумент maxDist . Если все строки в table больше " distance " из заданной строки в x , тогда amatch () вернет NA для этого элемента своего вывода. & Quot; расстояние & Quot; определяется по-разному в зависимости от выбранного вами алгоритма сопоставления строк. Для 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

Answer 4

Я не знаю R, но я использовал для реализации алгоритм Хиршберга, который быстр и не занимает слишком много места.

Насколько я помню, это всего 2 или 3 рекурсивно вызываемых коротких функции.

Вот ссылка: http://wordaligned.org/articles/longest-common-subsequence

Так что не стесняйтесь внедрять его в R, это стоит усилий, так как это очень интересный алгоритм.