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.

Implementation (Baseline)

Trie Class

trie_t Struct

  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

Operations

  1. *trie_t new_trie(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 add_node(char current, trie_t *t)

    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 insert_string(char *word, trie_t *t)

    Purpose: Inserts word into trie.

    Details: For each trie, check if entry of the next character exists in the children array:

              If so, move into that node in the array

          If not, add a new node

          Then move on to the next character in string

          Set the is_word of the last node to 1

  4. int delete_string(char *word, trie_t *t)

    Purpose: Delete word in trie.

    Details: Returns 1 if deleted. Conditions:

              If word is not in trie, trie is not modified. 
            
          If word is completely unique (no other part of the word is part of another word) then delete the entire word.

          If word is the prefix of another word in the trie, unmark the leaf node.

          If word is present in the trie, having at least one other word as a prefix, delete all the nodes up to the prefix.

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

    Purpose: Search for a word in a trie.

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

  6. int trie_free(trie_t *t)

    Purpose: Free an entire trie.

    Details: Returns 0 if freed properly.

Optimizations (Awaiting)

Clone this wiki locally