algorithm/code in R to find pattern from any position in a string

Question

I want to find the pattern from any position in any given string such that the pattern repeats for a threshold number of times at least. For example for the string "a0cc0vaaaabaaaabaaaabaa00bvw" the pattern should come out to be "aaaab". Another example: for the string "ff00f0f0f0f0f0f0f0f0000" the pattern should be "0f". In both cases threshold has been taken as 3 i.e. the pattern should be repeated for at least 3 times.

If someone can suggest an optimized method in R for finding a solution to this problem, please do share with me. Currently I am achieving this by using 3 nested loops, and it's taking a lot of time.

Thanks!

Answer 1

find.string finds substring of maximum length subject to (1) substring must be repeated consecutively at least th times and (2) substring length must be no longer than 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 ""
}

and here are some tests. The last test processes the entire text of James Joyce's Ulysses in 1.4 seconds on my laptop:

> 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!"

ADDED

Although I developed my answer before having seen BrodieG's, as he points out they are very similar to each other. I have added some features of his to the above to get the solution below and tried the tests again. Unfortunately when I added the variation of his code the James Joyce example no longer works although it does work on the other two examples shown. The problem seems to be in adding the len constraint to the code and may represent a fundamental advantage of the code above (i.e. it can handle such a constraint and such constraints may be essential for very long strings).

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"

REVISED The James Joyce test that was supposed to be testing find.string2 was actually using find.string. This is now fixed.

Answer 2

Use regular expressions, which are made for this type of stuff. There may be more optimized ways of doing it, but in terms of easy to write code, it's hard to beat. The data:

vec <- c("a0cc0vaaaabaaaabaaaabaa00bvw","ff00f0f0f0f0f0f0f0f0000")    

The function that does the matching:

find_rep_path <- function(vec, reps) {
  regexp <- paste0(c("(.+)", rep("\\1", reps - 1L)), collapse="")
  match <- regmatches(vec, regexpr(regexp, vec, perl=T))
  substr(match, 1, nchar(match) / reps)  
}

And some tests:

sapply(vec, find_rep_path, reps=3L)
# a0cc0vaaaabaaaabaaaabaa00bvw      ff00f0f0f0f0f0f0f0f0000 
#                      "aaaab"                       "0f0f" 
sapply(vec, find_rep_path, reps=5L)
# $a0cc0vaaaabaaaabaaaabaa00bvw
# character(0)
# 
# $ff00f0f0f0f0f0f0f0f0000
# [1] "0f"

Note that with threshold as 3, the actual longest pattern for the second string is 0f0f, not 0f (reverts to 0f at threshold 5). In order to do this, I use back references (\\1), and repeat these as many time as necessary to reach threshold. I need to then substr the result because annoyingly base R doesn't have an easy way to get just the captured sub expressions when using perl compatible regular expressions. There is probably a not too hard way to do this, but the substr approach works well in this example.

---

Also, as per the discussion in @G. Grothendieck's answer, here is the version with the cap on length of pattern, which is just adding the limit argument and the slight modification of the regexp.

find_rep_path <- function(vec, reps, limit) {
  regexp <- paste0(c("(.{1,", limit,"})", rep("\\1", reps - 1L)), collapse="")
  match <- regmatches(vec, regexpr(regexp, vec, perl=T))
  substr(match, 1, nchar(match) / reps)  
}
sapply(vec, find_rep_path, reps=3L, limit=3L)
# a0cc0vaaaabaaaabaaaabaa00bvw      ff00f0f0f0f0f0f0f0f0000 
#                          "a"                         "0f" 

Answer 3

For a bounded pattern (i.e not huge) it's best I think to just create all possible substrings first and then count them. This is if the sub-patterns can overlap. If not change the step fun in the loop.

pat="a0cc0vaaaabaaaabaaaabaa00bvw"
len=nchar(pat)
thr=3
reps=floor(len/2)

