在一组字符串中找到最长的公共起始子串的R实现

Question

在一组字符串中找到最长的公共起始子串的R实现

rstring

5

这个问题只是要求在R中实现以下问题：查找一组字符串中的最长公共起始子串（JavaScript）。

"这个问题是最长公共子串问题的一个更具体的案例。我只需要在数组中找到最长的公共起始子串。"

因此，我只是在寻找此问题的R实现（最好不要使用JavaScript版本中建议的for / while循环方式），如果可能，我想将其封装为一个函数，以便我可以在数据表中应用于许多组。

经过一些搜索，我无法找到此问题的R示例，因此提出了这个问题。

示例数据：我有以下字符向量：

dput(data)
c("ADA4417-3ARMZ-R7", "ADA4430-1YKSZ-R2", "ADA4430-1YKSZ-R7", 
"ADA4431-1YCPZ-R2", "ADA4432-1BCPZ-R7", "ADA4432-1BRJZ-R2")

我希望您能在R中运行一个算法，该算法将找到以下输出：ADA44。

从我在JavaScript答案中看到的内容，想法是首先对向量进行排序，提取第一个和最后一个元素（例如："ADA4417-3ARMZ-R7"和"ADA4432-1BRJZ-R2"），将它们分解为单个字符，并循环遍历它们，直到其中一个字符不匹配（希望我的理解是正确的）。

如果您能提供任何帮助，那就太好了！

- Yehoshaphat Schellekens

4个回答

5

使用 Biostrings 中的 lcprefix 函数来查找两个字符串的“最长公共前缀”，这是一种非 base 的替代方法。

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

x2 <- sort(x)
substr(x2[1], start = 1, stop = lcprefix(x2[1], x2[length(x2)]))
# [1] "ADA44"

- Henrik

谢谢@Henrik，有没有理由相信这会比基本版本更快？ - Yehoshaphat Schellekens

1

@YehoshaphatSchellekens Biostrings主页上的措辞听起来很有前途：“内存高效的字符串容器、字符串匹配算法和其他实用程序，可快速操作大型生物序列或序列集。”，但我认为您需要进行一些基准测试。此外，请注意?lcprefix上的警告。我怀疑substr不是瓶颈，但您可以使用stringi::stri_sub来缩短一些微秒。 - Henrik

2

借鉴Henrik的回答，Bioconductor有一个基于C的前缀函数和一个基于R的函数。其中，基于R的函数如下所示：

lcPrefix <- function (x, ignore.case = FALSE) 
{
    x <- as.character(x)
    if (ignore.case) 
        x <- toupper(x)
    nc <- nchar(x, type = "char")
    for (i in 1:min(nc)) {
        ss <- substr(x, 1, i)
        if (any(ss != ss[1])) {
            return(substr(x[1], 1, i - 1))
        }
    }
    substr(x[1], 1, i)
}
<environment: namespace:Biobase>

据我所知，这段内容与生物信息学软件包Bioconductor没有特殊的要求。

--- 引用 ---

与Bioconductor协调高通量基因组分析。 W. Huber，V.J. Carey，R. Gentleman等人，M. Morgan Nature Methods,
2015:12, 115。

- russellpierce

1

这是一个简洁的解决方案：

data<-c("ADA4417-3ARMZ-R7", "ADA4430-1YKSZ-R2", "ADA4430-1YKSZ-R7", "ADA4431-1YCPZ-R2", "ADA4432-1BCPZ-R7", "ADA4432-1BRJZ-R2")

substr(data[1],1,which.max(apply(do.call(rbind,lapply(strsplit(data,''),`length<-`,nchar(data[1]))),2,function(i)!length(unique(i))==1))-1)
[1] "ADA44"

- Catherine Smith

这行代码既糟糕又棒极了，但还是谢谢分享！ :) - Ni-Ar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cath · Accepted Answer

从您提出的建议中汲取灵感，您可以尝试这个函数：

comsub<-function(x) {
    # sort the vector
    x<-sort(x)
    # split the first and last element by character
    d_x<-strsplit(x[c(1,length(x))],"")
    # compute the cumulative sum of common elements
    cs_x<-cumsum(d_x[[1]]==d_x[[2]])
    # check if there is at least one common element
    if(cs_x[1]!=0) {
        # see when it stops incrementing and get the position of last common element
        der_com<-which(diff(cs_x)==0)[1]
        # return the common part
        return(substr(x[1],1,der_com))
    } else { # else, return an empty vector
        return(character(0))
    }
}

更新

根据 @nicola 的建议，这个函数有了一个更简单、更优雅的变体：

comsub<-function(x) {
    # sort the vector
    x<-sort(x)
    # split the first and last element by character
    d_x<-strsplit(x[c(1,length(x))],"")
    # search for the first not common element and so, get the last matching one
    der_com<-match(FALSE,do.call("==",d_x))-1
    # if there is no matching element, return an empty vector, else return the common part
    ifelse(der_com==0,return(character(0)),return(substr(x[1],1,der_com)))
}

示例：

使用您的数据

x<-c("ADA4417-3ARMZ-R7", "ADA4430-1YKSZ-R2", "ADA4430-1YKSZ-R7", 
"ADA4431-1YCPZ-R2", "ADA4432-1BCPZ-R7", "ADA4432-1BRJZ-R2")
> comsub(x)
#[1] "ADA44"

当没有公共的起始子串时

x<-c("abc","def")
> comsub(x)
# character(0)