Runtime Trie data structure generation vs storing & reading to a file approach

Question

I am creating a Trie structure for every single word in the English dictionary. I wanna use this structure for games such as word search & scrabble type games but I don't know if its faster to generate the structure at runtime or if I should be figuring out a way to flatten this Trie structure into JSON or XML to be read into memory at runtime.

I don't know much about creating databases or storing data for later usage so any recommendations would be awesome - right now im looking at Jackson and Java. The ultimate goal is to port this application to JavaScript on my website.

Answer 1

This is how you can generate Trie structure and use it on your website without using Java, just with JavaScript. Simple Trie structure with two methods: insert and search could look like this in JS:

function Trie() {
    this.root = new TrieNode();
    this.insert = function(key) { 
        let length = key.length, next = this.root; 

        for (let level = 0; level < length; level++) { 
            let character = key.charAt(level); 
            if (next.children[character] == null) {
                next.children[character] = new TrieNode(); 
            }

            next = next.children[character]; 
        }
        next.endOfWord = true; 
    }
    this.search = function(key) { 
        let length = key.length, next = this.root; 

        for (let level = 0; level < length; level++) { 
            let character = key.charAt(level);

            if (next && next.children[character]) {
                next = next.children[character];
                continue;
            }
            return false;
        }

        return next && next.endOfWord;
    } 
}

function TrieNode() {
    this.children = {};
    this.endOfWord = false; 
}

Using above simple implementation you can create Trie instance and insert all words you want:

const trie = new Trie();
trie.insert("hello");
trie.insert("hi");
trie.insert("help");
trie.insert("helpful");
... more words

For example, using Node.js you can:

• Read all required words from source file.
• For each word insert it into trie structure using insert method.
• generate JSON from object by: JSON.stringify(trie).
• Save it to a file: trie.js which can be used later on you page.

Result js file for above words should look like:

{
   "root":{
      "children":{
         "h":{
            "children":{
               "e":{
                  "children":{
                     "l":{
                        "children":{
                           "l":{
                              "children":{
                                 "o":{
                                    "children":{
                                       
                                    },
                                    "endOfWord":true
                                 }
                              },
                              "endOfWord":false
                           },
                           "p":{
                              "children":{
                                 "f":{
                                    "children":{
                                       "u":{
                                          "children":{
                                             "l":{
                                                "children":{
                                                   
                                                },
                                                "endOfWord":true
                                             }
                                          },
                                          "endOfWord":false
                                       }
                                    },
                                    "endOfWord":false
                                 }
                              },
                              "endOfWord":true
                           }
                        },
                        "endOfWord":false
                     }
                  },
                  "endOfWord":false
               },
               "i":{
                  "children":{
                     
                  },
                  "endOfWord":true
               }
            },
            "endOfWord":false
         }
      },
      "endOfWord":false
   }
}

To make a valid JS file with a code you need to add: const RAW_TRIE = string at the beginning, so our file looks like:

const RAW_TRIE = {
   "root":{
      "children":{
         "h":{
          ...

You created a raw Trie object which you can include to your page by adding this line to your HTML or template files:

<script src="www.your-domain.com/path/to/static/file/trie.js"></script>

Since this file is loaded you should have an access to RAW_TRIE object. You can set prototype to Trie and use search method:

const TRIE = Object.setPrototypeOf(RAW_TRIE, new Trie());
console.log("hello exists: " + TRIE.search("hello"));
console.log("hello1 does not exist: " + TRIE.search("hello1"));

This approach allows you to create on server side file with all words you need and client can download it and use as a regular static file.

Note: above solution is an only one way how to do that and some (or all) steps can be improved or changed. It is not a final version which can be used without any changes on production. You can try to optimise it and make trie.js file as small as possible by changing TrieNode function or even removing it.