# all poss strings up to half length of pattern
library(stringr)
pat=str_split(pat, "")[[1]][-1]
str.vec=vector()
for(win in 2:reps)
 {
     str.vec= c(str.vec, rollapply(data=pat,width=win,FUN=paste0, collapse=""))
 }

# the max length string repeated more than 3 times
tbl=table(str.vec)
tbl=tbl[tbl>=3]
tbl[which.max(nchar(names(tbl)))]

aaaabaa 
      3 

NB Whilst I'm lazy and append/grow the str.vec here in a loop, for a larger problem I'm pretty sure the actual length of str.vec is predetermined by the length of the pattern if you care to work it out.

Answer 4

Not optimized (even it is fast) function , but I think it is more R way to do this.

1. Get all patterns of certains length > threshold : vectorized using mapply and substr
2. Get the occurrence of these patterns and extract the one with maximum occurrence : vectorized using str_locate_all.
3. Repeat 1-2 this for all lengths and tkae the one with maximum occurrence.

Here my code. I am creating 2 functions ( steps 1-2) and step 3:

library(stringr)
ss = "ff00f0f0f0f0f0f0f0f0000" 
ss <- "a0cc0vaaaabaaaabaaaabaa00bvw"
find_pattern_length <- 
function(length=1,ss){
  patt = mapply(function(x,y) substr(ss,x,y),
                1:(nchar(ss)-length),
                (length+1):nchar(ss))
  res = str_locate_all(ss,unique(patt))
  ll = unlist(lapply(res,length))
  list(patt = patt[which.max(ll)],
       rep = max(ll))
}

get_pattern_threshold <- 
function(ss,threshold =3 ){
  res <- 
  sapply(seq(threshold,nchar(ss)),find_pattern_length,ss=ss)
  res[,which.max(res['rep',])]
}

some tests:

get_pattern_threshold('ff00f0f0f0f0f0f0f0f0000',5)
$patt
[1] "0f0f0"

$rep
[1] 6

> get_pattern_threshold('ff00f0f0f0f0f0f0f0f0000',2)
$patt
[1] "f0"

$rep
[1] 18

Answer 5

Here is my solution, it's not optimized (build vector with patterns <- c() ; pattern <- c(patterns, x) for example) and can be improve but simpler than yours, I think.

I can't understand which pattern exactly should (I just return the max) be returned but you can adjust the code to what you want exactly.

str <- "a0cc0vaaaabaaaabaaaabaa00bvw"

findPatternMax <- function(str){

  nb <- nchar(str):1
  length.patt <- rev(nb)
  patterns <- c()

  for (i in 1:length(nb)){
    for (j in 1:nb[i]){
      patterns <- c(patterns, substr(str, j, j+(length.patt[i]-1)))
    }
  }
  patt.max <- names(which(table(patterns) == max(table(patterns))))
  return(patt.max)
}


  findPatternMax(str)

  > findPatternMax(str)
  [1] "a"

EDIT : Maybe you want the returned pattern have a min length ?

then you can add a nchar.patt parameter for example :

nchar.patt <- 2 #For a pattern of 2 char min

nb <- nb[length.patt >= nchar.patt]

length.patt <- length.patt[length.patt >= nchar.patt]

Answer 6

Since you want at least three repetitions, there is a nice O(n^2) approach.

For each possible pattern length d cut string into parts of length d. In case of d=5 it would be:

a0cc0
vaaaa
baaaa
baaaa
baa00
bvw

Now look at each pairs of subsequent strings A[k] and A[k+1]. If they are equal then there is a pattern of at least two repetitions. Then go further (k+2, k+3) and so on. Finally you also check if suffix of A[k-1] and prefix of A[k+n] fit (where k+n is the first string that doesn't match).

Repeat it for each d starting from some upper bound (at most n/3).

You have n/3 possible lengths, then n/d strings of length d to check for each d. It should give complexity O(n (n/d) d)= O(n^2).

Maybe not optimal but I found this cutting idea quite neat ;)