<commit_before>"""
hash_table.py

Python implementation of the very simple, fixed-array hash table
used for the audfprint fingerprinter.

2014-05-25 <NAME> <EMAIL>
"""

import numpy as np
import random
import cPickle as pickle
import os, gzip
import scipy.io
import math

# Current format version
HT_VERSION = 20140920
# Earliest acceptable version
HT_COMPAT_VERSION = 20140920

class HashTable(object):
    """
    Simple hash table for storing and retrieving fingerprint hashes.

    :usage:
       >>> ht = HashTable(size=2**10, depth=100)
       >>> ht.store('identifier', list_of_landmark_time_hash_pairs)
       >>> list_of_ids_tracks = ht.get_hits(hash)
    """

    def __init__(self, filename=None, hashbits=20, depth=100, maxtime=16384):
        """ allocate an empty hash table of the specified size """
        if filename is not None:
            self.params = self.load(filename)
        else:
            self.hashbits = hashbits
            self.depth = depth
            if maxtime != 2**int(round(math.log(maxtime)/math.log(2))):
                raise ValueError("maxtime must be a power of 2")
            self.maxtime = maxtime
            # allocate the big table
            size = 2**hashbits
            self.table = np.zeros((size, depth), dtype=np.uint32)
            # keep track of number of entries in each list
            self.counts = np.zeros(size, dtype=np.int32)
            # map names to IDs
            self.names = []
            # track number of hashes stored per id
            self.hashesperid = np.zeros(0, np.uint32)
            # Empty params
            self.params = {}
            # Record the current version
            self.ht_version = HT_VERSION
            # Mark as unsaved
            self.dirty = True

    def reset(self):
        """ Reset to empty state (but preserve parameters) """
        self.table[:,:] = 0
        self.counts[:] = 0
        self.names = []
        self.hashesperid.resize(0)
        self.dirty = True

    def store(self, name, timehashpairs):
        """ Store a list of hashes in the hash table
            associated with a particular name (or integer ID) and time.
        """
        if type(name) is str:
            # lookup name or assign new
            if name not in self.names:
                self.names.append(name)
                self.hashesperid = np.append(self.hashesperid, [0])
            id_ = self.names.index(name)
        else:
            # we were passed in a numerical id
            id_ = name
        # Now insert the hashes
        hashmask = (1 << self.hashbits) - 1
        #mxtime = self.maxtime
        timemask = self.maxtime - 1
        # Try sorting the pairs by hash value, for better locality in storing
        #sortedpairs = sorted(timehashpairs, key=lambda x:x[1])
        sortedpairs = timehashpairs
        # Tried making it an np array to permit vectorization, but slower...
        #sortedpairs = np.array(sorted(timehashpairs, key=lambda x:x[1]),
        #                       dtype=int)
        # Keep only the bottom part of the time value
        #sortedpairs[:,0] = sortedpairs[:,0] % self.maxtime
        # Keep only the bottom part of the hash value
        #sortedpairs[:,1] = sortedpairs[:,1] & hashmask
        idval = id_ * self.maxtime
        for time_, hash_ in sortedpairs:
            # How many already stored for this hash?
            count = self.counts[hash_]
            # Keep only the bottom part of the time value
            #time_ %= mxtime
            time_ &= timemask
            # Keep only the bottom part of the hash value
            hash_ &= hashmask
            # Mixin with ID
            val = (idval + time_) #.astype(np.uint32)
            if count < self.depth:
                # insert new val in next empty slot
                #slot = self.counts[hash_]
                self.table[hash_, count] = val
            else:
                # Choose a point at random
                slot = random.randint(0, count)
                # Only store if random slot wasn't beyond end
                if slot < self.depth:
                    self.table[hash_, slot] = val
            # Update record of number of vals in this bucket
            self.counts[hash_] = count + 1
        # Record how many hashes we (attempted to) save for this id
        self.hashesperid[id_] += len(timehashpairs)
        # Mark as unsaved
        self.dirty = True

    def get_entry(self, hash_):
        """ Return np.array of [id, time] entries
            associate with the given hash as rows.
        """
        vals = self.table[hash_, :min(self.depth, self.counts[hash_])]
        return np.c_[vals / self.maxtime, vals % self.maxtime].astype(np.int32)

    def get_hits(self, hashes):
        """ Return np.array of [id, delta_time, hash, time] rows
            associated with each element in hashes array of [time, hash] rows
        """
        # Allocate to largest possible number of hits
        hits = np.zeros((np.shape(hashes)[0]*self.depth, 4), np.int32)
        nhits = 0
        # Fill in
        for time_, hash_ in hashes:
            idstimes = self.get_entry(hash_)
            nids = np.shape(idstimes)[0]
            hitrows = nhits + np.arange(nids)
            hits[hitrows, 0] = idstimes[:, 0]
            hits[hitrows, 1] = idstimes[:, 1] - time_
            hits[hitrows, 2] = hash_
            hits[hitrows, 3] = time_
            nhits += nids
        # Discard the excess rows
        hits.resize( (nhits, 4) )
        return hits

    def save(self, name, params=None):
        """ Save hash table to file <name>,
            including optional addition params
        """
        # Merge in any provided params
        if params:
            for key in params:
                self.params[key] = params[key]
        with gzip.open(name, 'wb') as f:
            pickle.dump(self, f, pickle.HIGHEST_PROTOCOL)
        self.dirty = False
        print "Saved fprints for", len(self.names), "files", \
              "(", sum(self.counts), "hashes)", \
              "to", name

    def load(self, name):
        """ Read either pklz or mat-format hash table file """
        ext = os.path.splitext(name)[1]
        if ext == '.mat':
            params = self.load_matlab(name)
        else:
            params = self.load_pkl(name)
        print "Read fprints for", len(self.names), "files", \
              "(", sum(self.counts), "hashes)", \
              "from", name
        return params

    def load_pkl(self, name):
        """ Read hash table values from file <name>, return params """
        with gzip.open(name, 'rb') as f:
            temp = pickle.load(f)
        assert temp.ht_version >= HT_COMPAT_VERSION
        params = temp.params
        self.hashbits = temp.hashbits
        self.depth = temp.depth
        self.maxtime = temp.maxtime
        self.table = temp.table
        self.counts = temp.counts
        self.names = temp.names
        self.hashesperid = np.array(temp.hashesperid).astype(np.uint32)
        self.ht_version = temp.ht_version<commit_msg>Print the number and percentage of dropped hashes when saving dbase<commit_after>"""
hash_table.py

Python implementation of the very simple, fixed-array hash table
used for the audfprint fingerprinter.

2014-05-25 <NAME> <EMAIL>
"""

