Simon Tatham's Algorithms Page

This web page is a repository for algorithms, maintained by Simon Tatham. Its purposes are:

• To provide unusual algorithms to people who might have a use for them.
• To make interesting reading for people who are into algorithm design.
• To act as prior art in case anybody else tries to patent one of these algorithms.

In addition to actual algorithms, I've also got a couple of unsolved problems, in the hope that people might send me ideas on how to solve them.

If you have an interesting and unusual algorithm and would like it stored on this site, send it to me and I might well add it. If you could write it up in HTML in a form that looks like the existing pages, that would be helpful.

Algorithms on this site don't have to be new and undiscovered inventions. They only have to be unusual enough not to show up in the average algorithms textbook.

So, enough of the introduction. Time for some actual algorithms.

Algorithms I have invented

(Disclaimer: I don't intend to imply that nobody else has ever thought of these algorithms. They might easily have done. The nice thing about not patenting them is that I don't have to know for sure whether they're original or not :-)

Cumulative frequency tables

A quick (log-time) mechanism for maintaining a cumulative frequency table. Useful in adaptive compression methods (particularly arithmetic compression). Might also have applications in assembly or code generation.

A block-sorting approach to string searching

A method of searching one string for another, inspired by the Burrows-Wheeler transform. Unlike most searching algorithms, which are optimised to search for one needle in a large amount of haystack text, this algorithm is optimised to take one fixed haystack and search it very fast for lots of different needles.

Sorting a linked list using Mergesort

All the serious computer-science literature about sorting tells you how to do it on arrays. As it turns out, sorting a linked list is much easier, but nobody actually bothers to tell you about it. Well, I do, and here's how you can use a variant of Mergesort to sort a linked list in reliable O(N log N) time, with no worst cases, no auxiliary storage requirements, and stably.

Counted B-trees

An enhancement to the well known B-tree algorithms to allow you to look up items in the tree by numeric index, or to find the numeric index of an item. Useful for finding percentiles, for deciding on a strategy for a complex search operation, or for storing items in a B-tree in arbitrary order without a sorting criterion.

Reversible linked lists

A modified form of doubly linked list, which allows an arbitrary section of a list to be reversed in constant time, simply by changing a few pointers around, like any list splice operation. Completely useless as far as I know, but very cute.

Unsolved problems: algorithms I wish I knew

Equivalence relations

I'd like a data structure that represents an equivalence relation on a given set, so that you start off assuming everything to be equivalent, and gradually split equivalence classes as more and more distinctions are found between elements. Applications include state machine construction, but I'm sure there are others.