Its being very long time I have been using the auto complete feature available in jqueryUI and AJAX toolkit in ASP.NET. I have been using the very native approach to get the possible words by making the call to the database and using the regular expression. The possible query to the database would look like this
SELECT Id , Name FROM tblName WHERE Name LIKE @prefix + ‘%’;
The problem with this kind of approach is that we make many calls to the database which will be very costly.
In recent time I am learning different data structure and their practical application. In my recent encounter to TRIE data structure (read more) I have the chance to use it my of the project to use it as real time for the auto complete feature. There are many articles on the TRIE and its concept, I have tired to put all the information and my own use to make it work for the auto complete. I am using the ASP.NET MVC Controller to serve the list of the auto complete words , for the UI I am using the jQuery UI autocomplete plugin. I am using the basic concept of ASP.NET like caching etc. to make it more real time. I am not worried about the database as such but I will have method to get the data from the database which can be used for any kind of storage system.
TRIE kind of data structure is good for words because we fixed number of characters and they are less in number. For example take two words like TREAT and TRAITER. As you can see TR is common prefix for both the word,so rather than storing twice we can have a common storing container . So if we see tree by it will be T->R and then two different branch at this level for E and A.
Now it is time for some code. I am going to start with the TRIENode class which will represent the node of the TRIE tree. TRIENode will have following property
1) Children : List of all the possible letter as key and address for the next node.
2) IsCompleteWord : It will mark the completeness of the word and we will use to know if we can use till this node path as the complete word.
3) PrefixCount : It will hold the number of words can be formed, if we will use the word till this node as prefix.
4) Ids : It will contain the multiple Ids of the name , in case we have duplicate names , we need to store the multiple Ids.
5) ActualChar : It will contain the original case of the letter of the word.In case of Children key we will store the lower version of the letter as the key.
TRIENode class
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
namespace TRIEAutoComplete.Models
{
public class TRIENode
{
private SortedDictionary<string, TRIENode> _children;
private bool _isCompleteWord;
private int _prefixCount;
private List<string> _ids;
private string _actualChar;
public string ActualChar
{
get
{
return _actualChar;
}
set
{
_actualChar = value;
}
}
public List<string> Ids
{
get
{
return _ids;
}
set
{
_ids = value;
}
}
public int PrefixCount
{
get
{
return _prefixCount;
}
set
{
_prefixCount = value;
}
}
public SortedDictionary<string,TRIENode> Children
{
get
{
return _children;
}
set
{
_children = value;
}
}
public bool IsCompleteWord
{
get
{
return _isCompleteWord;
}
set
{
_isCompleteWord = value;
}
}
public TRIENode()
{
_children = new SortedDictionary<string, TRIENode>();
_isCompleteWord = false;
_prefixCount = 0;
_actualChar = string.Empty;
_ids = new List<string>();
}
}
}
TRIE.cs : It will be contain all the required methods. I have added an extra method RemoveWord , it will remove the associated Ids of the existing word and if there is no Ids left it will make the IsCompleteWord flag false.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
namespace TRIEAutoComplete.Models
{
public class TRIE
{
public TRIENode CreateNode()
{
return new TRIENode();
}
public void AddWord(string word , TRIENode rootNode , string id)
{
int len = word.Length;
if (len == 0)
{
rootNode.PrefixCount++;
rootNode.IsCompleteWord = true;
rootNode.Ids.Add(id);
return;
}
for (int i = 0; i < len; i++)
{
string key = word.Substring(i, 1);
string lowerVersionKey = key.ToLower();
if(!rootNode.Children.ContainsKey(lowerVersionKey))
{
rootNode.Children.Add(lowerVersionKey, new TRIENode());
rootNode.Children[lowerVersionKey].ActualChar = key;
}
rootNode.PrefixCount++;
rootNode = rootNode.Children[lowerVersionKey];
}
rootNode.IsCompleteWord = true;
rootNode.Ids.Add(id);
}
public void RemoveWord(string word, TRIENode rootNode, string id)
{
int len = word.Length;
if (len == 0)
{
rootNode.PrefixCount--;
if (rootNode.PrefixCount == 0)
rootNode.IsCompleteWord = false;
rootNode.Ids.Remove(id);
return;
}
for (int i = 0; i < len; i++)
{
string key = word.Substring(i, 1);
string lowerVersionKey = key.ToLower();
rootNode.PrefixCount--;
rootNode = rootNode.Children[lowerVersionKey];
}
rootNode.Ids.Remove(id);
if (rootNode.Ids.Count == 0)
rootNode.IsCompleteWord = false;
}
public TRIENode GetMatchedNode(string prefix, TRIENode rootNode)
{
int len = prefix.Length;
if (len > 0)
{
for (int i = 0; i < len; i++)
{
string key = prefix.Substring(i, 1);
string lowerVersionKey = key.ToLower();
if (!rootNode.Children.ContainsKey(lowerVersionKey))
return null;
rootNode = rootNode.Children[lowerVersionKey];
}
return rootNode;
}
return null;
}
public void GetAutoCompleteList(TRIENode matchedNode, string completeWord, List<AutoCompleteResult> wordList)
{
foreach (var item in matchedNode.Children)
{
string tmpWord = completeWord + item.Value.ActualChar;
if(item.Value.IsCompleteWord)
{
AutoCompleteResult r = new AutoCompleteResult();
r.id = string.Join(",", item.Value.Ids);
r.label = tmpWord;
r.value = tmpWord;
wordList.Add(r);
}
GetAutoCompleteList(item.Value, tmpWord , wordList);
}
}
}
}
AutoCompleteResult.cs : It will contain the result for the JSON structure for auto complete of the jqueryUI.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
namespace TRIEAutoComplete.Models
{
public class AutoCompleteResult
{
public string id;
public string label;
public string value;
}
}
AutoCompleteController.cs : MVC Controller containing all the possible actions . To make it more real time , I am caching the root node when I have loaded all the names from my database. Fetching the names again from the database is very costly affair. I have added couple of action method to use the Delete and Add of the names and cache it again. We can delete or add the names from the database in normal way and once we succeed we can delete or add from the word from the cache itself .
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Caching;
using System.Web.Mvc;
using TRIEAutoComplete.Models;
namespace TRIEAutoComplete.Controllers
{
public class AutoCompleteController : Controller
{
TRIE trieDS = new TRIE();
TRIENode rootNode = new TRIENode();
//
// GET: /AutoComplete/
public ActionResult Index()
{
rootNode = trieDS.CreateNode();
trieDS.AddWord("Name One", rootNode, "1");
trieDS.AddWord("Name Two", rootNode, "2");
trieDS.AddWord("Name One", rootNode, "4");
HttpContext.Cache["rootNode"] = rootNode;
return View();
}
public JsonResult AutoCompleteList(string term)
{
List<AutoCompleteResult> result = new List<AutoCompleteResult>();
if (HttpContext.Cache["rootNode"] != null)
rootNode = (TRIENode)HttpContext.Cache["rootNode"];
TRIENode matchedNode = trieDS.GetMatchedNode(term, rootNode);
trieDS.GetAutoCompleteList(matchedNode, term, result);
return Json(result, JsonRequestBehavior.AllowGet);
}
public void AddWord(string word, string id)
{
if (HttpContext.Cache["rootNode"] != null)
rootNode = (TRIENode)HttpContext.Cache["rootNode"];
trieDS.AddWord(word, rootNode, id);
rootNode = (TRIENode)HttpContext.Cache["rootNode"];
}
public void RemoveWord(string word , string id)
{
if (HttpContext.Cache["rootNode"] != null)
rootNode = (TRIENode)HttpContext.Cache["rootNode"];
trieDS.RemoveWord(word, rootNode, id);
HttpContext.Cache["rootNode"] = rootNode;
}
}
}
<%@ Page Language="C#" Inherits="System.Web.Mvc.ViewPage<dynamic>" %>
<!DOCTYPE html>
<html>
<head runat="server">
<meta name="viewport" content="width=device-width" />
<title>AutoComplete : Example</title>
<script src="../../Scripts/jquery-1.8.2.min.js"></script>
<script src="../../Scripts/jquery-ui-1.8.24.min.js"></script>
<script type="text/javascript">
$(document).ready(function () {
$("#txtName").autocomplete({
source: '/AutoComplete/AutoCompleteList',
minlength: 2,
select: function (event, ui) {
}
});
});
</script>
</head>
<body>
<div>
<input type="text" name="txtName" id="txtName" />
<input type="hidden" name="hydId" id="hydId" />
</div>
</body>
</html>
I am using the select method in the jquery UI autocomplete to get the Id or Ids of the selected option and I will send the same to get the list of the possible names and extra detail from the database. In the database you can easily index the Id and get the list much faster. Currently I have applied the same in my one of the project. Please do share or correct me in case I have missed something .
Devesh's Blog 