In ezgraphs/rtrie: A Simple R-Based Implementation of a Trie (A.k.a. Digital Tree/Radix Tree/Prefix Tree)

Other Trie Packages

The rtrie package provides a few simple functions to support tries representing lists of words. Other R packages on CRAN provide trie implementations with different characteristics including:

• triebeard
• AhoCorasickTrie

Also see various packages related to trees in general.

Trie Creation

A list of words can be created programatically or read from a data file or other source.

  words<-read.delim(
    file=system.file("extdata", "dictionary.txt", package = "rtrie"), 
    header=F, sep = " ",
    stringsAsFactors = FALSE)
  class(words)

In this case a data frame was created from a file. Creating a trie involves a simple function call to the char_tree function. A trie is created from a vector passed as an argument (in this case column V1 from the data frame).

trie <- char_tree(words$V1, 'X')

To get an idea of the performance, the file in question contained r length(words$V1) words. The microbenchmark library can be used for timing.

  library(rtrie)
  library(microbenchmark)
  timings <- microbenchmark(
    trie <- char_tree(words$V1, 'X'), 
    times=1
  )

  print(paste(timings$time / 1000000000, 'seconds'))

Match the Beginning of Words

What are words that start with "stu".

cat(matching_words('stu',trie))

Test if a Character String is a Word

Is "stunt" a word?

cat(is_word('stunt',trie))

How about "stu"?

cat(is_word('stu',trie))

ezgraphs/rtrie documentation built on May 16, 2019, 9:57 a.m.