In this article, we will implement a very popular feature of the search engines did you mean using Nodejs.How often we misspell while searching something on the internet, well there can be many reasons for this raging from the Unknown spelling of Goods (while shopping), Keyboard problem, Misspelled words or Unaccustomed international celebrity names.Different search engine reacts differently to this problem.
Let’s talk about very popular search engine Google, When you type something wrong in Google search bar it will show you the correct word with the message,Did you mean‘##Something##’. Same with Amazon whenever you type the wrong spelling of the product then it will correct you by showing possible suggestions.
Here I will demonstrate this features on the small collection of words usingLevenshtein distance. But in real life, you may have a situation where you have a Huge dataset to work on.In that case, you can do some workaround and divide data into small chunks and then you can apply this idea.Here we will find out the Levenshtein distance between the word which user is searching for with respect to each word in the collection.
1. What is Levenshtein Distance?
In very simple terms,
Levenshtein Distance is a similarity between two strings
This is distance is as basically amatricfor measuring the amount of difference between two words. Now, this distance is calculated on the basis of Insertion, deletion, and substitution required to match the source string to target string. Levenshtein Distance is also known and Edit distance.
Example:
Let’s understand this with the help of a small example, Here we have two strings.
First String isshashank, wheres1 = shashank.
Second String isshashanq, wheres2= shashanq.
So the Levenshtein Distance between s1 and s2 would1.
i.e. LD(s1, s2) = 1.
Explanation:
Here we are comparing the shashank(s1) with shashanq(s2). To transform shashank to shashanq, we need only one substitution.
2. Creating a new Nodejs project
1. Let’s start off by creating a new Nodejs project by using ng init
command.This command will create a new package.json file.
2.I found a very useful node module to calculate the Levenshtein Distance, run the below command to install the package for Levenshtein Distance.
npm install levenshtein-distance
Below is my package.json file for this application.
package.json:
{ "name": "levenshtein-distance-project", "version": "1.0.0", "description": "", "main": "server.js", "scripts": { "test": "echo \"Error: no test specified\" && exit 1" }, "author": "", "license": "ISC", "dependencies": { "body-parser": "*", "express": "*", "levenshtein-distance": "0.0.2" } }
3. Collection of Words Example
For this application, I have created a small collection of words in the form of array shown below, Which we will include in our application.
data.js:
module.exports = [ 'possibilities', 'hit', 'lead', 'left', 'apple', 'pineapple', 'banana', 'orange', 'radish', 'carrot', 'pea', 'bean', 'potato', 'shashank', 'sasank', 'asyncronous', 'marmoset', 'Seth MacFarlane', 'Arnold Schwarzenegger', 'Scarlett Johansson', 'Rodrigo Santoro', 'java', 'lava', 'bullet' ];
4. Creating a NodeJs Server
Now we’ll start with a new project and see how to get the desired search output. But before that let’s take look at our project directory structure shown below.
1.Create a server.js in the root of the project, which will be our entry point for the project.Here we will define our route and we will start the server.
=>TheappConfig()
method will set the application configuration.
=>InincludeRoutes()
method we will execute the application route.
=>TheappExecute()
method will call theappConfig()
as well asappExecute()
and it will run the nodejs server.
server.js:
/* * @author Shashank Tiwari * did you mean using Nodejs */'use strict'; const express = require("express"); const http = require('http'); const bodyParser = require('body-parser'); const levenshteinDistance = require("levenshtein-distance"); const wordCollection = require('./data'); class Server { constructor() { this.port = process.env.PORT || 4000; this.host = `localhost`; this.app = express(); this.http = http.Server(this.app); } appConfig() { this.app.use( bodyParser.json() ); this.app.use(require("express").static('client')); } /* Including app Routes starts*/ includeRoutes(app) { app.get("/", function (req, res) { res.sendFile(__dirname + '/client/index.html'); }); app.post("/getSuggestion", function (request, response) { /* ------- ------- ------- Here we will calculate the distance between the string All the words will be pushed inside the array let's stay 'responseCollection' and we will return the responseCollection to the client ------- ------- ------- */ }); } /* Including app Routes ends*/ appExecute() { this.appConfig(); this.includeRoutes(this.app); this.http.listen(this.port, this.host, () => { console.log(`Listening on http://${this.host}:${this.port}`); }); } } const app = new Server(); app.appExecute();
5. did you mean using Nodejs and levenshtein-distance
Now the only remaining part left on the server side is implementing this feature. Below is the code that you need write inside the/getSuggestion
post request.
=>Inside the/getSuggestion
post request we will calculate and write the rest of the code.
server.js:
/* * @author Shashank Tiwari * did you mean using Nodejs */app.post("/getSuggestion", function (request, response) { // Variable for server response let responseCollection = []; //Storing the user entered string into variable let getSuggestionString = request.body.suggestion; /* * Creating an object of the levenshtein-distance node module by passing the collection of words */let collection = new levenshteinDistance(wordCollection); /* * Calling the find() method on the object of the levenshtein-distance node module * Storing the response inside the responseCollection variable */ collection.find(getSuggestionString, function (result) { responseCollection.push(result); }); response.status(200).json(responseCollection); });
6. Implementing FrontEnd using AngularJs
1.Let’s create index.html inside the/client
folder and write down the below markup.
index.html:
<!-- @author Shashank Tiwari did you mean using Nodejs --> <html ng-app="app" ng-controller="app"> <head> <title>Did you mean feature using Nodejs</title> <link rel="stylesheet" href="css/bootstrap.min.css"> <link rel="stylesheet" href="css/style.css"> </head> <body> <div class="container"> <div class="app-heading"> <h2> Did you mean feature in Nodejs </h2> </div> <div class="app-idea"> <h4> Type something in below textbox for example: <span>aple,carot</span> </h4> </div> </div> <div class="container"> <div class="app"> <input type="text" class="form-control " ng-model="suggestion" placeholder="sasan"> <div ng-show="suggestionCollection.length > 0" class="container"> <h3> Did you mean ?</h3> <div class="suggestion-collection"> <span ng-repeat="suggestion in suggestionCollection"> {{suggestion}} </span> </div> </div> </div> </div> </body> <script src="js/angular.min.js"></script> <script src="js/script.js"></script> </html>
2.Now create a script.js inside the/js
folder under the/client
folder and write down the below code.
=>In the below code we have Angularjs service to call the nodejs endpoint/getSuggestion
and in that HTTP request we will send the user entered text.
And rest is self-explanatory.
script.js:
/* * @author Shashank Tiwari * did you mean using Nodejs */const app = angular.module('app',[]); app.service('appService', ['$http', function($http){ return { 'getSuggestion' : function(suggestion,callback){ $http.post('/getSuggestion', { 'suggestion': suggestion }).success(function (response) { callback(response); }) .error(function (data, status, header, config) { callback({ 'error': true, 'message': "Something went wrong." }); }); } } }]); app.controller('app', function ($scope,appService) { $scope.suggestion = null; $scope.suggestionCollection = []; $scope.$watch('suggestion', function (newValue, oldValue) { if (newValue !== null) { if (newValue.length > 3) { appService.getSuggestion(newValue, function (response) { $scope.suggestionCollection = response; }); }else{ $scope.suggestionCollection = []; } }else{ $scope.suggestionCollection = []; } }); });
7. Conclusion
I won’t say this is the exact and the only method to implement this feature, but this can be helpful when you are working with a small collection of words. I hope this explains the little bit about the Levenshtein distance and how to use it to implement such feature.If you have any suggestion or anything that you want to ask, do let me know in below comment box.