[R] Compact Patricia Trees (Tries)

[Richard R. Liu]

Gabor,

Thanks for the hint to use charmatch.  It is faster than what I was  
doing, but I suspect it might still be suboptimal.  I have a list of  
words, and I want to know which of those exactly or partially match  
one word.  By the very description of charmatch's arguments, the  
second being "table", I suspect, if it's investing any time at all in  
creating a structure that it can search more efficiently, it's going  
it with "table", not with the first argument "x".  I suspect that the  
time difference in favor of charmatch is due to the fact that it's  
doing natively what I was doing with R script, i.e., comparing each  
element of the first argument to a substring of the second argument  
with the same length as the element.

Any insights?

Regards,
Richard

Richard R. Liu
Dittingerstr. 33
CH-4053 Basel
Switzerland

Tel.:  +41 61 331 10 47
Mobil: +41 79 708 67 66
Email:  richard.liu at pueo-owl.ch



On Apr 29, 2010, at 13:06 , Gabor Grothendieck wrote:

> 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.
>>
>