NAME
perfect_hash
DESCRIPTION
Generate a minimal perfect hash function for the keys in a file,
desired hash values may be specified within this file as well.
A given code template is filled with parameters, such that the
output is code which implements the hash function.
Templates can easily be constructed for any programming language.
The code is based on an a program A.M. Kuchling wrote:
http://www.amk.ca/python/code/perfect-hash
The algorithm the program uses is described in the paper
'Optimal algorithms for minimal perfect hashing',
Z. J. Czech, G. Havas and B.S. Majewski.
http://citeseer.ist.psu.edu/122364.html
The algorithm works like this:
1. You have K keys, that you want to perfectly hash against some
desired hash values.
2. Choose a number N larger than K. This is the number of
vertices in a graph G, and also the size of the resulting table G.
3. Pick two random hash functions f1, f2, that return values from 0..N-1.
4. Now, for all keys, you draw an edge between vertices f1(key) and f2(key)
of the graph G, and associate the desired hash value with that edge.
5. If G is cyclic, go back to step 2.
6. Assign values to each vertex such that, for each edge, you can add
the values for the two vertices and get the desired (hash) value
for that edge. This task is easy, because the graph is acyclic.
This is done by picking a vertex, and assigning it a value of 0.
Then do a depth-first search, assigning values to new vertices so that
they sum up properly.
7. f1, f2, and vertex values of G now make up a perfect hash function.
For simplicity, the implementation of the algorithm combines steps 5 and 6.
That is, we check for loops in G and assign the vertex values in one procedure.
If this procedure succeeds, G is acyclic and the vertex values are assigned.
If the procedure fails, G is cyclic, and we go back to step 2, replacing G
with a new graph, and thereby discarding the vertex values from the failed
attempt.
CLASSES
builtins.Exception(builtins.BaseException)
TooManyInterationsError
builtins.object
Format
Graph
IntSaltHash
StrSaltHash
class Format(builtins.object)
| Format(width=76, indent=4, delimiter=', ')
|
| Methods defined here:
|
| __call__(self, data, quote=False)
| Call self as a function.
|
| __init__(self, width=76, indent=4, delimiter=', ')
| Initialize self. See help(type(self)) for accurate signature.
|
| print_format(self)
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
__weakref__
| list of weak references to the object (if defined)
class Graph(builtins.object)
| Graph(N)
|
| Implements a graph with 'N' vertices. First, you connect the graph with
| edges, which have a desired value associated. Then the vertex values
| are assigned, which will fail if the graph is cyclic. The vertex values
| are assigned such that the two values corresponding to an edge add up to
| the desired edge value (mod N).
|
| Methods defined here:
|
| __init__(self, N)
| Initialize self. See help(type(self)) for accurate signature.
|
| assign_vertex_values(self)
| Try to assign the vertex values, such that, for each edge, you can
| add the values for the two vertices involved and get the desired
| value for that edge, i.e. the desired hash key.
| This will fail when the graph is cyclic.
|
| This is done by a Depth-First Search of the graph. If the search
| finds a vertex that was visited before, there's a loop and False is
| returned immediately, i.e. the assignment is terminated.
| On success (when the graph is acyclic) True is returned.
|
| connect(self, vertex1, vertex2, edge_value)
| Connect 'vertex1' and 'vertex2' with an edge, with associated
| value 'value'
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
class IntSaltHash(builtins.object)
| IntSaltHash(N)
|
| Random hash function generator.
| Simple byte level hashing, each byte is multiplied in sequence to a table
| containing random numbers, summed tp, and finally modulo NG is taken.
|
| Methods defined here:
|
| __call__(self, key)
| Call self as a function.
|
| __init__(self, N)
| Initialize self. See help(type(self)) for accurate signature.
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
|
| ----------------------------------------------------------------------
| Data and other attributes defined here:
|
| template = '\nS1 = [$S1]\nS2 = [$S2]\nassert len(S1) == len(S2)... (G[...
class StrSaltHash(builtins.object)
| StrSaltHash(N)
|
| Random hash function generator.
| Simple byte level hashing: each byte is multiplied to another byte from
| a random string of characters, summed up, and finally modulo NG is
| taken.
|
| Methods defined here:
|
| __call__(self, key)
| Call self as a function.
|
| __init__(self, N)
| Initialize self. See help(type(self)) for accurate signature.
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
|
| ----------------------------------------------------------------------
| Data and other attributes defined here:
|
| chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ012345678...
|
| template = '\ndef hash_f(key, T):\n return sum(ord(T[i % $N...S1")]...
class TooManyInterationsError(builtins.Exception)
| Common base class for all non-exit exceptions.
|
| Method resolution order:
| TooManyInterationsError
| builtins.Exception
| builtins.BaseException
| builtins.object
|
| Data descriptors defined here:
|
| __weakref__
| list of weak references to the object (if defined)
|
| ----------------------------------------------------------------------
| Methods inherited from builtins.Exception:
|
| __init__(self, /, *args, **kwargs)
| Initialize self. See help(type(self)) for accurate signature.
|
| ----------------------------------------------------------------------
| Static methods inherited from builtins.Exception:
|
| __new__(*args, **kwargs) from builtins.type
| Create and return a new object. See help(type) for accurate signature.
|
| ----------------------------------------------------------------------
| Methods inherited from builtins.BaseException:
|
| __delattr__(self, name, /)
| Implement delattr(self, name).
|
| __getattribute__(self, name, /)
| Return getattr(self, name).
|
| __reduce__(...)
| Helper for pickle.
|
| __repr__(self, /)
| Return repr(self).
|
| __setattr__(self, name, value, /)
| Implement setattr(self, name, value).
|
| __setstate__(...)
|
| __str__(self, /)
| Return str(self).
|
| with_traceback(...)
| Exception.with_traceback(tb) --
| set self.__traceback__ to tb and return self.
|
| ----------------------------------------------------------------------
| Data descriptors inherited from builtins.BaseException:
|
| __cause__
| exception cause
|
| __context__
| exception context
|
| __dict__
|
| __suppress_context__
|
| __traceback__
|
| args
FUNCTIONS
builtin_template(Hash)
generate_code(keys, Hash=, template=None, options=None)
Takes a list of key value pairs and inserts the generated parameter
lists into the 'template' string. 'Hash' is the random hash function
generator, and the optional keywords are formating options.
The return value is the substituted code template.
generate_hash(keys, Hash=)
Return hash functions f1 and f2, and G for a perfect minimal hash.
Input is an iterable of 'keys', whos indicies are the desired hash values.
'Hash' is a random hash function generator, that means Hash(N) returns a
returns a random hash function which returns hash values from 0..N-1.
main()
read_table(filename, options)
Reads keys and desired hash value pairs from a file. If no column
for the hash value is specified, a sequence of hash values is generated,
from 0 to N-1, where N is the number of rows found in the file.
read_template(filename)
run_code(code)
DATA
absolute_import = _Feature((2, 5, 0, 'alpha', 1), (3, 0, 0, 'alpha', 0...
division = _Feature((2, 2, 0, 'alpha', 2), (3, 0, 0, 'alpha', 0), 1310...
print_function = _Feature((2, 6, 0, 'alpha', 2), (3, 0, 0, 'alpha', 0)...
trials = 5
verbose = False
VERSION
0.4.2