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.
(comments to anakin@pobox.com)
(thanks to
chiark
for hosting this page)
(last modified on Sun May 7 14:33:22 2017)