Re: fast dictionary search algorithm

From: Paul Hsieh (qed_at_pobox.com)
Date: 02/10/04 

Date: 9 Feb 2004 21:14:04 -0800

prashanthellina@gmx.net (Prashanth Ellina) wrote:
> I have a text file with words and meanings. The record count is
> approximately 100,000. I need to develop an algorithm that will find a
> requested word's meaning in the shortest time possible. The algorithm
> may be a combination of existing search algorithms or an
> improvisation.
>
> I have considered hashing and multiple level hashing as an option
> but am not sure about the hash function. People tell me it is
> difficult to avoid collisions. Have tried binary search, however need
> something faster.

Collisions are not fatal. And they aren't necessarily slow if you
don't go the route of rehashing. For example, for all the entries
that land on a given hash index, simply place them all into a sorted
binary, and use binary search on them from there. In this way you get
the benefit of the massive narrowing of your search via hashing, and
the O(log(n)) guarantee of the binary tree at the same time.

You can think of hashing as using your CPU's brute force hardware to
simultaneously perform roughly the top 15 levels of a binary search by
direct computation.

Here's is a state of the art hash function which will help minimize
your collisions:

    http://www.isthe.com/chongo/tech/comp/fnv/ 

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Relevant Pages

  • Re: fast dictionary search algorithm
    ... Prashanth Ellina wrote: ... > I have a text file with words and meanings. ... The algorithm ... > I have considered hashing and multiple level hashing as an option ...
    (comp.programming)
  • Re: fast dictionary search algorithm
    ... > I have a text file with words and meanings. ... The algorithm ... If you had all the entries in a decently-balanced binary search tree, ... where you have a perfect hash, and good luck finding a perfect hash that ...
    (comp.programming)
  • Re: fast dictionary search algorithm
    ... > I have a text file with words and meanings. ... The algorithm ... > I have considered hashing and multiple level hashing as an option ... The Aho-corasick multiple string search algorithm may be worth looking at. ...
    (comp.programming)
  • Re: fast dictionary search algorithm
    ... > I have a text file with words and meanings. ... The algorithm ... > I have considered hashing and multiple level hashing as an option ... trees, and select which tree to search by. ...
    (comp.programming)
  • Re: fast dictionary search algorithm
    ... > I have a text file with words and meanings. ... The algorithm ... > I have considered hashing and multiple level hashing as an option ... > but am not sure about the hash function. ...
    (comp.programming)