From: "Zed A. Shaw" <zedshaw@...>
Date: 2005-05-11T07:38:40+09:00
Subject: Re: String Hashing Algorithms

On Wed, 2005-05-11 at 05:00 +0900, Phrogz wrote:
> 
> Background
> =============================================================
> At work, we have some (young) code which is currently doing a lot of
> string compares, which needs to be really fast. We're about to try
> using hashes of the strings to represent each string instead, but
> instead of a traditional hash table (which 'chains' collisions for the
> same key) we're going to require that no two (different) strings may
> share the same hash key.

Just out of curiosity, but have you considered some other
structures/algorithms which might be alternatives depending on your
usage?  Off the top of my head I can think of:

* Trie -- Should find other strings really fast, but gets pretty big the
more strings you need to store.  There's a C library for this at
http://www.octavian.org/cs/software.html
* PATRICIA -- Basically a compacted Trie which takes less space.
Couldn't find a library for this one.
* Suffix Array -- I have a Ruby binding for one of the faster C
libraries which I use in FastCST.  The big advantage of a Suffix Array
is that you can store it so that you only need to calculate the suffix
array once.  A suffix array is really more useful for matching and
exclusion.
* Suffix Tree -- There's really not much of a reason to use suffix trees
these days since newer suffix array construction algorithms are faster.
The main advantage of a suffix tree is that searching for a result can
be faster.  The main disadvntages are that they are fat memory pigs.
* Bloom Filter -- These are not as acurate, but they can be fast as all
hell if you just want to match strings with some probability.

Anyway, just thought I'd throw out some alternatives to hash tables for
certain situations.  I'd say if you need to match C++ keywords to a
stored index then take a look at the libtst Trie implementation.  It's
quite fast for that application.  If you just need to see if a certain
word is "included" or "excluded" than a suffix array could do that
really fast.  Trick there is to build the suffix array by joining the
strings with a | character (or something else) between them.  Nice thing
about a suffix array is that you can build it offline and then just load
it directly for the searching.

Zed A. Shaw
http://www.zedshaw.com/