sawine@2
|
1 |
"""
|
sawine@2
|
2 |
Name: perfect_hashing - applies the two-level scheme to build a perfect hash function
|
sawine@2
|
3 |
|
sawine@2
|
4 |
Description: Perfect Hashing builds a perfect hash function.
|
sawine@2
|
5 |
|
sawine@2
|
6 |
Author: Eugen Sawin <sawine@me73.com>
|
sawine@2
|
7 |
"""
|
sawine@2
|
8 |
|
sawine@2
|
9 |
def main():
|
sawine@2
|
10 |
args = parse_args()
|
sawine@2
|
11 |
N = args.n
|
sawine@2
|
12 |
k = args.k
|
sawine@2
|
13 |
s = [int(e) for e in args.s.split(',')]
|
sawine@2
|
14 |
perfect_hashing(N, len(s), k, s)
|
sawine@2
|
15 |
|
sawine@2
|
16 |
def hkx(N, n, k, x):
|
sawine@2
|
17 |
return ((k*x) % N) % n
|
sawine@2
|
18 |
|
sawine@2
|
19 |
def find_ki(N, mi, Wi):
|
sawine@2
|
20 |
def injective():
|
sawine@2
|
21 |
hx = []
|
sawine@2
|
22 |
for x in Wi:
|
sawine@2
|
23 |
thx = hkx(N, mi, ki, x)
|
sawine@2
|
24 |
if thx in hx:
|
sawine@2
|
25 |
return False
|
sawine@2
|
26 |
else:
|
sawine@2
|
27 |
hx.append(thx)
|
sawine@2
|
28 |
return True
|
sawine@2
|
29 |
|
sawine@2
|
30 |
ki = 1
|
sawine@2
|
31 |
while not injective():
|
sawine@2
|
32 |
ki += 1
|
sawine@2
|
33 |
return ki
|
sawine@2
|
34 |
|
sawine@2
|
35 |
def perfect_hashing(N, n, k, xi):
|
sawine@2
|
36 |
hx = {}
|
sawine@2
|
37 |
for x in xi:
|
sawine@2
|
38 |
hx[(k, x)] = hkx(N, n, k, x)
|
sawine@2
|
39 |
print "h%i(%i) = (%i * %i mod %i) mod %i = %i" % (k, x, k, x, N, n, hx[(k,x)])
|
sawine@2
|
40 |
ml = []
|
sawine@2
|
41 |
sl = []
|
sawine@2
|
42 |
kl = []
|
sawine@2
|
43 |
for i in xrange(n):
|
sawine@2
|
44 |
Wi = [thx[0][1] for thx in hx.iteritems() if thx[1] == i]
|
sawine@2
|
45 |
bi = len(Wi)
|
sawine@2
|
46 |
mi = 2 * bi * (bi - 1) + 1
|
sawine@2
|
47 |
si = sum(ml)
|
sawine@2
|
48 |
ki = find_ki(N, mi, Wi)
|
sawine@2
|
49 |
ml.append(mi)
|
sawine@2
|
50 |
sl.append(si)
|
sawine@2
|
51 |
kl.append(ki)
|
sawine@2
|
52 |
print "\nW%i = " % i, Wi
|
sawine@2
|
53 |
print "=> b%i = %i" % (i, bi), "m%i = %i" % (i, mi), "s%i = %i" % (i, si), "k%i = %i" % (i, ki)
|
sawine@2
|
54 |
if bi > 1:
|
sawine@2
|
55 |
print "=> hk%i = (%i * x mod %i) mod %i" % (i, ki, N, mi)
|
sawine@2
|
56 |
|
sawine@2
|
57 |
print
|
sawine@2
|
58 |
for x in xi:
|
sawine@2
|
59 |
i = hx[(k, x)]
|
sawine@2
|
60 |
posx = sl[i] + hkx(N, ml[i], kl[i], x)
|
sawine@2
|
61 |
print "x = %i => pos(%i) = %i" % (x, x, posx)
|
sawine@2
|
62 |
|
sawine@2
|
63 |
from argparse import ArgumentParser
|
sawine@2
|
64 |
|
sawine@2
|
65 |
def parse_args():
|
sawine@2
|
66 |
parser = ArgumentParser(description='Builds a perfect hash function.')
|
sawine@2
|
67 |
parser.add_argument('n', type=int, help='size of the universe U')
|
sawine@2
|
68 |
parser.add_argument('k', type=int, help='parameter k of the hash function')
|
sawine@2
|
69 |
parser.add_argument('s', help='comma-separated values defining the given set S')
|
sawine@2
|
70 |
return parser.parse_args()
|
sawine@2
|
71 |
|
sawine@2
|
72 |
if __name__ == "__main__":
|
sawine@2
|
73 |
main()
|