Building a search engine using Redis and redis-py

Redis is a remote data structure server. You can think of it like memcached with strings, lists, sets, hashes, and zsets (hashes that you can sort by value).

All of the operations that you expect are available: list push/pop from either end, sorting lists and sets, sorting based on a lookup key or hash, and more. Redis also offers set intersection/union, zset intersection/union with aggregation methods, master/slave replication, on-disk persistence, clients for most major modern languages, and an active discussion group.

Why build a search engine from scratch when Lucene, Xapian, and other software are available? To start: simplicity, speed, and flexibility. We are going to build a search engine implementing TF/IDF search with Redis, redis-py, and a few lines of Python. With small changes, you can integrate your own document importance scoring or combine TF/IDF with pre-computed PageRank.

First things first

You need a recent version of Redis installed on your platform. The original article used Redis git head because it depended on features not yet available in a stable release. After Redis is running, install redis-py.

For fuzzy full-text search, the article also points to PlayNice.ly's approach, which uses Metaphone or Double Metaphone to handle spelling mistakes. Porter stemming can normalize tense, so jump, jumping, and jumped become jump. Depending on your context, use one, neither, or both.

Have everything running? Let's run some tests.

>>> import redis
>>> r = redis.Redis()
>>> r.sadd('temp1', '1')
True
>>> r.sadd('temp2', '2')
True
>>> r.sunion(['temp1', 'temp2'])
set(['1', '2'])
>>> p = r.pipeline()
>>> r.scard('temp1')
1
>>> p.scard('temp1')
<redis.client.pipeline object at 0x022EC420>
>>> p.scard('temp2')
<redis.client.Pipeline object at 0x022EC420>
>>> p.execute()
[1, 1]
>>> r.zunionstore('temp3', {'temp1':2, 'temp2':3})
2
>>> r.zrange('temp3', 0, -1, withscores=True)
[('1', 2.0), ('2', 3.0)]

That is more or less the meat of everything we will use: add items to sets, union sets with weights, use pipelines to minimize round-trips, and pull items out with scores.

Parse the documents

To index documents, start by including only alpha-numeric characters and apostrophes for contractions such as can't and won't. If you use Porter stemming or Metaphone, contractions and ownerships such as Joe's can be handled automatically. A secondary word dictionary can ensure that a stemmer produces a real base word.

Indexing and index removal are similar, so the same function can handle both operations.

import re

NON_WORDS = re.compile("[^a-z0-9' ]")

# stop words pulled from the below url
# http://www.textfixer.com/resources/common-english-words.txt
STOP_WORDS = set('''a able about across after all almost also am
among an and any are as at be because been but by can cannot
could dear did do does either else ever every for from get got
had has have he her hers him his how however i if in into is it
its just least let like likely may me might most must my neither
no nor not of off often on only or other our own rather said say
says she should since so some than that the their them then
there these they this tis to too twas us wants was we were what
when where which while who whom why will with would yet you
your'''.split())

def get_index_keys(content, add=True):
		# Very simple word-based parser. We skip stop words and
		# single character words.
		words = NON_WORDS.sub(' ', content.lower()).split()
		words = [word.strip("'") for word in words]
		words = [word for word in words
								if word not in STOP_WORDS and len(word) > 1]
		# Apply the Porter Stemmer here if you would like that
		# functionality.

		# Apply the Metaphone/Double Metaphone algorithm by itself,
		# or after the Porter Stemmer.

		if not add:
				return words

		# Calculate the TF portion of TF/IDF.
		counts = collections.defaultdict(float)
		for word in words:
				counts[word] += 1
		wordcount = len(words)
		tf = dict((word, count / wordcount)
								for word, count in counts.iteritems())
		return tf

Stop words are so common that they are mostly worthless to indexing or search. The provided set is aggressive, but it helps direct searches toward meaningful content.

In your own code, tweak parsing to suit your data. Phrase parsing, URL extraction, hashtags, @tags, and special tokens such as has_url, has_attachment, is_banned, or is_active can all improve search quality.

Build the index

