Using space filling curves as a heuristic for shortest path algorithms

Simple Full Text Search for App Engine

Revised 2009-07-12 to include addition of stemming, multi-word exact matching, multiple search entities, and stowing of designated parent titles in index entity keys.

The basic insight behind Levenshtein automata is that it's possible to construct a Finite state automaton that recognizes exactly the set of strings within a given Levenshtein distance of a target word. We can then feed in any word, and the automaton will accept or reject it based on whether the Levenshtein distance to the target word is at most the distance specified when we constructed the automaton. Further, due to the nature of FSAs, it will do so in O(n) time with the length of the string being tested. Compare this to the standard Dynamic Programming Levenshtein algorithm, which takes O(mn) time, where m and n are the lengths of the two input words! It's thus immediately apparrent that Levenshtein automaton provide, at a minimum, a faster way for us to check many words against a single target word and maximum distance - not a bad improvement to start with!

Search Index compression

A GNU-FDL book on algorithmic graph theory.

TeX line breaking algorithm in JavaScript

The downside to all this is that you send months developing your complex algorithms and when you’re done you show somebody the result of all your efforts — a page or two of code. It looks like something that somebody could have written in an afternoon. Even worse, you start to suspect that if you had really known scipy and spent a few days carefully thinking about the problem to start with, then you probably could have coded it in an afternoon. It’s a little embarrassing.

the homepage of peter Norvig, with many links to software design articles and software examples in python and lisp. He now works at google as a director of research.