在两个字符变量之间查找共同的子字符串

Question

我有两个字符变量（对象名称），我想提取它们之间最大的共同子字符串。

a <- c('blahABCfoo', 'blahDEFfoo')
b <- c('XXABC-123', 'XXDEF-123')

I want the following as a result:

[1] "ABC" "DEF"

这些向量作为输入应该得到相同的结果：

a <- c('textABCxx', 'textDEFxx')
b <- c('zzABCblah', 'zzDEFblah')

这些示例是代表性的。字符串包含标识元素，每个向量元素中其余文本是常见的，但未知的。

是否在以下位置之一（按优先顺序）中有解决方案：

1. 基本 R 2. 推荐的软件包 3. 可在 CRAN 上获得的软件包

所谓重复问题的答案不满足这些要求。

- Matthew Lundberg

---

还有这个：http://finzi.psych.upenn.edu/R/Rhelp02a/archive/68013.html - Maxim.K

http://svitsrv25.epfl.ch/R-doc/library/Biostrings/html/pmatchPattern.html，以及这个http://www.emoticode.net/r/longest-common-substring.html - Maxim.K

我正在寻找一个基础函数，或者是一个推荐包中的内容（可以在CRAN上获取）。 - Matthew Lundberg

@JoshO'Brien，我找不到 Rlibstree。你能安装成功吗？ - GSee

@MatthewLundberg，你所拥有的是最长的非公共子串，不是吗？对于你的第一个例子，LCS 是 blah。 - Arun

Answer 1

这里有一个适用于CRAN的软件包：

library(qualV)

sapply(seq_along(a), function(i)
    paste(LCS(strsplit(a[i], '')[[1]], strsplit(b[i], '')[[1]])$LCS,
          collapse = ""))

- eddi

---

(+1) 用于CRAN包。虽然我觉得这个函数的输入非常奇怪，但是它很明显要求用户创建所有后缀。为什么要让用户这样做呢？好的一点是他们在C中有自己的LCS实现。 - Arun

@Arun，是的，我理解你所说的内容，我的意思是该软件包以处理数字向量为中心，而此函数旨在成为LCSequence，这是LCSubstring的概括。如果有人为字符串编写了专门版本当然会很好，但无论如何都可以。 - eddi

@ConfusedMan，这个链接是否描述了你的问题：https://dev59.com/e14c5IYBdhLWcg3wJnb8？你是否期望的输出只有“'AR '”而不是“'AR I'”？ - Nate Anderson

此外，我认为用strsplit(a[i],'')[[1]]替换substring(a[i], seq(1, nchar(a[i])), seq(1, nchar(a[i])))更容易。起初我只是觉得这样更易读。但是[这个网站]表明，strsplit(...)也更高效。 - Nate Anderson

最后，只要LCS被设计为接受向量，这里是字符串转向量的翻译：function(a,b){ av <- strsplit(a,'')[[1]]; bv <- strsplit(b,'')[[1]]; return(paste(LCS(av,bv)$LCS, collapse='')); } - Nate Anderson

Answer 2

如果您不介意使用Bioconductor软件包，那么您可以使用 Rlibstree。安装过程非常简单。

source("http://bioconductor.org/biocLite.R")
biocLite("Rlibstree") 

然后，您可以执行以下操作：

require(Rlibstree)
ll <- list(a,b)
lapply(data.frame(do.call(rbind, ll), stringsAsFactors=FALSE), 
           function(x) getLongestCommonSubstring(x))

# $X1
# [1] "ABC"

# $X2
# [1] "DEF"

---

顺便说一句：我不确定 Rlibstree 是否使用 libstree 0.42 或者 libstree 0.43。源代码包中都有这两个库。我记得在一个使用了 libstree 0.42 的巨大 perl 数组上遇到了内存泄漏（导致错误）。提醒一下。

- Arun

Answer 3

因为我有太多不想做的事情，所以我做了这个：

Rgames> for(jj in 1:100) {
+ str2<-sample(letters,100,rep=TRUE)
+ str1<-sample(letters,100,rep=TRUE)
+ longs[jj]<-length(lcstring(str1,str2)[[1]])
+ }
Rgames> table(longs)
longs
 2  3  4 
59 39  2

有人愿意对匹配字符串的实际分布进行统计估计吗？ （lcstring只是一个暴力自制函数；输出包含所有最大字符串，这就是为什么我只看第一个列表元素的原因）

- Carl Witthoft