[R] Compact Patricia Trees (Tries)

[Gabor Grothendieck]

Using charmatch partial matches of 10,000 5 leters words to the same
list can be done in 10 seconds on my machine and 10,000 5 letter words
to 100,000 10 letter words in 1 minute.  Is that good enough?  Try
this simulation:

# generate N random words each k long
rwords <- function(N, k) {
   L <- sample(letters, N*k, replace = TRUE)
   apply(matrix(L, k), 2, paste, collapse = "")
}
w1 <- rwords(1e5, 10)
w2 <- rwords(1e4, 5)

system.time(charmatch(w2, w2))

system.time(charmatch(w2, w1))


On Thu, Apr 29, 2010 at 4:05 AM, Richard R. Liu <richard.liu at pueo-owl.ch> wrote:
> I have an application that a long list of character strings to determine which
> occur at the beginning of a given word.  A straight forward R script using grep
> takes a long time to run.  Rewriting it to use substr and match might be an
> option, but I have the impression that preparing the list as a trie and
> performing trie searches might lead to dramatic improvements in performance.
>
>
> I have searched the CRAN packages and find no packages that support Compact
> Patricia Trees.  Does anybody know of such?
>
>
> Thanks,
> Richard
>
> Richard R. Liu
> richard.liu at pueo-owl.ch
>
> ______________________________________________
> 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.
>