Fast String Index

[Mark Bucciarelli]

I assume at some point Tenor will have to do the following task: given a
string key, lookup a corresponding record.

I just implemented this task using an extremely performant algorithm,
and wanted to share the reference with the list.

It's an algorithm designed by Jon Bentley (wrote Programming Perls, Bell
Labs ex-employee). It's called a ternery search tree and man is it fast.
With my 2.6Gh box I was able to perform 400,000 lookups a second on a
table with 10,000 entries and a eight character key (small table, but
still ...).

Here are the references:

    http://www.cs.princeton.edu/~rs/strings/paper.pdf

    http://www.cs.princeton.edu/~rs/strings/tstdemo.c

He also describes a multi-key quicksort and other fast ways to sort
strings. In general, a great read for those who enjoy algorithms.

m