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

“..the way humans (especially engineer-humans) perceive beauty is intimately related to our ability to process and understand complexity. A language that makes it hard to write elegant code makes it hard to write good code.”

- Eric S. Raymond
Why Python?

Related posts:

1. Thursday Quote: Eric Hellman
2. Thursday Quote: Jonathan Edwards
3. XML, XSL Are Stinkin Powerfull

I’ve had trouble compiling native extensions on the Mac before, but I finally found a fix.

You just need the correct ARCHFLAGS environment variable. You can set this in your .bashrc or use it right before python setup.py build

ARCHFLAGS="-arch i386 -arch x86_64"

This works because XCode dropped the PPC compiler in v4, and with that variable we tell the setup script not to bother trying to compile for that arch, just i386 and x86_64.

Much thanks to Y.H. Wong in this Super User thread.

No related posts.

Yesterday I was stuck at the office while Darcy got a flat replaced. I decided to make a Markdown editor real quick, since I’m always using the web dingus to preview it, and that gets old.

I found the python-markdown2 library, and then decided to try out the WebKit integration in Qt4.

The best word for it is painless. Seriously, I got the first version glued together in about ten minutes, including finding the markdown library and reading all the docs for QWebView. It’s a brutal hack, but it worked just fine, and only took up 45 lines of code.

I’ve since dropped in three more markup languages, as well as cleaned it up to something readable. But I doubt I have more than a couple hours invested thus far.

I think this is a quintessential demonstration of the power of Python, which breaks down to three things.

1. Fast development
   No compile cycle, it reduces the barrier to creating a prototype.
2. Huge Ecosystem
   There is a library for everything and it’s all easy to get to and use.
3. Good Documentation & Intuitive Behavior
   Most packages have good documentation, and those that don’t still behave intuitively. Just pydoc around until you find what you need.

MarkedUp is now feature complete, stable, and available at your local github.

Related posts:

1. Looking up words in a Dictionary using Python
2. I am a fool….
3. Charting Weight Change With Google Visualizations

There is a relatively prevalent quote in the programming world, bandied about by programmers of all creeds.

“Premature optimization is the root of all evil.”

- Donald Knuth

I agree. What we intuit about optimization is usually wrong. And what’s more, until you hit a bottleneck, it’s often a waste of time. Moore has been good to us, and CPU bound problems aren’t as common as they once were.

That said, I think people should not cling to this. It’s dumb.

Today I was looking for a better way to compute sha1 file hashes in PHP. I know about sha1() obviously, but that’s not how it should be done for files.

Python provides the excellent hashlib that lets you update a hash with blocks of data. It’s excellent for file hashing, because you can read in data in chunks and update the hash as you go, thus avoiding reading the whole file into memory at once. Here, have a sample program that reads in 512 byte chunks.

1
2
3
4
5
6
7
8
9
10
11

>>> import hashlib
>>> hash = hashlib.sha1()
>>> with open( 'test.jpg', 'r' ) as handle:
...     while True:
...             data = handle.read(512)
...             if not data:
...                     break
...             hash.update( data )
... 
>>> hash.hexdigest()
'9e8d5ee361c6988baf7f75999f2c854a765f3eca'

So I quickly found the sha1_file() function. Perfect, I’m sure this reads in chunks, otherwise they would not have bothered to make the function.

Then I scroll down to check the user contributed notes for anything interesting. The top two notes are examples of using this snippet to get a sha1 hash of a file:

$hash = sha1( file_get_contents( $file ) );

I was stunned. The definition of file_get_contents() is as follows:

“Reads entire file into a string.”

Surely they are not suggesting that I read the entire file into memory, as a PHP variable, and then pass it on to the hashing function? Who would think that is a good solution, when there is a perfectly good built in function to do this for you, in chunks, in a neater fashion?

My only explanation is ignorance, or utter lack of consideration. I gave it a test with these two PHP scripts.

1
2
3

<?php
        echo sha1( file_get_contents( 'test.jpg' ) ) . "\n";
        echo memory_get_peak_usage() . "\n";

1
2
3

<?php
        echo sha1_file( 'test.jpg' ) . "\n";
        echo memory_get_peak_usage() . "\n";

The first version weighed in as using slightly more memory than second one. About 89k actually. And test.jpg is 88k.

Imagine if that picture was a few megs bigger. Imagine if I could somehow trigger this process on your website, over and over again with ab or something. It’s a DOS in the making.

Develop however you want to, just please, please don’t be stupid.

Related posts:

1. PHP Virtual Machine, Version 0.01
2. Thursday Quote: Rob Pike
3. Charting Weight Change With Google Visualizations

I’ve been meaning to check out the Tweepy for a while and got around to it today. It’s a Python library for interacting with Twitter. The feature I’m most interested in is the streaming API support, which isn’t advertised much by Tweepy but seems pretty solid.

Tweepy has pretty good documentation, and the code is terse and readable, but what I found most useful was the examples repository, which had the only example of streaming with Tweepy that I could find in the official documentation.

It’s really straightforward. Implement a tweepy.streaming.StreamListener to consume data, set up a tweepy.streaming.Stream with that listener, then pull the trigger on the streaming function you want to use.

Here’s a quick example I set up to track the filter keyword “omaha”.