Now add term frequencies to the appropriate Redis sorted sets. Adding and removing from the index are almost identical, so one function can do both.

def handle_content(connection, prefix, id, content, add=True):
		# Get the keys we want to index.
		keys = get_index_keys(content)

		# Use a non-transactional pipeline here to improve
		# performance.
		pipe = connection.pipeline(False)

		# Adding and removing use the same shape of operation.
		if add:
				pipe.sadd(prefix + 'indexed:', id)
				for key, value in keys.iteritems():
						pipe.zadd(prefix + key, id, value)
		else:
				pipe.srem(prefix + 'indexed:', id)
				for key in keys:
						pipe.zrem(prefix + key, id)

		# Execute the insertion/removal.
		pipe.execute()

		# Return the number of keys added/removed.
		return len(keys)

Redis pipelines bulk-execute commands to reduce network round-trips. Fewer round-trips translate into improved performance because network latency is often the slow part of a Redis interaction. At this point, the function has added or removed zset key/value pairs. The only thing left is search.

Search with TF/IDF

The search function parses query terms just as indexing did, fetches the number of documents containing each term, calculates IDF, and uses ZUNIONSTORE to combine the weighted term scores.

import math
import os

def search(connection, prefix, query_string, offset=0, count=10):
		# Get search terms just like we did earlier.
		keys = [prefix + key
						for key in get_index_keys(query_string, False)]

		if not keys:
				return [], 0

		total_docs = max(
				connection.scard(prefix + 'indexed:'), 1)

		# Get document frequency values.
		pipe = connection.pipeline(False)
		for key in keys:
				pipe.zcard(key)
		sizes = pipe.execute()

		# Calculate inverse document frequencies.
		def idf(count):
				if not count:
						return 0
				return max(math.log(total_docs / count, 2), 0)
		idfs = map(idf, sizes)

		# Generate weights for zunionstore.
		weights = dict((key, idfv)
						for key, size, idfv in zip(keys, sizes, idfs)
								if size)

		if not weights:
				return [], 0

		# Generate temporary result storage.
		temp_key = prefix + 'temp:' + os.urandom(8).encode('hex')
		try:
				known = connection.zunionstore(temp_key, weights)
				ids = connection.zrevrange(
						temp_key, offset, offset+count-1, withscores=True)
		finally:
				connection.delete(temp_key)
		return ids, known

The first part parses search terms. The second fetches document frequency, which is needed for IDF. The third calculates IDF and packs it into a weights dictionary. Finally, ZUNIONSTORE multiplies each term's TF score by its IDF weight, combines scores by document ID, and returns the highest-scoring results.

Those snippets are enough to build a working search engine with Redis. The original author also published a more useful interface and a minimal test case in this GitHub Gist.

Ideas for improvements

• Replace TF with the constant 1. This lets you replace sorted sets with standard sets and reduce memory requirements for large indexes. Test both approaches against your data.
• Search quality is largely about parsing. Parse documents so users can find them through tags, phrases, URLs, references, and other useful signals.
• Parse queries intelligently. A query such as web history search +firefox -ie could boost Firefox, penalize IE, and use SDIFF to explicitly exclude documents when using sets.
• Pipeline the commands that currently run outside a pipeline. ZUNIONSTORE and ZRANGE can be combined in another pipeline if result ordering is handled correctly.
• Store all indexed keys for each document ID in a set. Un-indexing can then fetch those names with SMEMBERS, issue the relevant ZREM calls, remove the indexed marker, and delete the key set.

There are countless improvements to this basic index and search code. Try different ideas and see what you can build.

A personal search history

The author first worked in indexing and search at Affini, where William I. Chang taught him the fundamentals of natural language indexing and search. The work included an ad-targeting system over LiveJournal users' interests, location, age, and gender; spam filtering; Craigslist search subscriptions; and targeted advertising.

Before Redis existed, he built search infrastructure from scratch: parsing in Python, indexing and search using Pyrex and C. The same system supported email search and live search over incoming Craigslist ads. These problems are much easier with Redis.

For more writing like this, the original post recommends Redis in Action from Manning Publications.