Skip to content

Design Document

Jump to bottom
Dustin Zhang edited this page Jun 5, 2018 · 5 revisions

Program Description

Goal: Add and implement support for prefix tries in Redis

Tries: A trie, also known as a digital tree, radix tree, or prefix tree, is an efficient search tree where keys are strings. The name for the data structure comes from the word reTrieval. Using a trie, search complexities can be brought to O(n) where n is the length of the key. Each node of the Trie has a character, indication whether the node represents the end of a word, and multiple branches. Each branch represents a possible character for the path of the key.

Redis: Redis is an open-source, in-memory remote database that offers versatile modules and support for common data structures like hashes, lists and bitmaps. It serves as a popular platform for project development.

We will be implementing Redis support for the prefix trie first with basic functionality of searching, inserting and deleting and will optimize further based on the needs of the other developing functionalities like autocomplete, spellcheck and text searching.

  • For more information on tries, visit here.
  • For more information on Redis or to try it yourself, visit here.

C Implementation

Trie Class

The trie class is composed of the trie_t struct and its respective operations.

The trie_t struct is composed of:

1. char current // The character the current trie contains

2. trie_t \*children[ALPHABET_SIZE] // ALPHABET_SIZE is 256 for all possible characters.

3. int is_word // If is_word is 1, indicates that this is the end of a word. Otherwise 0.

4. trie_t \*parent // Parent trie_t for traversing backwards.

5. char \*charlist // Array of characters that are contained in the node and its children.

Operations

  1. *trie_t trie_new(char current)

    Purpose: Creates and allocates memory for new trie_t.

    Details: Sets current to be current, all children are initialized to NULL, is_word set to 0.

  2. *trie_t trie_add_node(trie_t *t, char c)

    Purpose: Creates new node in trie_t.

    Details: Set t->children[current] to be current, is_word for new node set to 0.

  3. int trie_insert_string(trie_t *t, char *word)

    Purpose: Inserts word into trie.

    Details: Returns 0 if word is successfully inserted into trie, 1 otherwise. In the trie containing the last character, is_word is set to 1.

  4. int trie_char_exists(trie_t *t, char c)

    Purpose: Checks if a character is contained with a trie.

    Details: Returns 0 if the character is contained, 1 if not.

  5. trie_t* trie_get_subtrie(trie_t *t, char *word)

    Purpose: Searches for a word/prefix in a trie.

    Details: Returns a pointer to the end of the prefix (word) if it exists in the trie.

  6. int trie_search(trie_t *t, char *word)

    Purpose: Search for a word in a trie.

    Details: Returns IN_TRIE (1) if word is found. Returns NOT_IN_TRIE (0) if word is not found at all and PARTIAL_IN_TRIE (-1) if word is found but end node's is_word is 0.

  7. int trie_count_completion(trie_t *t, char *pre)

    Purpose: Count the number of different possible endings of a given prefix in a trie.

    Details: Returns the number of endings of the prefix given, 0 if prefix doesn't exist.

  8. int trie_free(trie_t *t)

    Purpose: Free an entire trie.

    Details: Returns 0 if freed properly.

Redis Module

The commands for the Redis Module will be on a separate page. Check here to see them.

Instructions on how to run Redis, build the Redis Module and use it are on our ReadMe.md file in our directory.

Clone this wiki locally