Autocomplete with static files [3/4] - Building an autocomplete static file generator

In this post we will be implementing an autocomplete static file generator, using the principles, learned in the past two articles in this series. Also within this post is a working demo which produces static autocomplete JSON files for a CSV.

Wed Nov 22 2017

In this post, we will be building an autocomplete static file generator in JavaScript. With the following characteristics:

Input: 1 x CSV
Output: 1 x ZIP archive, containing many files
- One .json file for every search term with results

Transformation details

This application will be transforming the input CSV such that:

One column in the CSV will be designated as the column to be searched on
All partial search terms that lead to results will be saved as separate files. The name of each file will be the partial search term
Within each of those files will contain the entire list of results for that search term

An example transformation is shown below:

CSV

Andrew Smith, Basketball
Adam Smith, Netball

JSON

A.JSON
[{ name: Andrew Smith, Sport: Basketball }, { name: Adam Smith, Sport: Netball }]

AD.JSON
[{ name: Adam Smith, Sport: Netball }]

Building the solution

The data structure that will hold the information

We will be using a Trie to hold the words/result, any node of the tree can have children and therefore is capable of being the head of the Trie aka ‘a Trie itself’. See the code below:

class PrefixTreeNode {
    constructor(value) {
        this.children = {};
        this.endWord = null;
        this.value = value;
        this.additionalInfo = null;
    }
}

Adding methods

We will want to add two methods to the Trie. We could add them to the existing class, however, to keep the code cleaner we will extend the PrefixTreeNode class

class PrefixTree extends PrefixTreeNode {
    constructor() {
        super(null);
    }

    addWord(word, additionalInfo) {
        //adds a new word to the trie
    }

    getAllFullWords() {
        //gets all the words and associated data from the trie
    }
}

Method that adds words to the trie data structure

The first method addWord will insert one word and its associated data into the Trie. The algorithm in Pseudocode is as follows:

Start with the head of the Trie.

:addWordToTrie
Does the next level of the trie contain the first letter of the word?
    If it doesn't, add the first letter of the word (as a new node) into that level.

Is the remaining word only one letter long?
    We have reached the endWord, please mark the node as such, save associated data
    DONE

Is the remaining word more than one letter long?
    :Add remaining portion of the word to the trie :addWordToTrie
    REPEAT/RECURSIVE

And in JavaScript

addWord(word, additionalInfo) {
    const addWordHelper = (node, str) => {
        if (!node.children[str[0]]) {
            node.children[str[0]] = new PrefixTreeNode(str[0]);
        }

        if (str.length === 1) {
            node.children[str[0]].endWord = 1; //set the end word, even if a longer word exists already
            node.children[str[0]].additionalInfo = additionalInfo;
        } else if (str.length > 1) {
            addWordHelper(node.children[str[0]], str.slice(1));
        }
    };
    addWordHelper(this, word);
}

Method that gets all the information out of the Trie

We need a method that gets us all node paths (partial words) from the Trie that ultimately lead to full words. Pseudocode is as follows:

Start with the top of the trie. Once the method has completed, the hashTable allValidLettersCombinations should be full. Each hashKey would be a filename, and the file’s contents would be full words.

Array savedLettersSoFar
Hashtable allValidLettersCombinations 

:currentNode
If there is a letter on currentNode
    Save that letter to the array savedLettersSoFar

If currentNode is an 'endWord'
    Get all previous letters and their sequential combinations/permutations
    For every combination, save that whole word into the hash allValidLettersCombinations

If the currentNode has children nodes
For every childnode
Create a new copy of Array savedLettersSoFar and REPEAT the above

And now in JavaScript

getAllFullWords() {
    const getAllSeqentialPermutations = (strArray) => {
        var permutations = [];
        var partialStringSoFar = '';
        strArray.forEach(s => {
            partialStringSoFar += s;
            permutations.push(partialStringSoFar.slice());
        });
        return permutations;
    }

    var nodePaths = {};
    const traverse = (n, nodesOnThisPath) => {
        if (n.value) {
            nodesOnThisPath.push(n.value);

            if (n.endWord) {
                var permutations = getAllSeqentialPermutations(nodesOnThisPath);
                permutations.forEach(p => {
                    if (nodePaths[p]) {
                        nodePaths[p].push({
                            results: nodesOnThisPath.join(''),
                            additionalInfo: n.additionalInfo
                        });
                    }
                    else {
                        nodePaths[p] = [{
                            results: nodesOnThisPath.join(''),
                            additionalInfo: n.additionalInfo
                        }];
                    }
                });
            }
        }

        if (n.children) {
            for (let k in n.children) {
                traverse(n.children[k], nodesOnThisPath.slice());
            }
        }
    };

    traverse(this, []);
    return nodePaths;
}

Source code for the Trie class

Source code for saving the Trie data to files

All source code

Edit on GitHub

Demonstration

Usage:

Upload any CSV with headers, one of the headers must be named “name” using the tool below
Download the ZIP file of results
Upload contents of ZIP file to a folder on your own web server

Transformation details

Building the solution

The data structure that will hold the information

Adding methods

Method that adds words to the trie data structure

Method that gets all the information out of the Trie

Source code for the Trie class

Source code for saving the Trie data to files

All source code

Demonstration

Find the number of non-contiguous islands in a 2d matrix world

Using recursion and depth-first search to find all islands in a given 2d matrix world

Find the median in a data stream

Adding incoming data in a way that it's optimized to always knowing the median

First missing positive

Find the first missing positive integer in an array in O(array_length) time from LeetCode

Median of two arrays

Getting the median of two sorted arrays in O(log(small_array_length)).

Merge k sorted linked lists

Disseminating the "merge k sorted linked lists" problem from Leetcode.com.

Setup Isso comments on your website today

This guide goes through everything you need to get the open source commenting software Isso running on your website for completely free with Google Cloud.

ZigZag conversion algorithm

A dive into the ZigZag letter conversion on Leetcode.com. Letters initially are written in a zig-zag formation and must be read back from left to right.

Cherry pickup algorithm

An in-depth look at the Cherry Pickup problem on Leetcode.com.

Autocomplete with static files [4/4] - Implementing autocomplete with generated static files

At this stage, we should have already have generated our 'data source' of autocomplete JSON files. We can now finally implement a working text box with autocomplete functionality, which consumes these files.

Autocomplete with static files [3/4] - Building an autocomplete static file generator

In this post we will be implementing an autocomplete static file generator, using the principles, learned in the past two articles in this series. Also within this post is a working demo which produces static autocomplete JSON files for a CSV.

Autocomplete with static files [2/4] - Visualization of words in a Trie

An interactive visualization of how to implement autocomplete without a backend server, using only static files. This post will help with understanding the underpinnings of autocomplete using a Trie data structure.

Autocomplete with static files [1/4] - Introduction

An introduction to static files and the benefits of generating static files for your autocomplete implementation.

Representing numbers, using sticks and stones.

NHibernate QueryOver examples using the C# library

QueryOver is a powerful wrapper for the NHibernate ORM Criteria API. It is type-safe with a familiar syntax to Lambda expressions and LINQ. This post covers a nice range of real-world usage examples.

Creating an Android app, with a large offline database (over 4GB)

Today we will be covering large SQLite databases with the Android PhoneGap framework. We will be going over the challenges and opportunities of running offline Android apps with scale.

Linking in-text citations to numbered references on a page

In this post, we will be adding a usability feature by adding hover functionality to citations. When hovering over a citation, we will show the corresponding reference text. In this example, we are dealing with unstructured HTML and using a set of business rules to link the citations to references.