import numpy as np
import random
import cPickle as pickle
import os, gzip
import scipy.io
import math

# Current format version
HT_VERSION = 20140920
# Earliest acceptable version
HT_COMPAT_VERSION = 20140920

class HashTable(object):
    """
    Simple hash table for storing and retrieving fingerprint hashes.

    :usage:
       >>> ht = HashTable(size=2**10, depth=100)
       >>> ht.store('identifier', list_of_landmark_time_hash_pairs)
       >>> list_of_ids_tracks = ht.get_hits(hash)
    """

    def __init__(self, filename=None, hashbits=20, depth=100, maxtime=16384):
        """ allocate an empty hash table of the specified size """
        if filename is not None:
            self.params = self.load(filename)
        else:
            self.hashbits = hashbits
            self.depth = depth
            if maxtime != 2**int(round(math.log(maxtime)/math.log(2))):
                raise ValueError("maxtime must be a power of 2")
            self.maxtime = maxtime
            # allocate the big table
            size = 2**hashbits
            self.table = np.zeros((size, depth), dtype=np.uint32)
            # keep track of number of entries in each list
            self.counts = np.zeros(size, dtype=np.int32)
            # map names to IDs
            self.names = []
            # track number of hashes stored per id
            self.hashesperid = np.zeros(0, np.uint32)
            # Empty params
            self.params = {}
            # Record the current version
            self.ht_version = HT_VERSION
            # Mark as unsaved
            self.dirty = True

    def reset(self):
        """ Reset to empty state (but preserve parameters) """
        self.table[:,:] = 0
        self.counts[:] = 0
        self.names = []
        self.hashesperid.resize(0)
        self.dirty = True

    def store(self, name, timehashpairs):
        """ Store a list of hashes in the hash table
            associated with a particular name (or integer ID) and time.
        """
        if type(name) is str:
            # lookup name or assign new
            if name not in self.names:
                self.names.append(name)
                self.hashesperid = np.append(self.hashesperid, [0])
            id_ = self.names.index(name)
        else:
            # we were passed in a numerical id
            id_ = name
        # Now insert the hashes
        hashmask = (1 << self.hashbits) - 1
        #mxtime = self.maxtime
        timemask = self.maxtime - 1
        # Try sorting the pairs by hash value, for better locality in storing
        #sortedpairs = sorted(timehashpairs, key=lambda x:x[1])
        sortedpairs = timehashpairs
        # Tried making it an np array to permit vectorization, but slower...
        #sortedpairs = np.array(sorted(timehashpairs, key=lambda x:x[1]),
        #                       dtype=int)
        # Keep only the bottom part of the time value
        #sortedpairs[:,0] = sortedpairs[:,0] % self.maxtime
        # Keep only the bottom part of the hash value
        #sortedpairs[:,1] = sortedpairs[:,1] & hashmask
        idval = id_ * self.maxtime
        for time_, hash_ in sortedpairs:
            # How many already stored for this hash?
            count = self.counts[hash_]
            # Keep only the bottom part of the time value
            #time_ %= mxtime
            time_ &= timemask
            # Keep only the bottom part of the hash value
            hash_ &= hashmask
            # Mixin with ID
            val = (idval + time_) #.astype(np.uint32)
            if count < self.depth:
                # insert new val in next empty slot
                #slot = self.counts[hash_]
                self.table[hash_, count] = val
            else:
                # Choose a point at random
                slot = random.randint(0, count)
                # Only store if random slot wasn't beyond end
                if slot < self.depth:
                    self.table[hash_, slot] = val
            # Update record of number of vals in this bucket
            self.counts[hash_] = count + 1
        # Record how many hashes we (attempted to) save for this id
        self.hashesperid[id_] += len(timehashpairs)
        # Mark as unsaved
        self.dirty = True

    def get_entry(self, hash_):
        """ Return np.array of [id, time] entries
            associate with the given hash as rows.
        """
        vals = self.table[hash_, :min(self.depth, self.counts[hash_])]
        return np.c_[vals / self.maxtime, vals % self.maxtime].astype(np.int32)

    def get_hits(self, hashes):
        """ Return np.array of [id, delta_time, hash, time] rows
            associated with each element in hashes array of [time, hash] rows
        """
        # Allocate to largest possible number of hits
        hits = np.zeros((np.shape(hashes)[0]*self.depth, 4), np.int32)
        nhits = 0
        # Fill in
        for time_, hash_ in hashes:
            idstimes = self.get_entry(hash_)
            nids = np.shape(idstimes)[0]
            hitrows = nhits + np.arange(nids)
            hits[hitrows, 0] = idstimes[:, 0]
            hits[hitrows, 1] = idstimes[:, 1] - time_
            hits[hitrows, 2] = hash_
            hits[hitrows, 3] = time_
            nhits += nids
        # Discard the excess rows
        hits.resize( (nhits, 4) )
        return hits

    def save(self, name, params=None):
        """ Save hash table to file <name>,
            including optional addition params
        """
        # Merge in any provided params
        if params:
            for key in params:
                self.params[key] = params[key]
        with gzip.open(name, 'wb') as f:
            pickle.dump(self, f, pickle.HIGHEST_PROTOCOL)
        self.dirty = False
        nhashes = sum(self.counts)
        print "Saved fprints for", len(self.names), "files", \
              "(", nhashes, "hashes)", \
              "to", name
        # Report the proportion of dropped hashes (overfull table)
        dropped = nhashes - sum(np.minimum(self.depth, self.counts))
        print "Dropped hashes=", dropped, "(%.2f%%)" % (100.0*dropped/nhashes)

    def load(self, name):
        """ Read either pklz or mat-format hash table file """
        ext = os.path.splitext(name)[1]
        if ext == '.mat':
            params = self.load_matlab(name)
        else:
            params = self.load_pkl(name)
        print "Read fprints for", len(self.names), "files", \
              "(", sum(self.counts), "hashes)", \
              "from", name
        return params

    def load_pkl(self, name):
        """ Read hash table values from file <name>, return params """
        with gzip.open(name, 'rb') as f:
            temp = pickle.load(f)
        assert temp.ht_version >= HT_COMPAT_VERSION
        params = temp.params
        self.hashbits = temp.hashbits
        self.depth = temp.depth
        self.maxtime = temp.maxtime
        self.table = temp.table
        self.counts = temp.counts
        self.names = temp.names
        self.hashesperid = np.array(temp.hashesperid).astype(np.uint32)
        self.ht_version = temp.ht_version
{'fraction_non_alphanumeric': 0.09967399597697163, 'fraction_numerical': 0.012277172782132206, 'mean_word_length': 1.8342834676626696, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1247069', 'n_tokens_mistral': 4370, 'n_tokens_neox': 4226, 'n_words': 1295}