John Hobbs

On a recent project I had the need to implement a basic search functionality into a web interface. This isn’t unusual, but what was different is that the data in this project was fairly static, and was kept in JSON on disk (and cached into memory). Additionally, there would be a point where it was moved off of our servers, onto an entirely different stack (hence the JSON).

There was minimal server side processing so far, and I did not want to add more overhead that would need to be ported. So, I decided to implement my search in JavaScript (with some help from Python). My idea was to do very basic string matching on a pre-built index. In this article I am going to lay out my implementation, but on a dummy data set.

The Process

This search breaks down into three steps:

1. Build Search Index
2. Perform Search
3. Connect To Interface

Before we start writing that, let’s cover the data.

The Data

Here is the data I will be sifting through. To keep it simple, I’m just searching through some sentences with associated ID’s. It’s short and simple, but with some tweaks you can apply this to bigger data sets, as I did.

My data set will be represented in JSON for portability and easy interpretation from JavaScript.

{
  "entries": [
    {
      "id": 1,
      "title": "The lazy white cat slept.",
      "body": "What a lazy cat."
    },
    {
      "id": 2,
      "title": "George, though angry, didn't make a sound.",
      "body": "George is a quiet man."
    },
    {
      "id": 3,
      "title": "Anyone could see that white didn't suit her.",
      "body": "Plus, it's after Labor Day."
    },
    {
      "id": 4,
      "title": "By Thor's Hammer, I will have my revenge.",
      "body": "Also, by Odin's Eye"
    },
    {
      "id": 5,
      "title": "Get off the couch you lazy bum.",
      "body": "Yeah, it's way better to sit at a computer desk."
    }
  ]
}

The Index

To facilitate easy matching, I’m going to build a search index that will be a dictionary, with individual words (tokens) as the keys, and arrays of ID’s as the values.

I’ve decided on Python for my index builder. Handling JSON from Python is easy, though if you have a version older than 2.6 you will need to use a different import, such as simplejson.

The core of this functionality is the tokenizer. To build this, we need to determine our rules. Since this is a simple search, I’m going to tokenize on word boundaries, it will be case insensitive, and I will only accept the characters A-Z, single quote and dash inside of a word.

Here is my implementation of the tokenizer, that follows these rules:

6
7
8
9

def tokenize ( string ):
  # Strip extra punctuation
  string = re.sub( r'[^a-z0-9A-Z \'\-]', '', string.lower() )
  return string.split( ' ' )

The remainder of the Python is simply opening and parsing the JSON.

13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

  index = {}
 
  with open( 'data.json', 'r' ) as handle:
    obj = json.loads( handle.read() )
 
    for entry in obj['entries']:
      # Break up both title and body
      tokens = tokenize( entry['title'] )
      tokens.extend( tokenize( entry['body'] ) )
 
      # Make them unique by casting to set
      tokens = set( tokens )
 
      # Now add them to the index
      for token in tokens:
        # Make a new entry for the token if it doesn't exist
        if token not in index.keys():
          index[token] = []
        # Add this id to the list of matches for this token
        index[token].append( entry['id'] )

Run that, and we get the dictionary we wanted:

