Predictive Search REST API for African words | Trie Data structure

Flask API serving Predictive search (auto-complete) results for African words.

Trie Hero Image
Trie data structure containing four (4) Yoruba names.

Why do we need an Autocomplete feature?

According to Fresh Consulting, search “Autocomplete Suggestions” (also known as “predictive search”) have become increasingly popular on e-commerce sites over the past five years. Our 2019 benchmark reveals that search autocomplete is now offered at 96% of major e-commerce sites, up from 72% in 2014, where we first started benchmarking e-commerce search implementations from the 60 largest online retailers.

Predictive search has a number of benefits to this user. These include:

What is a Trie datastructure?

According to wiki also called digital tree or prefix tree, is a type of search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters.

Trie Quick-reference
Trie quick reference from Interview lake

Predictive search for African words. What is the use case?

The number of technology consumers in Africa is rapidly growing as internet become increasingly accessible in the continent. This value was give as 530 million in 2021 — Internet world stats. Technology providers and developers need to pay more attention to the user experience of these rapidly ballooning population. According to CommerceShop, Predictive search has shown a 20% increase in customer engagement and 11% increase in customer interactivity when implemented on eCommerce sites. An application which is shipped of the shelf with the capability to predict a good number of user input in his/her local language will have a significant advantage over one without this feature.

API Implementation.

This API was implemented using the Flask framework. See below a snapshot of the folder structure:

Project folder structure
Project folder structure

The folder structure above is a common structure used for Flask application. This was generated using a Flask project generator package called Flask Noodle. Only two new files (triesDS.py and triesData.py) are added to the project skeleton provided by Flask Noodle. See below the contents of the new files:

triesDS.py contents
triesDS.py | Containing the Tries class skeleton and documentation that guide it’s implementation.
triesData.py contents
triesData.py | Containing language data, this is the content available for the predictive search.

Note that the views.py file is also updated to include the API endpoint that takes in the search parameter as a URL argument (see Flask Doc). See implementation below:

API Endpoint implementation in Flask

Application Demonstration

A simple client demo is shown below. This fast speed of the predictive search API is a testament to the efficient implementation of the Trie datastructure.

The whole working repository is available on GitHub. Kindly acknowledge use.