-
Notifications
You must be signed in to change notification settings - Fork 1
/
README.Rmd
96 lines (69 loc) · 3.48 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
---
output: github_document
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
```{r, include = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>",
fig.path = "man/figures/README-",
out.width = "100%"
)
```
# reasytries
<!-- badges: start -->
[](https://github.com/UBC-MDS/reasytries/actions)
[](https://github.com/UBC-MDS/reasytries/actions)
[](https://codecov.io/gh/UBC-MDS/reasytries)
<!-- badges: end -->
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](https://github.com/) with:
``` r
# 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](https://www.r-project.org/)
[rlang 0.4.10](https://cran.r-project.org/web/packages/rlang/index.html)
## Documentation
The official documentation can be found [here](https://ubc-mds.github.io/reasytries/)
## 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](https://www.rdocumentation.org/packages/triebeard/versions/0.3.0/topics/trie).