reasytries

The reasytries package contains classes and functions that efficiently store and search words passed by the user based on a trie data structure.

This package was developed as a project for UBC MDS-Vancouver program DSCI 524 course.

Installation

This package is not yet available on CRAN. Therefore, you will have to install the latest version of reasytries from GitHub with:

# install.packages("devtools")
devtools::install_github("UBC-MDS/reasytries")

Overview

Storing and searching words can be expensive in terms of time and computing: for example, using a balanced binary search tree, the time complexity for searching a word is (O(mlogn)), where (m) is the length of the word and (n) is the number of keys in the tree. However, with the trie data structure, the time complexity for searching can be reduced to (O(m)). The reasytries package is a simple tool to aid word insertion, deletion, and searching in the trie data structure. Users can pass any words to be stored for later-on searching or printing with certain prefix, and even modify the words in storage.

Dependencies

R 4.0.2

rlang 0.4.10

Documentation

The official documentation can be found here

Features

Classes

• Class Trie: Conceptual class representation of a trie

Functions

• trie_create() function initializes an empty trie

• trie_add(trie, word_to_add) function takes in a trie and a word_to_add to store each letter of the new word in the trie data structure.

• trie_contain(trie, word) function takes in a trie and a word to search through the trie structure and check if the word has been stored in the trie already.

• trie_find_prefix(trie, prefix) function takes in a trie and a prefix to search through the trie structure and return a list of all word stored with the given prefix.

• trie_delete(trie, word_to_delete) function takes in a trie and a word_to_delete to remove the letters of the word if they are contained in the trie already. The function returns FALSE when the trie does not contain the word_to_delete.

R Ecosystem

This reasytries package aims to simplify and speed up the process of searching through a dictionary. In addition to time complexity benefits, a tries data structure also allows to search for given words inside the fixed dictionary when given a prefix. Users who are building a search/filter bar from a fixed dictionary will find this package useful! As trie is a famous data structure, there are currently some simple trie packages in R such as trie.