Autocomplete using a trie

In this post I am going to show you how to implement autocomplete using jquery and Trie data structure.
Before going into code implementations lets understand what is trie.






A trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.
In the example shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it. A trie can be seen as a tree-shaped deterministic finite automaton. Each finite language is generated by a trie automaton, and each trie can be compressed into a deterministic acyclic finite state automaton.(source wikipedia)

Open visual studio and create empty website project and add following code into App_Code

AutoComplete.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

/// <summary>
/// Summary description for Trie
/// </summary>
public class Autocomplete
{

    // Trie node class
    public class Node
    {
        public string Prefix { get; set; }
        public Dictionary<char, Node> Children { get; set; }

        // Does this node represent the last character in a word?
        public bool IsWord;

        public Node(String prefix)
        {
            this.Prefix = prefix;
            this.Children = new Dictionary<char, Node>();
        }
    }

    // The trie
    private Node trie;

    // Construct the trie from the dictionary
    public Autocomplete(String[] dict)
    {
        trie = new Node("");
        foreach (String s in dict)
            InsertWord(s);
    }

    // Insert a word into the trie
    private void InsertWord(String s)
    {
        // Iterate through each character in the string. If the character is not
        // already in the trie then add it
        Node curr = trie;
        for (int i = 0; i < s.Length; i++)
        {
            if (!curr.Children.ContainsKey(s[i]))
            {

                curr.Children.Add(s[i], new Node(s.Substring(0, i + 1)));
            }
            curr = curr.Children[s[i]];
            if (i == s.Length - 1)
                curr.IsWord = true;
        }
    }

    // Find all words in trie that start with prefix
    public List<String> GetWordsForPrefix(String pre)
    {
        List<String> results = new List<String>();

        // Iterate to the end of the prefix
        Node curr = trie;
        foreach (char c in pre.ToCharArray())
        {
            if (curr.Children.ContainsKey(c))
            {
                curr = curr.Children[c];
            }
            else
            {
                return results;
            }
        }

        // At the end of the prefix, find all child words
        FindAllChildWords(curr, results);
        return results;
    }

    // Recursively find every child word
    private void FindAllChildWords(Node n, List<String> results)
    {
        if (n.IsWord)
            results.Add(n.Prefix);
        foreach (var c in n.Children.Keys)
        {
            FindAllChildWords(n.Children[c], results);
        }
    }
}
Default.aspx
<%@ Page Language="C#" AutoEventWireup="true" CodeFile="Default.aspx.cs" Inherits="_Default" %>

<!DOCTYPE html>

<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title></title>
    <script src="Scripts/jquery-1.12.4.js"></script>
    <script src="Scripts/jquery-ui-1.12.1.js"></script>
    <link href="Content/themes/base/jquery-ui.css" rel="stylesheet" />
    <script type="text/javascript">
            $(document).ready(function() {
                SearchText();
            });
            function SearchText() {
                $(".autosuggest").autocomplete({
                    source: function(request, response) {
                        $.ajax({
                            type: "POST",
                            contentType: "application/json; charset=utf-8",
                            url: "WebService.asmx/GetData",
                            data: "{'username':'" + document.getElementById('txtSearch').value + "'}",
                            dataType: "json",
                            success: function (data) {
                                if (data != null) {

                                    response(data.d);
                                }
                            },
                            error: function(result) {
                                alert("Error");
                            }
                        });
                    }
                });
            }
        </script>
</head>
<body>
    <form id="form1" runat="server">
          <div class="demo">
           <div class="ui-widget">
            <label for="tbAuto">Enter UserName: </label>
       <input type="text" id="txtSearch" class="autosuggest" />
    </div>
        </form>
</body>
</html>
Web.Config
<?xml version="1.0"?>

<!--
  For more information on how to configure your ASP.NET application, please visit
  http://go.microsoft.com/fwlink/?LinkId=169433
  -->

<configuration>

    <system.web>
      <compilation debug="true" targetFramework="4.5.2" />
      <httpRuntime targetFramework="4.5.2" />
      <webServices>
        <protocols>
          <add name="HttpPost"/>
        </protocols>
      </webServices>
    </system.web>

</configuration>
WebService.asmx
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Services;

/// <summary>
/// Summary description for WebService
/// </summary>
[WebService(Namespace = "http://tempuri.org/")]
[WebServiceBinding(ConformsTo = WsiProfiles.BasicProfile1_1)]
// To allow this Web Service to be called from script, using ASP.NET AJAX, uncomment the following line. 
[System.Web.Script.Services.ScriptService]
public class WebService : System.Web.Services.WebService
{

    public WebService()
    {

        //Uncomment the following line if using designed components 
        //InitializeComponent(); 
    }

    [WebMethod]
    public List<string> GetData(string username)
    {
        Autocomplete a = new Autocomplete(new String[] { "india", "ireland", "usa", "poland", "uk", "germany", "guana", "uae" });

        return a.GetWordsForPrefix(username);
    }

}

4 comments:

  1. I just see the post i am so happy to the communication science post of information's.So I have really enjoyed and reading your blogs for these posts.Any way I’ll be replay for your great thinks and I hope you post again soon.

    Software Testing Training Institute in Chennai

    ReplyDelete
  2. Learn Dot Net Training in Chennai at Credo Systemz. Training offered by MNC Experts. Rated as Best .Net Training Institute in Chennai. Learn C# & ASP.Net Course with 100% Placement.

    .NET Framework developed by Microsoft is an integral part for most of the primary applications running on Windows. .NET with its consistent and comprehensive programming model, created a technological revolution in recent years. Applications built using .NET has the capability to entice the user with visually stunning experiences along with faultless and secured communication system.

    ReplyDelete
  3. The .NET framework helps you create mobile, desktop, and web applications that run on Windows PCs, devices and servers and it's included in Visual Studio.

    Develop web sites and services that run on Linux, Windows and macOS with the blazing fast and modular platform provided by .NET Core and ASP.NET Core.

    Xamarin brings the power and productivity of .NET to iOS and Android, reusing skills and code while getting access to the native APIs and performance.

    Xamarin brings the power and productivity of .NET to iOS and Android, reusing skills and code while getting access to the native APIs and performance.

    Dot Net Training in Chennai

    Best Dot Net Training in Chennai

    ReplyDelete