string - R中的算法/代码从字符串中的任何位置查找模式

Question

我想从任何给定字符串中的任何位置找到模式，以便该模式至少重复阈值次数。
例如，对于字符串“a0cc0vaaaabaaaabaaaabaa00bvw”，模式应该是“aaaab”。另一个例子:对于字符串“ff00f0f0f0f0f0f0f0f0000”，模式应该是“0f”。
在这两种情况下，阈值都被视为 3，即模式应至少重复 3 次。

如果有人可以建议 R 中的优化方法来找到解决此问题的方法，请与我分享。目前我通过使用 3 个嵌套循环来实现这一点，这需要很多时间。

谢谢!

Answer 1

find.string查找最大长度的子串受 (1) 子串必须连续重复至少 th次和 (2) 子串长度不能超过 len .

reps <- function(s, n) paste(rep(s, n), collapse = "") # repeat s n times

find.string <- function(string, th = 3, len = floor(nchar(string)/th)) {
    for(k in len:1) {
        pat <- paste0("(.{", k, "})", reps("\\1", th-1))
        r <- regexpr(pat, string, perl = TRUE)
        if (attr(r, "capture.length") > 0) break
    }
    if (r > 0) substring(string, r, r + attr(r, "capture.length")-1) else ""
}

这里有一些测试。最后一个测试在我的笔记本电脑上在 1.4 秒内处理了 James Joyce 的《尤利西斯》的全文:

> find.string("a0cc0vaaaabaaaabaaaabaa00bvw")
[1] "aaaab"
> find.string("ff00f0f0f0f0f0f0f0f0000")
[1] "0f0f"
> 
> joyce <- readLines("http://www.gutenberg.org/files/4300/4300-8.txt") 
> joycec <- paste(joyce, collapse = " ") 
> system.time(result <- find.string2(joycec, len = 25))

   user  system elapsed 
   1.36    0.00    1.39 
> result
[1] " Hoopsa boyaboy hoopsa!"

添加

尽管我在看到 BrodieG 之前就提出了我的答案，但正如他指出的那样，它们彼此非常相似。我在上面添加了他的一些功能以获得下面的解决方案并再次尝试测试。不幸的是，当我添加他的代码的变体时，James Joyce 示例不再有效，尽管它对显示的其他两个示例有效。问题似乎在于添加 len对代码的约束，并且可能代表上述代码的一个基本优势(即它可以处理这样的约束，并且这样的约束对于很长的字符串可能是必不可少的)。

find.string2 <- function(string, th = 3, len = floor(nchar(string)/th)) {
    pat <- paste0(c("(.", "{1,", len, "})", rep("\\1", th-1)), collapse = "")
    r <- regexpr(pat, string, perl = TRUE)
    ifelse(r > 0, substring(string, r, r + attr(r, "capture.length")-1), "")
}

> find.string2("a0cc0vaaaabaaaabaaaabaa00bvw")
[1] "aaaab"
> find.string2("ff00f0f0f0f0f0f0f0f0000")
[1] "0f0f"

> system.time(result <- find.string2(joycec, len = 25))
   user  system elapsed 
      0       0       0 
> result
[1] "w"

修订本应测试的 James Joyce 测试 find.string2实际上正在使用 find.string .现在已修复。