1 # Derived from: https://github.com/ilanschnell/perfect-hash
2 # Commit: e376138af70db9f668de7e23cf84671872a676d8
6 # Copyright (c) 2019, Ilan Schnell
9 # Redistribution and use in source and binary forms, with or without
10 # modification, are permitted provided that the following conditions are met:
11 # * Redistributions of source code must retain the above copyright
12 # notice, this list of conditions and the following disclaimer.
13 # * Redistributions in binary form must reproduce the above copyright
14 # notice, this list of conditions and the following disclaimer in the
15 # documentation and/or other materials provided with the distribution.
16 # * Neither the name of the <organization> nor the
17 # names of its contributors may be used to endorse or promote products
18 # derived from this software without specific prior written permission.
20 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
21 # ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
22 # WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
23 # DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
24 # DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25 # (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
26 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
27 # ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29 # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 Generate a minimal perfect hash function for the keys in a file,
33 desired hash values may be specified within this file as well.
34 A given code template is filled with parameters, such that the
35 output is code which implements the hash function.
36 Templates can easily be constructed for any programming language.
38 The code is based on an a program A.M. Kuchling wrote:
39 http://www.amk.ca/python/code/perfect-hash
41 The algorithm the program uses is described in the paper
42 'Optimal algorithms for minimal perfect hashing',
43 Z. J. Czech, G. Havas and B.S. Majewski.
44 http://citeseer.ist.psu.edu/122364.html
46 The algorithm works like this:
48 1. You have K keys, that you want to perfectly hash against some
51 2. Choose a number N larger than K. This is the number of
52 vertices in a graph G, and also the size of the resulting table G.
54 3. Pick two random hash functions f1, f2, that return values from 0..N-1.
56 4. Now, for all keys, you draw an edge between vertices f1(key) and f2(key)
57 of the graph G, and associate the desired hash value with that edge.
59 5. If G is cyclic, go back to step 2.
61 6. Assign values to each vertex such that, for each edge, you can add
62 the values for the two vertices and get the desired (hash) value
63 for that edge. This task is easy, because the graph is acyclic.
64 This is done by picking a vertex, and assigning it a value of 0.
65 Then do a depth-first search, assigning values to new vertices so that
68 7. f1, f2, and vertex values of G now make up a perfect hash function.
71 For simplicity, the implementation of the algorithm combines steps 5 and 6.
72 That is, we check for loops in G and assign the vertex values in one procedure.
73 If this procedure succeeds, G is acyclic and the vertex values are assigned.
74 If the procedure fails, G is cyclic, and we go back to step 2, replacing G
75 with a new graph, and thereby discarding the vertex values from the failed
78 from __future__ import absolute_import, division, print_function
86 from collections import defaultdict
87 from os.path import join
89 if sys.version_info[0] == 2:
90 from cStringIO import StringIO
92 from io import StringIO
104 Implements a graph with 'N' vertices. First, you connect the graph with
105 edges, which have a desired value associated. Then the vertex values
106 are assigned, which will fail if the graph is cyclic. The vertex values
107 are assigned such that the two values corresponding to an edge add up to
108 the desired edge value (mod N).
110 def __init__(self, N):
111 self.N = N # number of vertices
113 # maps a vertex number to the list of tuples (vertex, edge value)
114 # to which it is connected by edges.
115 self.adjacent = defaultdict(list)
117 def connect(self, vertex1, vertex2, edge_value):
119 Connect 'vertex1' and 'vertex2' with an edge, with associated
122 # Add vertices to each other's adjacent list
123 self.adjacent[vertex1].append((vertex2, edge_value))
124 self.adjacent[vertex2].append((vertex1, edge_value))
126 def assign_vertex_values(self):
128 Try to assign the vertex values, such that, for each edge, you can
129 add the values for the two vertices involved and get the desired
130 value for that edge, i.e. the desired hash key.
131 This will fail when the graph is cyclic.
133 This is done by a Depth-First Search of the graph. If the search
134 finds a vertex that was visited before, there's a loop and False is
135 returned immediately, i.e. the assignment is terminated.
136 On success (when the graph is acyclic) True is returned.
138 self.vertex_values = self.N * [-1] # -1 means unassigned
140 visited = self.N * [False]
142 # Loop over all vertices, taking unvisited ones as roots.
143 for root in range(self.N):
147 # explore tree starting at 'root'
148 self.vertex_values[root] = 0 # set arbitrarily to zero
150 # Stack of vertices to visit, a list of tuples (parent, vertex)
151 tovisit = [(None, root)]
153 parent, vertex = tovisit.pop()
154 visited[vertex] = True
156 # Loop over adjacent vertices, but skip the vertex we arrived
157 # here from the first time it is encountered.
159 for neighbor, edge_value in self.adjacent[vertex]:
160 if skip and neighbor == parent:
164 if visited[neighbor]:
165 # We visited here before, so the graph is cyclic.
168 tovisit.append((vertex, neighbor))
170 # Set new vertex's value to the desired edge value,
171 # minus the value of the vertex we came here from.
172 self.vertex_values[neighbor] = (
173 edge_value - self.vertex_values[vertex]) % self.N
175 # check if all vertices have a valid value
176 for vertex in range(self.N):
177 assert self.vertex_values[vertex] >= 0
179 # We got though, so the graph is acyclic,
180 # and all values are now assigned.
184 class StrSaltHash(object):
186 Random hash function generator.
187 Simple byte level hashing: each byte is multiplied to another byte from
188 a random string of characters, summed up, and finally modulo NG is
191 chars = string.ascii_letters + string.digits
193 def __init__(self, N):
197 def __call__(self, key):
198 # XXX: xkbcommon modification: make the salt length a power of 2
199 # so that the % operation in the hash is fast.
200 while len(self.salt) < max(len(key), 32): # add more salt as necessary
201 self.salt += random.choice(self.chars)
203 return sum(ord(self.salt[i]) * ord(c)
204 for i, c in enumerate(key)) % self.N
208 return sum(ord(T[i % $NS]) * ord(c) for i, c in enumerate(key)) % $NG
210 def perfect_hash(key):
211 return (G[hash_f(key, "$S1")] +
212 G[hash_f(key, "$S2")]) % $NG
215 class IntSaltHash(object):
217 Random hash function generator.
218 Simple byte level hashing, each byte is multiplied in sequence to a table
219 containing random numbers, summed tp, and finally modulo NG is taken.
221 def __init__(self, N):
225 def __call__(self, key):
226 while len(self.salt) < len(key): # add more salt as necessary
227 self.salt.append(random.randint(1, self.N - 1))
229 return sum(self.salt[i] * ord(c)
230 for i, c in enumerate(key)) % self.N
235 assert len(S1) == len(S2) == $NS
238 return sum(T[i % $NS] * ord(c) for i, c in enumerate(key)) % $NG
240 def perfect_hash(key):
241 return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % $NG
244 def builtin_template(Hash):
246 # =======================================================================
247 # ================= Python code for perfect hash function ===============
248 # =======================================================================
251 """ + Hash.template + """
252 # ============================ Sanity check =============================
257 for h, k in enumerate(K):
258 assert perfect_hash(k) == h
262 class TooManyInterationsError(Exception):
266 def generate_hash(keys, Hash=StrSaltHash):
268 Return hash functions f1 and f2, and G for a perfect minimal hash.
269 Input is an iterable of 'keys', whos indicies are the desired hash values.
270 'Hash' is a random hash function generator, that means Hash(N) returns a
271 returns a random hash function which returns hash values from 0..N-1.
273 if not isinstance(keys, (list, tuple)):
274 raise TypeError("list or tuple expected")
276 if NK != len(set(keys)):
277 raise ValueError("duplicate keys")
279 if not isinstance(key, str):
280 raise TypeError("key a not string: %r" % key)
281 if NK > 10000 and Hash == StrSaltHash:
283 WARNING: You have %d keys.
284 Using --hft=1 is likely to fail for so many keys.
285 Please use --hft=2 instead.
288 # the number of vertices in the graph G
291 print('NG = %d' % NG)
293 trial = 0 # Number of trial graphs so far
295 if (trial % trials) == 0: # trials failures, increase NG slightly
297 NG = max(NG + 1, int(1.05 * NG))
299 sys.stdout.write('\nGenerating graphs NG = %d ' % NG)
302 if NG > 100 * (NK + 1):
303 raise TooManyInterationsError("%d keys" % NK)
306 sys.stdout.write('.')
309 G = Graph(NG) # Create graph with NG vertices
310 f1 = Hash(NG) # Create 2 random hash functions
313 # Connect vertices given by the values of the two hash functions
314 # for each key. Associate the desired hash value with each edge.
315 for hashval, key in enumerate(keys):
316 G.connect(f1(key), f2(key), hashval)
318 # Try to assign the vertex values. This will fail when the graph
319 # is cyclic. But when the graph is acyclic it will succeed and we
320 # break out, because we're done.
321 if G.assign_vertex_values():
325 print('\nAcyclic graph found after %d trials.' % trial)
326 print('NG = %d' % NG)
328 # Sanity check the result by actually verifying that all the keys
329 # hash to the right value.
330 for hashval, key in enumerate(keys):
332 G.vertex_values[f1(key)] + G.vertex_values[f2(key)]
338 return f1, f2, G.vertex_values
341 class Format(object):
343 def __init__(self, width=76, indent=4, delimiter=', '):
346 self.delimiter = delimiter
348 def print_format(self):
349 print("Format options:")
350 for name in 'width', 'indent', 'delimiter':
351 print(' %s: %r' % (name, getattr(self, name)))
353 def __call__(self, data, quote=False):
354 if not isinstance(data, (list, tuple)):
357 lendel = len(self.delimiter)
360 for i, elt in enumerate(data):
361 last = bool(i == len(data) - 1)
363 s = ('"%s"' if quote else '%s') % elt
365 if pos + len(s) + lendel > self.width:
366 aux.write('\n' + (self.indent * ' '))
372 aux.write(self.delimiter)
375 return '\n'.join(l.rstrip() for l in aux.getvalue().split('\n'))
378 def generate_code(keys, Hash=StrSaltHash, template=None, options=None):
380 Takes a list of key value pairs and inserts the generated parameter
381 lists into the 'template' string. 'Hash' is the random hash function
382 generator, and the optional keywords are formating options.
383 The return value is the substituted code template.
385 f1, f2, G = generate_hash(keys, Hash)
387 assert f1.N == f2.N == len(G)
389 salt_len = len(f1.salt)
390 assert salt_len == len(f2.salt)
395 template = builtin_template(Hash)
400 fmt = Format(width=options.width, indent=options.indent,
401 delimiter=options.delimiter)
406 return string.Template(template).substitute(
413 K = fmt(list(keys), quote=True))
416 def read_table(filename, options):
418 Reads keys and desired hash value pairs from a file. If no column
419 for the hash value is specified, a sequence of hash values is generated,
420 from 0 to N-1, where N is the number of rows found in the file.
423 print("Reading table from file `%s' to extract keys." % filename)
427 sys.exit("Error: Could not open `%s' for reading." % filename)
432 print("Reader options:")
433 for name in 'comment', 'splitby', 'keycol':
434 print(' %s: %r' % (name, getattr(options, name)))
436 for n, line in enumerate(fi):
438 if not line or line.startswith(options.comment):
441 if line.count(options.comment): # strip content after comment
442 line = line.split(options.comment)[0].strip()
444 row = [col.strip() for col in line.split(options.splitby)]
447 key = row[options.keycol - 1]
449 sys.exit("%s:%d: Error: Cannot read key, not enough columns." %
457 exit("Error: no keys found in file `%s'." % filename)
462 def read_template(filename):
464 print("Reading template from file `%s'" % filename)
466 with open(filename, 'r') as fi:
469 sys.exit("Error: Could not open `%s' for reading." % filename)
473 tmpdir = tempfile.mkdtemp()
474 path = join(tmpdir, 't.py')
475 with open(path, 'w') as fo:
478 subprocess.check_call([sys.executable, path])
479 except subprocess.CalledProcessError as e:
480 raise AssertionError(e)
482 shutil.rmtree(tmpdir)
486 from optparse import OptionParser
488 usage = "usage: %prog [options] KEYS_FILE [TMPL_FILE]"
491 Generates code for perfect hash functions from
492 a file with keywords and a code template.
493 If no template file is provided, a small built-in Python template
494 is processed and the output code is written to stdout.
497 parser = OptionParser(usage = usage,
498 description = description,
500 version = "%prog: " + __version__)
502 parser.add_option("--delimiter",
505 help = "Delimiter for list items used in output, "
506 "the default delimiter is '%default'",
509 parser.add_option("--indent",
513 help = "Make INT spaces at the beginning of a "
514 "new line when generated list is wrapped. "
515 "Default is %default",
518 parser.add_option("--width",
522 help = "Maximal width of generated list when "
523 "wrapped. Default width is %default",
526 parser.add_option("--comment",
529 help = "STR is the character, or sequence of "
530 "characters, which marks the beginning "
531 "of a comment (which runs till "
532 "the end of the line), in the input "
534 "Default is '%default'",
537 parser.add_option("--splitby",
540 help = "STR is the character by which the columns "
541 "in the input KEYS_FILE are split. "
542 "Default is '%default'",
545 parser.add_option("--keycol",
549 help = "Specifies the column INT in the input "
550 "KEYS_FILE which contains the keys. "
551 "Default is %default, i.e. the first column.",
554 parser.add_option("--trials",
558 help = "Specifies the number of trials before "
559 "NG is increased. A small INT will give "
560 "compute faster, but the array G will be "
561 "large. A large INT will take longer to "
562 "compute but G will be smaller. "
563 "Default is %default",
566 parser.add_option("--hft",
570 help = "Hash function type INT. Possible values "
571 "are 1 (StrSaltHash) and 2 (IntSaltHash). "
572 "The default is %default",
575 parser.add_option("-e", "--execute",
576 action = "store_true",
577 help = "Execute the generated code within "
578 "the Python interpreter.")
580 parser.add_option("-o", "--output",
582 help = "Specify output FILE explicitly. "
583 "`-o std' means standard output. "
584 "`-o no' means no output. "
585 "By default, the file name is obtained "
586 "from the name of the template file by "
587 "substituting `tmpl' to `code'.",
590 parser.add_option("-v", "--verbose",
591 action = "store_true",
594 options, args = parser.parse_args()
596 if options.trials <= 0:
597 parser.error("trials before increasing N has to be larger than zero")
600 trials = options.trials
603 verbose = options.verbose
605 if len(args) not in (1, 2):
606 parser.error("incorrect number of arguments")
608 if len(args) == 2 and not args[1].count('tmpl'):
609 parser.error("template filename does not contain 'tmpl'")
613 elif options.hft == 2:
616 parser.error("Hash function %s not implemented." % options.hft)
618 # --------------------- end parsing and checking --------------
623 print("keys_file = %r" % keys_file)
625 keys = read_table(keys_file, options)
628 print("Number os keys: %d" % len(keys))
630 tmpl_file = args[1] if len(args) == 2 else None
633 print("tmpl_file = %r" % tmpl_file)
635 template = read_template(tmpl_file) if tmpl_file else None
638 outname = options.output
641 if 'tmpl' not in tmpl_file:
642 sys.exit("Hmm, template filename does not contain 'tmpl'")
643 outname = tmpl_file.replace('tmpl', 'code')
648 print("outname = %r\n" % outname)
651 outstream = sys.stdout
652 elif outname == 'no':
656 outstream = open(outname, 'w')
658 sys.exit("Error: Could not open `%s' for writing." % outname)
660 code = generate_code(keys, Hash, template, options)
662 if options.execute or template == builtin_template(Hash):
664 print('Executing code...\n')
668 outstream.write(code)
669 if not outname == 'std':
673 if __name__ == '__main__':