From: Charles Mills <cmills@...>
Date: 2005-05-11T14:20:26+09:00
Subject: Re: String Hashing Algorithms


Zed A. Shaw wrote:
> 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/

You may be interested in this project:
http://www.rubyforge.org/projects/judy

Has an implementation of something like what you describe as a PATRICIA
above and a sparse hash.

-Charlie