# -*- coding: utf-8 -*-
 
from tweepy.streaming import StreamListener, Stream
 
class Listener ( StreamListener ):
  def on_status( self, status ):
    print '-' * 20
    print status.text
    return
 
if __name__ == "__main__":
 
  USERNAME = "YourUsernameHere"
  PASSWORD = "YourPasswordHere"
 
  listener = Listener()
  stream = Stream(
    USERNAME,
    PASSWORD,
    listener
  );
 
  stream.filter( track=( "omaha", ) )

Related posts:

1. Python UNIX Sockets
2. Handling Forms With PHP
3. Auto-Generated Github User Page With py-github

Github has a cool feature called “Github Pages” that let you host static content on a subdomain of github, e.g. http://jmhobbs.github.com/.

They also provide an auto-generator for project pages that has a nice clean format which I really like. So I decided to make my user page match the look and feel of the project pages. And to boot I wanted to be able have it auto-generate since I want it to be “hands free”, otherwise I’ll forget to update it.

To make this happen I whipped up my template and then grabbed the excellent py-github from Dustin Sallings, which I have used before.

Without furthur ado I’ll just show you the source. It’s not complicated, just some API calls then search replace on a template file. If you want to use it, be sure to get the most recent version from http://github.com/jmhobbs/jmhobbs.github.com.

Throw in a cron job and you are set. Beware of lot’s of “page build” notices from Github though.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

# -*- coding: utf-8 -*-
 
import github.github as github
import yaml
import time
from datetime import datetime
 
def repo_date_to_epoch ( date ):
  epoch = time.mktime(
    time.strptime(
      date[0:-6],
      "%Y-%m-%dT%H:%M:%S"
    )
  )
  return int( epoch )
 
def main ():
 
  print "Loading settings...."
  f = open( 'settings.yaml' )
  settings = yaml.load( f )
  f.close()
 
  gh = github.GitHub()
 
  print "Fetching user information..."
  user = gh.users.show( settings['username'] )
 
  print "Fetching repository information..."
  repos = gh.repos.forUser( settings['username'] )
 
  print "Sorting repositories..."
  repos = sorted( repos, cmp=lambda a, b: repo_date_to_epoch( b.pushed_at ) - repo_date_to_epoch( a.pushed_at ) )
 
  print "Loading template..."
  f = open( 'index.html.tpl' )
  template = f.read()
  f.close()
 
  print "Mangling template..."
  template = template.replace( '<% username %>', settings['username'] )
  template = template.replace( '<% fullname %>', user.name )
  template = template.replace( '<% email %>', user.email )
  template = template.replace( '<% following %>', str( user.following_count ) )
  template = template.replace( '<% followers %>', str( user.followers_count ) )
  template = template.replace( '<% publicrepos %>', str( user.public_repo_count ) )
 
  repo_string = ''
 
  for repo in repos:
    if repo.private:
      continue
 
    repo_string = repo_string + '<div class="repo"><h3><a href="' + repo.url + '">' + repo.name + '</a>'
 
    try:
      repo_string = repo_string + ' - <span class="small"><a href="' + repo.homepage + '">' + repo.homepage + '</a></span>'
    except AttributeError:
      pass
 
    repo_string = repo_string + '</h3>'
 
    repo_string = repo_string + "Forks: " + str( repo.forks ) + " - Watchers: " + str( repo.watchers ) + ' | '
 
    if repo.has_issues:
      repo_string = repo_string + ' <a href="' + repo.url + '/issues">Issues</a> |'
 
    if repo.has_wiki:
      repo_string = repo_string + ' <a href="http://wiki.github.com/' + settings['username'] + '/' + repo.name + '">Wiki</a> |'
 
    if repo.has_downloads:
      repo_string = repo_string + ' <a href="' + repo.url + '/downloads">Downloads</a> |'
 
    repo_string = repo_string + '<br/>Last Push: ' + datetime.fromtimestamp( repo_date_to_epoch( repo.pushed_at ) ).ctime()
 
    try:
      repo_string = repo_string + '<pre>' + repo.description + '< /pre>'
    except AttributeError:
      repo_string = repo_string + '<br/><br/>'
      pass
 
    repo_string = repo_string + "</div><!--// .repo //-->\n"
 
  template = template.replace( '<% repos %>', repo_string )
 
  ga = """
    <script type="text/javascript">
      var _gaq = _gaq || [];
      _gaq.push(['_setAccount', '<% ga_code %>']);
      _gaq.push(['_trackPageview']);
      (function() {
        var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
        ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
        var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
      })();
    </script>
  """
 
  if False != settings['google_analytics']:
    template = template.replace( '<% google_analytics %>', ga )
    template = template.replace( '<% ga_code %>', settings['google_analytics'] )
  else:
    template = template.replace( '<% google_analytics %>', '' )
 
  print "Writing file..."
  f = open( 'index.html', 'w' )
  f.write( template )
  f.close()
 
  print "Done!"
 
if __name__ == "__main__":
  main()

Wow. You actually scrolled through all of that. Amazing.

Related posts:

1. Territorial Seeds User Script
2. I was featured on Github! Sort of.
3. USB7 + pySerial

1. Looking up words in a Dictionary using Python
2. Awesome C Program
3. KolorTool For KDE 4