import time
import struct
import hashlib
filename = "test.pdf"
filename2 = "Python_for_Data_Analysis.pdf"
file_dump = open(filename, "rb")
file_dump2 = open(filename2, "rb")
file_dump
<open file 'test.pdf', mode 'rb' at 0x105b18e40>
file_dump2
<open file 'Python_for_Data_Analysis.pdf', mode 'rb' at 0x105b18f60>
def byte_reader(memory_dump, number_bytes):
'''
Read the #number_byte of bytes
'''
byte = memory_dump.read(number_bytes)
return byte
byte_reader(file_dump, 32)
'%PDF-1.6\r%\xe2\xe3\xcf\xd3\r\n10792 0 obj\r<</F'
byte_reader(file_dump2, 32)
'%PDF-1.6\r%\xe2\xe3\xcf\xd3\r\n10792 0 obj\r<</F'
def hashing_byte_reader(memory_dump, number_bytes):
'''
Read the bytes and return MD5
'''
byte = memory_dump.read(number_bytes)
m = hashlib.md5()
m.update(byte)
hash_byte = m.hexdigest()
return byte, hash_byte
fd = open(filename, "rb")
def gen_hashes(fd):
for element in xrange(0,100):
buffer, hash_result = hashing_byte_reader(fd, 16)
yield hash_result
hash1 = gen_hashes(fd)
hash1_set = set(hash1)
hash1_set
set(['d2d56fd6da70f634347068f4db84fd5b', '90d034c5f6b05e94d7d799f14fe008d6', 'c84ad22a67d405d3823cef724ebd09bb', 'f33ecc1048976f08009750a95a318146', '01c8a4c01983f3af14a2eb7cf56e1bfc', 'ef4f324d42351339e11655155a09711a', '6b05444eb6eef6878494daaf65c34801', '5b705643470ded220a51274c6e5dd184', 'a39529456ddd26c9a8b3498583cd0889', 'da470fa7ab90dd8081aefc128d87d55d', 'f0a81008577ddbccdb5fb950c5c84959', 'd308ca9690aef4b9d659fec38b460551', '3899571e339a3817ce80529585e0c095', '96b601c7465be7f73aacff0453dc8127', 'f6428164ad17b668c0bda8247d7733c9', '47fc0a743b51219894caf4d7d1b78923', '29039d773418a2255bd966f83f683141', '4aa1492929f36d610a454e0777b68104', '7e1d1746e33300b7ead456e3693914c7', '44499548fa3bd4d00009f0653c5bfd42', '960bee379c4152682b635c825b8cea73', '147b54a5653742c1107a7a1555229c78', '59070bfb1d13ee62d649e02a3936ada5', '9ca305c8014c0981f889ae618ab83579', '1f8a64afa5d871bfacfd5129e9f7c466', 'c2e1ee6c4620da8640e41db1e078e39d', 'a868ca612988c1915c536be93cad4b62', '6b3bc1820f98c31f4789d6832b43c434', '5802d549b2b7325a937f0829929cab97', 'f00aaccfe86291d7588668ea14bb0d47', '7cfd41aa2dd63e40971265eb641f67ee', '2f69efcf2018bd46710818e674e417a6', 'dea321def6cbfab92627848a15a99633', '6dc5cd21bb89f37e2906b07b5eef5e4c', '719d18b744ec9693b79b7e1a689f7e0c', 'a46fc4e9839d3d46a100f302339aa6f9', 'c82f7ebba78bf800f56cee1d6bf952a2', '1ab32e97bd34a104e442ecb62c45fc05', '814bf9f9da4b353be99c63311a689c4d', '704b6e7d23b929eb75942c5f80f1e4ef', '04b3de90f83e9fca6df79ff129ce8d02', 'fec0e0b7e59634a90c2a37f16d2dc884', '4feb3c02274b870e48ae0d8caa1361ec', '0a5f0f597ccb1407539949b3c6f50e21', '32434bbd3c380b33891ff11be769e546', 'b546c6adf4cfcc7028a9cf6bd21fbd97', 'f1d5d5ea10c80c338c23f092fc0fb2fc', '05953d13417244e3420b96d62ab136cf', 'd584c3eddd55e126e97fab53a17d8c9d', '6a440fb77cec0897a5e9ee31b3cef22c', '95d87048d42362f9a5c44e07160a022f', '0e8fd03942482758fba02c135a8e3552', 'e763e5b353053732f064206bc9b05150', '1078ba9185d1316e41c40be179f55977', '092cead87c44b50f962d96f29c39243d', '2f57d09601bc7130eb1f232e22acdac4', '451990b54b46a3c72e021652ab6eab85', '2d36e9011a017cf20aee5827aae1cc27', '13b585054d78e7158e75ff4fe3746cb4', '7d0875fe9c075242a1f62fe27d18beab', '624c89946174f0fcd5370016b034edfe', 'c9c7bec627534454e23ad02457d44ed7', 'f000515b3bf48a40990d47dc8c859e4c', '83e4dc3aa8e97d7e24967f3b08344598', '82b06352b134928a9e0605134d00ac55', '6e0387af67f5ab5d9c77cfdfcef4be49', 'ee6213d8e2e0ae965f8acb4ed09cc1a6', '2f3f715f0e0aebdf00c6841bb5ec0d45', '8e73754f6b8c7f043df01fcb36075dc7', '62c08febfa671faf0b190e9a2cd9a1c2', 'e8d4c9a52ae5cb55a6bd1b3e14133806', '145c7e76da196606dab538f0b95e8537', '76fc76acd72ecaf23a9f4d9831592949', '10743ed1c425da349a56d3295f04c0cb', '431fa8ec94ffe04b4a453e323c7b75c6', '1791077b68730038335042cb1826b4ab', '6d0600b3017097e1c7f9efec08d44ac1', 'df049dd9f5b2274b6482fa7eefd4bc93', 'ae5901b746400d3f3d117bd0892306f3', '5d333f2e5d8abda015ff3dd2f7e226c9', 'cc49ca1eb52fbc7863ac51063b63e083', '825312cdc69fe25e4a9e9f8bff5d3332', 'f43f578c0b5b2728ff99ca9ab26092b4', 'a9b3177a5fff60ab6449370d18dd85f8', '6df65ce3740acf25fa55bac05854820b', '74426cec1f6ee2fa080c2fd964b74109', 'c782358327e79f56cabad5e0fc3695e3', '2545c07a6c092a7e05bc83f07c6cd299', '9bad6f098858368055dd6ea67813bb2e', '3e4f277d07c306cddb9c17f8548ead9d', '6b552a3366ac67648049ffde4e91cd36', '8dc8f9e29289f8254996c9b24d96e53a', '2eeffe17b18e1305a884c796cc8d1d8c', 'bc831227877e8da3c86ac6fe00b3325c', '4519d11616dbe54f278253ba81aa2e5e', 'b77918e8be6887ca18458b3af9f61d94', 'b97255812da987c2e053ada647da9b62', '1dddd27c4cdbc9cab6bc392b10fb8af6', 'b722c62d18d989b7d59523a99b9d9a61', 'ad28bbf73a1cf04ccd325b61c44af131'])
fd = open(filename2, "rb")
def gen_hashes(fd):
for element in xrange(0,100):
buffer, hash_result = hashing_byte_reader(fd, 16)
yield hash_result
hash2 = gen_hashes(fd)
hash2_set = set(hash2)
hash2_set
set(['d2d56fd6da70f634347068f4db84fd5b', '90d034c5f6b05e94d7d799f14fe008d6', 'c84ad22a67d405d3823cef724ebd09bb', 'f33ecc1048976f08009750a95a318146', '01c8a4c01983f3af14a2eb7cf56e1bfc', 'ef4f324d42351339e11655155a09711a', '6b05444eb6eef6878494daaf65c34801', '5b705643470ded220a51274c6e5dd184', 'a39529456ddd26c9a8b3498583cd0889', 'da470fa7ab90dd8081aefc128d87d55d', 'f0a81008577ddbccdb5fb950c5c84959', 'd308ca9690aef4b9d659fec38b460551', '3899571e339a3817ce80529585e0c095', '96b601c7465be7f73aacff0453dc8127', 'f6428164ad17b668c0bda8247d7733c9', '47fc0a743b51219894caf4d7d1b78923', '29039d773418a2255bd966f83f683141', '4aa1492929f36d610a454e0777b68104', '7e1d1746e33300b7ead456e3693914c7', '44499548fa3bd4d00009f0653c5bfd42', '960bee379c4152682b635c825b8cea73', '147b54a5653742c1107a7a1555229c78', '59070bfb1d13ee62d649e02a3936ada5', '9ca305c8014c0981f889ae618ab83579', '1f8a64afa5d871bfacfd5129e9f7c466', 'c2e1ee6c4620da8640e41db1e078e39d', 'a868ca612988c1915c536be93cad4b62', '6b3bc1820f98c31f4789d6832b43c434', '5802d549b2b7325a937f0829929cab97', 'f00aaccfe86291d7588668ea14bb0d47', '7cfd41aa2dd63e40971265eb641f67ee', '2f69efcf2018bd46710818e674e417a6', 'dea321def6cbfab92627848a15a99633', '6dc5cd21bb89f37e2906b07b5eef5e4c', '719d18b744ec9693b79b7e1a689f7e0c', 'a46fc4e9839d3d46a100f302339aa6f9', 'c82f7ebba78bf800f56cee1d6bf952a2', '1ab32e97bd34a104e442ecb62c45fc05', '814bf9f9da4b353be99c63311a689c4d', '704b6e7d23b929eb75942c5f80f1e4ef', '04b3de90f83e9fca6df79ff129ce8d02', 'fec0e0b7e59634a90c2a37f16d2dc884', '4feb3c02274b870e48ae0d8caa1361ec', '0a5f0f597ccb1407539949b3c6f50e21', '32434bbd3c380b33891ff11be769e546', 'b546c6adf4cfcc7028a9cf6bd21fbd97', 'f1d5d5ea10c80c338c23f092fc0fb2fc', '05953d13417244e3420b96d62ab136cf', 'd584c3eddd55e126e97fab53a17d8c9d', '6a440fb77cec0897a5e9ee31b3cef22c', '95d87048d42362f9a5c44e07160a022f', '0e8fd03942482758fba02c135a8e3552', 'e763e5b353053732f064206bc9b05150', '1078ba9185d1316e41c40be179f55977', '092cead87c44b50f962d96f29c39243d', '2f57d09601bc7130eb1f232e22acdac4', '451990b54b46a3c72e021652ab6eab85', '2d36e9011a017cf20aee5827aae1cc27', '13b585054d78e7158e75ff4fe3746cb4', '7d0875fe9c075242a1f62fe27d18beab', '624c89946174f0fcd5370016b034edfe', 'c9c7bec627534454e23ad02457d44ed7', 'f000515b3bf48a40990d47dc8c859e4c', '83e4dc3aa8e97d7e24967f3b08344598', '82b06352b134928a9e0605134d00ac55', '6e0387af67f5ab5d9c77cfdfcef4be49', 'ee6213d8e2e0ae965f8acb4ed09cc1a6', '2f3f715f0e0aebdf00c6841bb5ec0d45', '8e73754f6b8c7f043df01fcb36075dc7', '62c08febfa671faf0b190e9a2cd9a1c2', 'e8d4c9a52ae5cb55a6bd1b3e14133806', '145c7e76da196606dab538f0b95e8537', '76fc76acd72ecaf23a9f4d9831592949', '10743ed1c425da349a56d3295f04c0cb', '431fa8ec94ffe04b4a453e323c7b75c6', '1791077b68730038335042cb1826b4ab', '6d0600b3017097e1c7f9efec08d44ac1', 'df049dd9f5b2274b6482fa7eefd4bc93', 'ae5901b746400d3f3d117bd0892306f3', '5d333f2e5d8abda015ff3dd2f7e226c9', 'cc49ca1eb52fbc7863ac51063b63e083', '825312cdc69fe25e4a9e9f8bff5d3332', 'f43f578c0b5b2728ff99ca9ab26092b4', 'a9b3177a5fff60ab6449370d18dd85f8', '6df65ce3740acf25fa55bac05854820b', '74426cec1f6ee2fa080c2fd964b74109', 'c782358327e79f56cabad5e0fc3695e3', '2545c07a6c092a7e05bc83f07c6cd299', '9bad6f098858368055dd6ea67813bb2e', '3e4f277d07c306cddb9c17f8548ead9d', '6b552a3366ac67648049ffde4e91cd36', '8dc8f9e29289f8254996c9b24d96e53a', '2eeffe17b18e1305a884c796cc8d1d8c', 'bc831227877e8da3c86ac6fe00b3325c', '4519d11616dbe54f278253ba81aa2e5e', 'b77918e8be6887ca18458b3af9f61d94', 'b97255812da987c2e053ada647da9b62', '1dddd27c4cdbc9cab6bc392b10fb8af6', 'b722c62d18d989b7d59523a99b9d9a61', 'ad28bbf73a1cf04ccd325b61c44af131'])
file_similarity_score = hash2_set.intersection(hash1_set)
len(file_similarity_score)
100
fd = open(filename, "rb")
i = 0
from hashlib import sha1
from math import ceil
from math import log
from math import pow
from sys import getsizeof
from Interface import Interface
from bitarray import bitarray
import sys
def get_SHA1_bin(word):
"""
Returns the SHA1 hash of any string
"""
hash_s = sha1()
hash_s.update(word)
return bin(long(hash_s.hexdigest(),16))[2:].zfill(160)
def get_index(binString,endIndex=160):
"""
Returns the position of the first 1 bit
from the left in the word until endIndex
"""
res = -1
try:
res = binString.index('1')+1
except(ValueError):
res = endIndex
return res
class Sketch(Interface):
"""
Class implements a Hyperloglog probabilistic data structure
"""
def __init__(self,max_cardinality):
"""Implementes a Hash Sketch
maxCardinality
this Sketch is able to count cardinalities up to cardinality *maxCardinality*
"""
self.__maxCardinality=maxCardinality
self.__maxIndex = 0
self.__bitarray = bitarray(160)
self.__bitarray.setall(False)
self.__name = "Sketch"
def getName(self):
"""
Returns name
"""
return self.__name
def add(self,item):
"""
Adds the item to the Hash Sketch
"""
binword = get_SHA1_bin(item)
index = get_index(binword)
self.__bitarray[index]= True
self.__maxIndex = max(self.__maxIndex,index)
def get_raw_estimate(self):
"""
Returns the raw estimate of sets cardinality
"""
return self.__maxIndex
def get_number_estimate(self):
"""
Returns Linear Count estimate of the sets cardinality
"""
zerobits = self.__bitarray.count(False)
fraction = float(zerobits)/len(self.__bitarray)
res = -len(self.__bitarray)*log(fraction)
return res
class SuperLogLogSketch(Interface):
"""
Implements the improved version of LogLog Sketches, SuperLogLog Sketches
"""
def __init__(self, maxCardinality, error_rate):
"""
Implementes a SuperLogLog Sketch
*maxCardinality
this Sketch is able to count cardinalities up to cardinality *maxCardinality*
error_rate
the error_rate of the sketch when calculating the cardinality of the set
"""
if not (0 < error_rate < 1):
raise ValueError("Error_Rate must be between 0 and 1.")
if not maxCardinality > 0:
raise ValueError("maxCardinality must be > 0")
self._maxCardinality = maxCardinality
self._k = int(round(log(pow(1.05/error_rate,2),2)))
self._bucketNumber = 1<<self._k
self._bucketSize = int(ceil(log(log(float(self._maxCardinality)/self._bucketNumber+3,2),2)))
self._B = 1 << self._bucketSize
self.__name = "SuperLogLogSketch"
self._bucketList = [0 for _ in xrange(self._bucketNumber)]
def getName(self):
"""
Returns name
"""
return self.__name
def getNumberEstimate(self,beta = 0.7):
"""
Returns the estimate of the cardinality
Arguments:
beta= Used to get the truncated list. Keep only the *beta* smallest values and discard the rest
"""
newList = sorted(self._bucketList)
lastIndex = ceil(len(newList)*beta)
nbeta = lastIndex/len(newList)
newList = newList[:int(lastIndex)]
m = self._bucketNumber*nbeta
e = 0.39701 * m*2**((1.0/m)*sum(newList))
return e
def _restrition_rule(self,unrestricted_value):
return min(unrestricted_value,self._B)
def add(self,item):
"""
Adds the item to the LogLog Sketch
"""
binword = get_SHA1_bin(item)
index = int(binword[:self._k],2)
self._bucketList[index] = self._restrition_rule(max(self._bucketList[index],getIndex(binword[self._k:],160-self._k)))
class LogLogSketch(Interface):
"""
Implements a LogLog Sketch
"""
def __init__(self, maxCardinality, error_rate):
"""
Implementes a LogLog Sketch
*maxCardinality
this Sketch is able to count cardinalities up to cardinality *maxCardinality*
error_rate
the error_rate of the sketch when calculating the cardinality of the set
"""
if not (0 < error_rate < 1):
raise ValueError("Error_Rate must be between 0 and 1.")
if not maxCardinality > 0:
raise ValueError("maxCardinality must be > 0")
self._maxCardinality = maxCardinality
self._k = int(round(log(pow(1.30/error_rate,2),2)))
self._bucketNumber = 1<<self._k
self._bucketSize = self._wordSizeCalculator(self._maxCardinality)
self._bucketList =[bitarray(self._bucketSize) for _ in xrange(self._bucketNumber)]
for barray in self._bucketList:
barray.setall(False)
self.__name = "LogLogSketch"
def getName(self):
"""
Returns name
"""
return self.__name
def add(self,item):
"""
Adds the item to the LogLog Sketch
"""
binword = get_SHA1_bin(item)
pos = int(binword[:self._k],2)
aux = getIndex(binword[self._k:],160-self._k)
index = min(aux,(1<<self._bucketSize)-1)
newValue = max(int(self._bucketList[pos].to01(),2),index)
self._bucketList[pos] = bitarray(bin(newValue)[2:])
def getNumberEstimate(self):
"""
Returns the estimate of the cardinality
"""
m = self._bucketNumber
e = 0.39701 * m*2**((1.0/m)*sum([int(x.to01(),2) for x in self._bucketList]))
return e
def __sizeof__(self):
return self._bucketNumber* self._bucketSize
def _wordSizeCalculator(self,Nmax):
"""
Estimates the size of the memory Units, using the maximum cardinality as an argument
"""
return int(ceil(log(log(Nmax,2),2)))
class HyperLogLogSketch(Interface):
"""
Implements a HyperLogLog Sketch
"""
def __init__(self, maxCardinality, error_rate):
"""Implementes a HyperLogLog Sketch
*maxCardinality
this Sketch is able to count cardinalities up to cardinality *maxCardinality*
error_rate
the error_rate of the sketch when calculating the cardinality of the set
"""
self.__ALPHA16=0.673
self.__ALPHA32=0.697
self.__ALPHA64=0.709
if not (0 < error_rate < 1):
raise ValueError("Error_Rate must be between 0 and 1.")
if not maxCardinality > 0:
raise ValueError("maxCardinality must be > 0")
self._maxCardinality = maxCardinality
self._k = int(round(log(pow(1.04/error_rate,2),2)))
self._bucketNumber = 1<<self._k
self._bucketSize = self._wordSizeCalculator(self._maxCardinality)
self._bucketList =[0 for _ in xrange(self._bucketNumber)]
self.__name = "HyperLogLogSketch"
self._alpha = self.__getALPHA(self._bucketNumber)
def __getALPHA(self,m):
if m <=16:
return self.__ALPHA16
elif m<=32:
return self.__ALPHA32
elif m<=64:
return self.__ALPHA64
else:
return 0.7213/(1+1.079/float(m))
def getName(self):
return self.__name
def add(self,item):
"""
Adds the item to the LogLog Sketch
"""
binword = get_SHA1_bin(item)
pos = int(binword[:self._k],2)
#Retrives the position of leftmost 1
aux = get_index(binword[self._k:],160-self._k)
# Sets its own register value to maximum value seen so far
self._bucketList[pos] = max(aux,self._bucketList[pos])
def getNumberEstimate(self):
"""
Returns the estimate of the cardinality
"""
m = self._bucketNumber
raw_e = self._alpha*pow(m,2)/sum([pow(2,-x) for x in self._bucketList])
if raw_e <= 5/2.0*m:
v = self._bucketList.count(0)
if v!=0:
return m*log(m/float(v),2)
else:
return raw_e
elif raw_e <= 1/30.0*2**160:
return raw_e
else:
return -2**160*log(1-raw_e/2.0**160,2)
def join(self,*HyperLogLogList):
"""
Joins the HyperLogLog Sketches passed as argument, with this HyperLogLog Sketch
"""
if HyperLogLogList:
for sketch in HyperLogLogList:
if type(sketch)!=type(self):
raise TypeError("all arguments must be HyperLogLog Sketches")
bucketLists = zip(self._bucketList,*[sketch._bucketList for sketch in HyperLogLogList])
self._bucketList = map(max,bucketLists)
else:
raise TypeError("join expected at least 1 argument, got 0")
def exclusion(self, something):
pass
def __sizeof__(self):
return self._bucketNumber* self._bucketSize
def _wordSizeCalculator(self,Nmax):
"""
Estimates the size of the memory Units, using the maximum cardinality as an argument
"""
return int(ceil(log(log(Nmax,2),2)))
def bs(number):
"""
Returns the binary representation of the number given as argument
"""
return str(number) if number<=1 else bs(number>>1) + str(number&1)
######################################
#
# make a bunch of hyperloglog sketches
#
######################################
a = HyperLogLogSketch(2000000,0.05)
b = HyperLogLogSketch(2000000,0.05)
c = HyperLogLogSketch(2000000,0.05)
for i in xrange(100000):
a.add(str(i))
for i in xrange(1500):
b.add(str(i))
for i in xrange(100000,200000):
c.add(str(i))
#print sys.getsizeof(a)
print "1-100,000 random items put in set - Estimated count: ", a.getNumberEstimate()
print "1500 random items put in set - Estimated count: ", b.getNumberEstimate()
print "100,000-200,000 random items put in set - Estimated count: ", c.getNumberEstimate()
print "Making a joined set with items numbered 1-100k and 100k-200k", c.join(a,a)
print "Here is the joined count: ", c.getNumberEstimate()
1-100,000 random items put in set - Estimated count: 99402.5499907 1500 random items put in set - Estimated count: 1530.86693324 100,000-200,000 random items put in set - Estimated count: 109661.677392 Making a joined set with items numbered 1-100k and 100k-200k None Here is the joined count: 208895.418605
"""
Demo to hash a bunch of blocks upto 1,000,000 blocks of 32 bytes blocks into Hyperloglog
"""
hash_store = HyperLogLogSketch(2000000,0.05)
fd = open("/Users/antigen/Downloads/Python_for_Data_Analysis.pdf", "rb")
i=0
for element in xrange(0,1000000):
buffer, hash_result = hashing_byte_reader(fd, 16)
hash_store.add(hash_result)
hash_store.getNumberEstimate()
826962.62820048362
#TODO: Need to figure out the intersection of two hash_stores