有谁知道解决最长常见子字符串问题的 R 包？我正在寻找可以在向量上快速工作的东西。
问问题
5457 次
4 回答
4
于 2009-09-15T20:42:58.140 回答
1
你应该看看包的LCS功能qualV。它是 C 实现的，因此非常有效。
于 2015-10-12T18:10:56.507 回答
1
关于最长公共子串问题的解决方案的预期应用，这里的问题并不完全清楚。我遇到的一个常见应用是在不同数据集中的名称之间进行匹配。这个stringdist包有一个有用的功能amatch()，我觉得它适合这个任务。
简而言之，amatch()将输入两个向量，第一个是x要从中查找匹配的字符串向量（也可以是单个字符串），第二个是table要进行比较的字符串向量to 并选择具有最长公共子字符串的匹配项。 amatch()然后将返回一个长度等于的向量x- 此结果的每个元素将是table包含最佳匹配的索引。
详细信息：amatch()接受一个参数，如果您想匹配最长的公共子字符串method，您可以指定该参数。lcs对于不同的字符串匹配技术（例如 Levenshtein 距离），还有许多其他选项。还有一个强制性的maxDist论点。如果 in 中的所有字符串table与给定字符串 in 的“距离”更大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')
此外，与 from 之类的函数不同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
于 2018-06-05T17:31:24.727 回答
0
我不知道 R，但我曾经实现过 Hirschberg 的算法，该算法速度快且不占用太多空间。
我记得只有 2 或 3 个递归调用的短函数。
这是一个链接： http ://wordaligned.org/articles/longest-common-subsequence
所以不要犹豫在 R 中实现它，它值得付出努力，因为它是一个非常有趣的算法。
于 2009-09-15T20:57:52.410 回答