$ python build_index.py
{u'a': [1, 2, 5],
 u'after': [3],
 u'also': [4],
 u'angry': [2],
 u'anyone': [3],
 ...

JavaScript

Now that we have an index to work with, let’s convert it to JSON. This just takes a little tweak to the Python.

33
34

  with open( 'index.json', 'w' ) as handle:
    handle.write( json.dumps( index ) )

That gives us a JSON file to work with.

{"thor's": [4], "is": [2], "bum": [5], "didn't": [2, 3], "yeah": [5], ...

Now we’re going to load that JSON with an AJAX call, so we have the index to work with.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  init: function () {
    Search.$results = $( '#search-results' );
 
    $.getJSON( 'index.json' )
      .error( Search.index_load_error )
      .success( Search.index_load_success );
  },
 
  index_load_error: function () {
    Search.$results.append( $('<li/>').text( 'Error Loading Index' ) );
  },
 
  index_load_success: function ( data ) {
    Search.index = data;
  },

Once we have that data, finding matches is just a matter of looking them up in Search.index. Below I’ve used a loop that will search through an array of terms, and then accumulate the matches.

25
26
27
28
29
30
31
32

    var matches = [];
 
    // For each term passed in, check it in the index
    $.each( terms, function ( i, term ) {
      if( Search.index[term] ) {
        matches = matches.concat( Search.index[term] );
      }
    } );

It works!

Hook It Up

Just a little bit remains to connect this thing. First we need to port over the tokenizer from Python to get a consistent result. Pretty easy port.

47
48
49
50
51

  tokenize: function ( string ) {
    string = string.toLowerCase();
    string = string.replace( /[^a-z0-9A-Z \'\-]/, '' );
    return string.split( ' ' );
  }

JavaScript tokenize in action.

Last we just need to apply our functions to some inputs, which we hook up with some jQuery.

17
18
19
20
21
22
23
24
25
26
27
28
29
30

      $( function () {
        $( '#search-terms' ).keyup( function () {
          var results = Search.search( Search.tokenize( $(this).val() ) ),
              $results = $( '#search-results' );
 
          // Clear current results
          $results.children().remove();
 
          // Add new ones
          $.each( results, function ( index, element ) {
            $results.append( $( '<li/>' ).text( element ) );
          } );
        } );
      } );

Make It Better

This is not, by any means, a complete system. You would want to grab the results and match up the ID’s to a more useful output. Additionally, you could drop the AJAX call and use a script tag to bring in the index.

There are plenty of improvements you can make, and I’d love to know if you make them!

For reference, here is the complete source: https://gist.github.com/1673557.

Related Posts

1. Replacing MySQL FULLTEXT With JavaScript
2. Linux Multiple File Search And Replace
3. Javascript Colorshifter

“Just edit the makefile directly. autoconf and friends are the devil’s tools.”

- Linus Torvalds
subsurface README

Related Posts

1. Thursday Quote: Linus Torvalds
2. Thursday Quote: Danny O’Brien
3. Thursday Quote: Reg Braithwaite

After six years of sameness, I finally redesigned the blog.

While I was at it, I made it responsive, so it should look good on mobile too.

Some content is bound to still look funny as I haven’t reviewed all of it, but for the most part I think it looks good!

Special thanks to @johnhenrymuller for design help and my cool new logo.

Related posts:

1. BlowPass V0.60 – A Major Revision
2. In-Omaha.com

I used to have a Windows phone, and I used a cool service called Dashwire to sync all my photos, contacts, etc. to the web.

Dashwire is shutting down this month, which is sad, but I haven’t used it in a long time, since I switched to Android. However, I’ve still got photos on there, and I’d like to grab them before they are gone. Unfortunately, Dashwire doesn’t have an easy export option that I could find.

So, pass one involved the photos RSS feed available on the site. I wrote this script to grab the feed, parse and download the photos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import sys
import time
import feedparser
import urllib
 
if 2 > len( sys.argv ):
  print "usage: %s <dashwire username>" % ( sys.argv[0], )
  exit(1)
 
url = 'http://dashwire.com/%s/photos/feed' % ( sys.argv[1], )
 
print "Fetching: ", url
 
rss = feedparser.parse( url )
 
for item in rss.entries:
  timestamp  = time.strftime( '%Y-%m-%d %H:%M:%S', item.date_parsed )
  file_url   = item.media_content[0]['url'].replace( '-mobile.jpg', '.jpg' )
  file_local = '%s - %s.jpg' % ( timestamp, item.title )
 
  print "Downloading %s to %s" % ( file_url, file_local )
 
  request = urllib.urlopen( file_url )
  with open( file_local, 'wb' ) as handle:
    handle.write( request.read() )
  request.close()

It works as advertised, but it only drags down public photos, and only the most recent 30.

For round two I opened up the Dashwire dashboard and poked around their AJAX calls.

Turns out they have an images.json which has entries for every one of your photos in it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[{
  "rotation": 0,
  "unique_id": "-1294276037.2068.1142222",
  "modified_at": 1252717454,
  "body": null,
  "title": null,
  "seconds": 1252373668,
  "guid": "aWGu0CNZGr3OCJadbiFPIW",
  "private": true,
  "bucket": "media3.dashwire.com",
  "tags": [],
  "type": "Image",
  "id": 6734053,
  "height": 1920,
  "comments_count": 0,
  "ratings_average": 0,
  "width": 2560
},...]

To get this file, log into the dashboard, then download http://my.dashwire.com/images.json.

Once you have that, you will also need to figure out your user guid. You can do that with JavaScript, it’s stored in Dashwire.User.guid.

Then just plug it into the script below to get your stuff out!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys
import time
import json
import urllib
 
USER_KEY = '[get this from dashwire]'
obj = None
 
with open( 'images.json', 'r' ) as handle:
  obj = json.loads( handle.read() )
 
for image in obj:
  file_url = 'http://%s/media/%s/%s.jpg' % ( image['bucket'], USER_KEY, image['guid'] )
  timestamp = time.strftime( '%Y-%m-%d %H:%M:%S', time.localtime( image['seconds'] ) )
  file_local = '%s - %s.jpg' % ( timestamp, image['title'] )
 
  print "Downloading %s to %s" % ( file_url, file_local )
 
  request = urllib.urlopen( file_url )
  with open( file_local, 'wb' ) as handle:
    handle.write( request.read() )
  request.close()

Now sit back and enjoy as it downloads your photos!

Hurry up though, it all shuts down on Febuary 15th

Related posts:

1. KolorTool For KDE 4
2. BlowPass V0.60 – A Major Revision
3. Premature optimization is the root of all evil. But don’t be stupid.