Succinct Data Structures: Cramming 80,000 words into a Javascript file.

jQuery creator John Resig needs a little help storing lists of words in his side project. Let's go overkill and explore a little known branch of computer science called Succinct Data Structures.

Simulating freehand drawing with Cairo

Microsoft's generosity knows no end for a year (comic)

How a programmer reads your resume (comic)

People thought it was a comic, so I never corrected them.

A simple command line calculator

A textbook example of recursive descent parsing.

Sign here (comic)

qb.js: An implementation of QBASIC in Javascript

Play NIBBLES.BAS in your browser. I re-implemented a small part of QBASIC as a compiler in Javascript, so it runs in a webpage.

O(n) Delta Compression With a Suffix Array

The difference between two sequences A and B can be compactly stored using COPY/INSERT operations. The greedy algorithm for finding these operations relies on an efficient way of finding the longest matching part of A of any given position in B. This article describes how to use a suffix array to find the optimal sequence of operations in time proportional to the length of the input sequences. As a preprocessing step, we find and store the longest match in A for every position in B in two passes over the suffix array.

Regular Expression Matching can be Ugly and Slow

If you open the first few pages of O'Reilly's Beautiful Code, you will find a well written chapter by Brian Kernighan (Personal motto: "No, I didn't invent C. Who told you that?"). The non-C inventing professor describes how a limited form of regular expressions can be implemented elegantly in only a few lines of C code.

Comment spam defeated at last

For years when running this blog, I would have to log in each day and delete a dozen comments due to spam. This was a chore, and I tried many ways to stem the tide.