R help - Aug 2012 - Search for locations of subsequences?

Is there a function to efficiently search for a subsequence within a vector?

For example, with

x <- 1:100

I'd like to search for the sequence c(49,50,51), and be told that it 
occurs exactly once, starting at location 49.  (The items in the vectors 
might be numeric or character, and there might be repetitions within the 
search pattern or within the vector I'm searching.)

Duncan Murdoch

On Aug 28, 2012, at 4:05 PM, Duncan Murdoch <murdoch.duncan at gmail.com>
wrote:
> Is there a function to efficiently search for a subsequence within a
vector?
> 
> For example, with
> 
> x <- 1:100
> 
> I'd like to search for the sequence c(49,50,51), and be told that it
occurs exactly once, starting at location 49.  (The items in the vectors might
be numeric or character, and there might be repetitions within the search
pattern or within the vector I'm searching.)
> 
> Duncan Murdoch

There is a thread here:

  http://tolstoy.newcastle.edu.au/R/e17/help/12/02/4201.html

that has various solutions and towards the end has a post with some timings.

Regards,

Marc Schwartz

Hello,

Try the following.

occur1 <- function(pat, vec){
     m <- length(pat)
     n <- length(vec)
     candidate <- seq.int(length=n-m+1)
     for (i in seq.int(length=m))
         candidate <- candidate[pat[i] == vec[candidate + i - 1]]
     candidate
}

patrn <- c(1,2,3,4)
exmpl <- c(3,3,4,2,3,1,2,3,4,8,8,23,1,2,3,4,4,34,4,3,2,1,1,2,3,4)

occur1(patrn, exmpl)
[1]  6 13 23

This was posted some time ago. And seems to be the fastest of the 7 
solutions.
https://stat.ethz.ch/pipermail/r-help/2012-February/303756.html

Hope this helps,

Rui Barradas

Em 28-08-2012 22:05, Duncan Murdoch escreveu:
> Is there a function to efficiently search for a subsequence within a 
> vector?
>
> For example, with
>
> x <- 1:100
>
> I'd like to search for the sequence c(49,50,51), and be told that it 
> occurs exactly once, starting at location 49.  (The items in the 
> vectors might be numeric or character, and there might be repetitions 
> within the search pattern or within the vector I'm searching.)
>
> Duncan Murdoch
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide 
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

On 12-08-28 5:45 PM, Rui Barradas wrote:
> Hello,
>
> Try the following.
>
> occur1 <- function(pat, vec){
>       m <- length(pat)
>       n <- length(vec)
>       candidate <- seq.int(length=n-m+1)
>       for (i in seq.int(length=m))
>           candidate <- candidate[pat[i] == vec[candidate + i - 1]]
>       candidate
> }
>
> patrn <- c(1,2,3,4)
> exmpl <- c(3,3,4,2,3,1,2,3,4,8,8,23,1,2,3,4,4,34,4,3,2,1,1,2,3,4)
>
> occur1(patrn, exmpl)
> [1]  6 13 23
>
> This was posted some time ago. And seems to be the fastest of the 7
> solutions.
> https://stat.ethz.ch/pipermail/r-help/2012-February/303756.html
Thanks!

Duncan Murdoch

Hello,

Function Biostrings::matchPattern can be called with an algorithm = 
"boyer-moore" argument.
I've never used it, this is the return value of

library(sos)
r1 <- findFn('boyer')
r2 <- findFn('moore')
r1 & r2

I have implemented the Boyer-Moore algorithm a couple of times, the 
first(!) of all in 8086 assembly, but I'm seeing a difficulty regarding 
your original request.
A Boyer-Moore algorithm to search for subsequences of character vectors 
all of which such that nchar(x) is 1 should be very easy to implement 
using the .Call interface, but for integer vectors I am not seeing how 
to implement the bad character shift table. What would be the alphabet? 
The set of 32-bit integers? In this case the table length would be 
prohibitive...

Ideas anyone?

Rui Barradas

Em 28-08-2012 22:05, Duncan Murdoch escreveu:
> Is there a function to efficiently search for a subsequence within a 
> vector?
>
> For example, with
>
> x <- 1:100
>
> I'd like to search for the sequence c(49,50,51), and be told that it 
> occurs exactly once, starting at location 49.  (The items in the 
> vectors might be numeric or character, and there might be repetitions 
> within the search pattern or within the vector I'm searching.)
>
> Duncan Murdoch
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide 
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.