AutoComplete with Redis, NodeJS and jQuery

Introduction

This article will show how to implement an auto completion feature using Redis and NodeJS, with a simple front end in HTML and jQuery to demonstrate the end result. Familiarity with Redis and NodeJS is assumed. If you have never heard of them, you are encouraged to look them up and read some introductions to get a feel of what they can do.

The complete source is located at my github page: https://github.com/wliao008/oc_autocomplete_redis

The end result would look like this:

Background

I setup OpenClinica for a client. OpenClinica is an open source clinical trial software for capturing electronic data. The data forms are being created in what is call Case Report Forms (CRF). In essence, you can create a CRF in Excel, upload it into OpenClinica and you will have a dynamic form to capture the data you want.

It is not uncommon to customize some of the functionality while building these CRFs, like interacting with input fields, or do customized validation, etc. OpenClinica allows this customization to happen via embedding JavaScript right inside of CRFs.

On this particular occasion the client have a really long list of codes called International Classication of Diseases, Ninth Revision, ICD9 for short. And they needed to be able to show this list on the form, so whoever entering data can select a specific code to be saved.

My first attempt was to do exactly that, I loaded all 1.8 MB of the list onto the drop down list via JavaScript, I quickly found that it is a bad idea as it basically hung the page and I had to kill the unresponsive browser.

My second option was to load all the code in a popup page, and provide some sort of pagination to page through the list, however user might have to page throught lot of pages just to find the right code, so it is not very user friendly, so that got voted down quick.

My third option was to implement an auto completion feature, where the user would type into the textbox and whatever ICD9 codes matched will show up. With some restriction on the length of the query, this would greatly reduce the size of the data being displayed. This sounds like a reasonable solution.

Usage Scenarios

Let's look at a really simple example (extracted from the actual list), and what the desired result should be, suppose I have the following list and I want to perform auto completion on them:

2.1 - Paratyphoid fever A
2.2 - Paratyphoid fever B
2.3 - Paratyphoid fever C
2.9 - Unspecified paratyphoid fever
3 - Salmonella gastroenteritis
3.1 - Salmonella septicemia

When user starts typing "para" in the query box, the following list should be immediately returned:

2.1 - Paratyphoid fever A
2.2 - Paratyphoid fever B
2.3 - Paratyphoid fever C
2.9 - Unspecified paratyphoid fever

When user starts typing "fever" in the query box, the same list should be immediately returned:

2.1 - Paratyphoid fever A
2.2 - Paratyphoid fever B
2.3 - Paratyphoid fever C
2.9 - Unspecified paratyphoid fever

When user starts typing "fever c", only the following should be returned:

2.3 - Paratyphoid fever C

But what if user start typing "ever"? Should it returns all the codes that partially match it? That's a choice of the actual implementation that we will have to make depending on the need of the user, as we will see shortly.

Data Processing

Redis introduced ZRANGEBYLEX in version 2.8.9, we will take advantage of that feature to process our data and do the actual lexical search. But before we can do the search, we will process the data and store them in a sorted set.

Since the user could query by typing any word within any entry, we need to have an item that begins at each segment of the entry in the sorted set, and all those items will point back to the original entry. That's a mouthful.

For example, to process this entry "2.1 - Paratyphoid fever A", first it's converted into lower case, then it will be broken down into:

2.1 - paratyphoid fever a
paratyphoid fever a
fever a
a

All those items should point back to the original entry, so no matter what the user queries, it should return the correct entry. You could use any approach or data structures with Redis to provide that callback reference, but for me I decided to just tag the original entry onto each item, like so:

2.1 - paratyphoid fever a$2.1 - Paratyphoid fever A
paratyphoid fever a$2.1 - Paratyphoid fever A
fever a$2.1 - Paratyphoid fever A
a$2.1 - Paratyphoid fever A

As run time when the user types in a query, I'd just take the returned results and extract whatever comes after the $ sign and present to the user in the drop down.

Another approach to processing the data is by character, take "2.1 - Paratyphoid fever A" as an example, it would be turned into:

2.1 - paratyphoid fever a$...
.1 - paratyphoid fever a$...
- paratyphoid fever a$...
paratyphoid fever a$...
aratyphoid fever a$...
ratyphoid fever a$...
atyphoid fever a$...
typhoid fever a$...
yphoid fever a$...
phoid fever a$...
hoid fever a$...
oid fever a$...
id fever a$...
d fever a$...
fever a$...
ever a$...
ver a$...
er a$...
r a$...
a$...

Where $... indicates the original entry. Going with this approach will mean that user will be able to match partial of any given words. However it will come at a cost of more memory used by Redis, in my test, storing the complete ICD9 code by character uses ~190 MB, where as by word uses ~29 MB. Whichever approach to go with will depend on the need of your user.

The Ruby script to process the data and store them in a sorted set in Redis named "icd9".

#require 'rubygems'
require "redis"

