Perfect Hashing


A hierarchical network of pattern engines needs a lot of memory. The lowest layers, however, may be frozen after some initial phase. During this early phase, new output symbols and feedback produce complicated locally constant functions. Later on, modified thresholds or increased veto will stabilize the domain borders. Change and adaptation will stop.
Such a layer may be stored in a very compact form.
Recent advances in computer science have produced a family of hash functions that are a perfect fit for this kind of table. There are now algorithms that can construct a minimal perfect hash function for a very large set of keys in linear time. The resulting hash function is perfect, it has no collisions. It is minimal, function evaluation is just a single array lookup. There is no overhead for a fill factor less than 100% and no overhead for chaining or other forms of collision handling. Storing such a function needs at least 1/log(2)=1.44 bits per key, and this limit is reached up to a small constant factor.
But look for yourself at sourceforge .
The authors have built a complete, ready to use library under the LGPL. Thank you very much.

P.S. I’m trying to understand the algorithms. A minimal perfect hash function X ⟶ Y is just a universal map from X to Y. The graph-theoretic background may have implications for the pattern engine itself. Can you spot the hypergraph lurking in the logo? The image of a point of X under (hk) is an „edge“ in a uniform hypergraph. The engine is trying to solve a coloring problem.

 Date Posted: 27 Dez 2009 @ 12 20 PM
Last Modified: 19 Jun 2010 @ 11 41 PM
Posted By: Hardy

Responses to this post » (None)


Post a Comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

\/ More Options ...
Change Theme...
  • Users » 3
  • Posts/Pages » 40
  • Comments » 3
Change Theme...
  • VoidVoid
  • LifeLife « Default
  • EarthEarth
  • WindWind
  • WaterWater
  • FireFire
  • LightLight

On Digital Memory

    No Child Pages.