# coding=utf-8

"""This is an initial implementation of LSH following the post from eventbrite.com blog

https://engineering.eventbrite.com/multi-index-locality-sensitive-hashing-for-fun-and-profit/

"""

import re
import hashlib
import struct

repeated_char_pattern = re.compile(r"(.)\1{1,}", re.DOTALL)

def tokenize_sentence(sentence):
    for word in sentence.split(' '):
        # for full in nltk.tokenize.sent_tokenize(sentence):
        # for word in nltk.tokenize.word_tokenize(full):
        word = word.lower()
        word = _replace_repeated_chars(word)
        word = word.strip('\'"!?,.')
        yield word


def _replace_repeated_chars(sentence):
    """look for 2 or more repetitions of character and replace with the character
    itself

    """
    return repeated_char_pattern.sub(r"\1\1", sentence)


def _minHash_similarity(hashesA, hashesB, N):
    """ Check how many of the hashes in the two groups are equal, that means the same token
    was found in the two sentences

        A higher result, more similarity between sentences

        O(N M^2)
    """
    count = 0
    count = sum(1 for i in range(N) if hashesA[i] == hashesB[i])

    return count/N


def _hamming_distance(bitsA, bitsB, N):
    """Hamming distance returns the number of equals bits"""
    X = bin( bitsA ^ bitsB)[2:]
    X = X.zfill(N)  # pad with leading zero to match the N bits
    count = 0

    return sum(1 for i in range(N) if int(X[i]) == 1)


def _generate_hash(seed, token):
    """ Calculate the hash given a seed plus token, then the digest is unpacked
    and converted to int, the final hash is just 4 from the first 4 chars of the digest. Any
    consistent hashing function should be enough

        :returns: Integer of the partial digest
    """
    return struct.unpack(
        'i', hashlib.md5('{0}${1}'.format(seed, token).encode('utf-8')).digest()[0:4])[0]


def minHash(tokens, N):
    """ For each token, will generate N hashes, then get the minimal ones
    and returns it.

    """
    final_hashes = list()

    for seed in range(N):
        hash_list = [_generate_hash(seed, token) for token in tokens]
        final_hashes.append(min(hash_list))
    return final_hashes


def bitsimilarity(bitsA, bitsB, N):
    """Returns the percent of similarity (using Hamming distance)

       O(M^2)

    """
    distance = _hamming_distance(bitsA, bitsB)
    similarity = 1 - distance / N
    return similarity


def bitsampling(hashes, N):
    """ Instead of storing the minHash, we can do better just storing the least significant bit
    of each hash

        returns a bit vector with the least significat bits
    """
    bits = 0

    for i in range(N):
        bits = (bits << 1) | (hashes[i] & 1)

    return bits


def split_chunks(bits, N, chunk_size):
    """Split the bits in groups of chunk bits"""
    bit_vector = bin(bits << (N % chunk_size))[2:]  # pad to left with zero to match the chunk multiple bits
    chunks = []

    for i in range(0, N, chunk_size):
        chunks.append(int(bit_vector[i:i+chunk_size], 2))
    return chunks


def generate_close_chunks(chunk):
    """Generates close chunks, numbers with one bit difference with original chunk

        returns list of chunks

    """
    size = len(bin(chunk)[2:])
    close_chunks = []
    for i in range(size):
        # apply a XOR operations with a zero-vector with just one bit as 1, the bit is
        # moved each iteration
        close_chunks.append(chunk ^ (1 << i))
    return close_chunks


class LSHTable(object):
    def __init__(self, hash_size, chunk_size):
        """
            :param hash_size: the number of different hashes to be generated per token and
                also the number of bits in the bitsampled string
            :param chunk_size: size for the chunk,
        """
        self._hash_size = hash_size
        self._chunk_size = chunk_size

        self._table = [{} for i in range(self._chunk_size)]

    def bitvector_from_tokens(self, tokens):
        hashes = minHash(tokens, N=self._hash_size)
        return bitsampling(hashes, N=self._hash_size)

    def add(self, bitvector):
        chunks = split_chunks(bitvector, self._hash_size, self._chunk_size)
        for i, c in enumerate(chunks):
            if not i in self._table:
                self._table[i] = {}
            if not chunks[i] in self._table[i]:
                self._table[i][chunks[i]] = [bitvector]

    def lookup(self, bitvector):
        chunks = split_chunks(bitvector, self._hash_size, self._chunk_size)
        matches = []
        for i, chunk in enumerate(chunks):
            close_chunks = generate_close_chunks(chunk)
            for close in close_chunks:
                if close in self._table[i]:
                    matches.extend(self._table[i][close])
        return matches

@@ -3912,16 +3912,23 @@
 n range(
+pow(2, 
 self._ch
@@ -3936,16 +3936,17 @@
 nk_size)
+)
 %5D%0A%0A    d

Fix bad hashtable initialization