def by_word(line, r)
    array = line.downcase.gsub!(/ - /, ' ').split(' ')
    len = array.length - 1
    (0..len).each {|n|
        val = array[-(len-n)..-1].join(' ') + "$#{line.chop}"
        r.zadd('icd9',0,val)
    }
end

def by_character(line,r)
    array = line.downcase.gsub!(/ - /, ' ').split('')
    len = array.length - 1
    (0..len).each{|n|
        char = array.slice(0,1).join
        if char != ' '
            val = array.join() + "$#{line.chop}"
            r.zadd('icd9',0,val)
        end
        array.shift
    }

end

def do_work()
    r = Redis.new
    f = File.open('list.txt', 'r')
    f.each_line do |line|
        by_word(line, r)
    end
    f.close
end

do_work

After the data is processed and stored, at this point, you can connect to the Redis server and start querying the data, for example:

127.0.0.1:6379> zrangebylex icd9 "[brain" "[brain\xff"
[Result omitted]

This will return anything that has the word "brain" in the entry. To find out how the strange looking zrangebylex query work, please refer to the Redis documentation at: http://redis.io/commands/zrangebylex

Once we're satisfied with the data, we can think about how to serve this to the user, for that, I will use NodeJS as the middle man.

Processing Query with NodeJS

The Node application will take the actual query submitted by the user, and in turn submit a Redis query to the Redis server, then it will gather the result returned, and extract the entries as mentioned above, and return the response back to the user. The complete Node app:

var redis = require("redis"), client = redis.createClient();
var http = require('http');

var parseQueryString = function( queryString ) {
    var params = {}, queries, temp, i, l;
    queries = queryString.split("&");
    for ( i = 0, l = queries.length; i < l; i++ ) {
        temp = queries[i].split('=');
        params[temp[0]] = temp[1];
    }
    return params;
};

http.createServer(function (req, res) {
  var q = parseQueryString(req.url.substring(req.url.indexOf('?') + 1));
  if (typeof(q["q"]) != 'undefined'){
      var query = decodeURIComponent(decodeURI(q["q"])).toLowerCase();
      var callback = q["callback"];
      console.log("query: " + query); 
      client.zrangebylex('icd9', '[' + query, '[' + query + '\xff', 
        function(err, reply){
        if (err !== null){
          console.log("error: " + err);
        } else {
          res.writeHead(200, {'Content-Type': 'text/plain'});
          var replies = [];
          for(var i = 0; i< reply.length; i++)
            replies.push(reply[i].split("$")[1]);
          replies = replies.sort();
          var str = callback + '( ' + JSON.stringify(replies) + ')';
          res.end(str);
        }
      });
  }
}).listen(1337, '127.0.0.1');

Front End

Finally we are ready to code up the front end. For this, I used jQuery's autocomplete plugin. As the user types in the words, it will submit an AJAX call to the NodeJS app using jsonp. Note it contains some JavaScript specific to OpenClinica which you can strip out to fit your need.

<!doctype html>
<html lang="en">
   <head>
      <meta charset="utf-8">
      <title>jQuery UI Autocomplete functionality</title>
          <style>
                ul.ui-autocomplete.ui-menu{width:600px}
                .ui-autocomplete { height: 200px; overflow-y: scroll; overflow-x: hidden;}
            </style>
      <link href="http://code.jquery.com/ui/1.10.4/themes/ui-lightness/jquery-ui.css" rel="stylesheet">
      <script src="http://code.jquery.com/jquery-1.10.2.js"></script>
      <script src="http://code.jquery.com/ui/1.11.2/jquery-ui.js"></script>
      <!-- Javascript -->
      <script>
        $(function(){
            $.ajaxSetup({ scriptCharset: "utf-8" ,contentType: "application/x-www-form-urlencoded; charset=UTF-8" });
            //this is OpenClinica specific
             var myOutputField = $("#myOutput").parent().parent().find("input");
            myOutputField.attr("readonly",true);
             $( "#icd9" ).autocomplete({
                source: function(req, res){
                    console.log('req.term: ' + req.term);
                    $.ajax({url: "http://127.0.0.1:1337/?callback=?",
                            dataType: "jsonp",
                            data:{
                                q: encodeURI(req.term)
                            },
                            success: function(data){
                                res(data);
                            },
                            error: function(xhr, status, err){
                                console.log(status);
                                console.log(err);
                            }
                    });
                },
                minLength: 2,
                select: function(event, ui){
                    if (ui.item){
                        $('#selectedIcd9Label').text(ui.item.label);
                        $('#myOutput').val(ui.item.label.split(' - ')[0]);
                    }
                }
             });
        });
      </script> 
   </head>
   <body>
      Search: <input id="icd9" style="width:600px;height:60px"><br/><br/>
      Label: <span id="selectedIcd9Label"></span>
   </body>
</html>

Conclusion

That is it, load up the index.html in your browser and test it out!

The combination of Redis and NodeJS, made programming an often difficult feature such as auto completion really easy to implement. I'd highly recommend you to start exploring these two technologies and what they can do for you.

History

12/17/2014 - initial ver.