A = ("a", "rose", "is", "a", "rose", "is", "a", "rose")
B = ("a", "rose", "is", "a", "flower", "which", "is", "a", "rose")

Shingle = Tuple[str]

def doc_to_shingle_bag(doc: List[str], w:int) -> Dict[Shingle, int]: 
    assert w > 0, w 
    ret = defaultdict(int)
    for i in range(len(doc) - w + 1): 
        ret[tuple(doc[i:i+w])] += 1 
    return ret 
    

print(doc_to_shingle_bag(A, 1))
print(doc_to_shingle_bag(A, 2))
print(doc_to_shingle_bag(A, 4))

def doc_to_shingles(doc: List[str], w: int) -> Set[Shingle]:
    assert w > 0, w 
    ret = set()
    for i in range(len(doc) - w + 1): 
        ret.add(tuple(doc[i:i+w]))
    return ret 

print(doc_to_shingles(A, 1))
print(doc_to_shingles(A, 2))
print(doc_to_shingles(A, 4))

def naive_resemblance_a(
    shingles_a: defaultdict[Shingle, int],
    shingles_b: defaultdict[Shingle, int]
) -> float:
    i = 0
    u = 0
    for k in set(shingles_a.keys()) | set(shingles_b.keys()):
        i += min(shingles_a[k], shingles_b[k])
        u += max(shingles_a[k], shingles_b[k])
    return i / max(u, 1e-6)

eps = 1e-6
ret = naive_resemblance_a(doc_to_shingle_bag(A, 1), doc_to_shingle_bag(B, 1)) 
assert abs(ret - 0.7) < eps, ret

ret = naive_resemblance_a(doc_to_shingle_bag(A, 2), doc_to_shingle_bag(B, 2)) 
assert abs(ret - 0.5) < eps, ret

ret = naive_resemblance_a(doc_to_shingle_bag(A, 3), doc_to_shingle_bag(B, 3)) 
assert abs(ret - 0.3) < eps, ret

print('All test cases passed.')

def naive_resemblance_b(
    shingles_a: Set[Shingle], 
    shingles_b: Set[Shingle]
) -> float:
    intersection = shingles_a & shingles_b 
    union = shingles_a | shingles_b 
    return len(intersection) / max(len(union), 1e-6)

eps = 1e-6
ret = naive_resemblance_b(doc_to_shingles(A, 1), doc_to_shingles(B, 1)) 
assert abs(ret - 0.6) < eps, ret 
ret = naive_resemblance_b(doc_to_shingles(A, 2), doc_to_shingles(B, 2)) 
assert abs(ret - 0.5) < eps, ret 
ret = naive_resemblance_b(doc_to_shingles(A, 3), doc_to_shingles(B, 3)) 
assert abs(ret - 0.42857142) < eps, ret

print('All test cases passed')

vocab_size = 60000
def random_doc(k):
    return set(random.sample(range(vocab_size), k))

random_doc(4)

def Jaccard_similarity(doc_a, doc_b):
    doc_a = set(doc_a)
    doc_b = set(doc_b)
    return len(doc_a & doc_b) / len(doc_a | doc_b)

def min_s(doc, s):
    doc = np.asarray(list(doc))
    return -find_top_k(-doc, s) \
        if len(doc) > s \
        else doc

d = random_doc(4)
print('document:', d)
print('min_s(document):', min_s(d, 2))

random_permutations = []
for i in range(1000):
    indices = list(range(vocab_size))
    random.shuffle(indices)
    random_permutations.append(indices)
    
random_permutation_index = 0

def get_random_permutation():
    global random_permutation_index
    indices = random_permutations[random_permutation_index]
    random_permutation_index += 1 
    random_permutation_index %= len(random_permutations)
    pi = lambda x: [indices[i] for i in x]
    return pi    

def m(pi, doc, s):
    return min_s(pi(doc), s)

def estimate_resemblance(pi, doc_a, doc_b, s):
    ma = set(m(pi, doc_a, s))
    mb = set(m(pi, doc_b, s))
    tmp = set(min_s(ma | mb, s))
    return len(tmp & ma & mb) / len(tmp)   

errors = []
for i in range(8):
    length_a = random.randint(10000, 30000)
    length_b = random.randint(10000, 30000)
    doc_a = random_doc(length_a)
    doc_b = random_doc(length_b)
    sim_j = Jaccard_similarity(doc_a, doc_b)
    
    num_samples = 256
    samples = []
    for j in range(num_samples):
        pi = get_random_permutation()
        s = estimate_resemblance(pi, doc_a, doc_b, s=10)
        samples.append(s)
    resemblance_est = np.mean(samples)
#     assert abs(sim_j - resemblance_est) < 1e-2
    errors.append((sim_j - resemblance_est))
    print('{}：{:.4f} ≈ {:.4f}'.format(i + 1, sim_j, resemblance_est))
print('Average error:', np.mean(np.abs(errors)))    

max_shingle_ID = 2**32-1
next_prime = 4294967311
num_hashes = 128

def pick_random_coeffs(k):
    rand_list = []
  
    for _ in range(k):
        rand_index = random.randint(0, max_shingle_ID) 

        while rand_index in rand_list:
            rand_index = random.randint(0, max_shingle_ID) 

        rand_list.append(rand_index)
    
    return rand_list

coeff_a = pick_random_coeffs(num_hashes)
coeff_b = pick_random_coeffs(num_hashes)
print(coeff_a[:8], coeff_b[:8])

from functools import partial 

hash_functions = [
    partial(
        lambda x, i: (coeff_a[i] * x + coeff_b[i]) % next_prime,
        i=i
    )
    for i in range(num_hashes)
]

hash_functions[0](0), hash_functions[1](0), hash_functions[0](0)

def get_min_hash(doc):
    hash_codes = [
        min((hash_function(x) for x in doc))
        for hash_function in hash_functions 
    ]
    return hash_codes 

random_docs = [random_doc(random.randint(10000, 30000)) for _ in range(8)]
hash_codes = [get_min_hash(doc) for doc in random_docs]

errors = [] 
total_time_j = 0
total_time_min_hash = 0

for i in range(len(random_docs)):
    doc_a = random_docs[i]
    min_hash_a = hash_codes[i]
    for j in range(i + 1, len(random_docs)):
        doc_b = random_docs[j]
        min_hash_b = hash_codes[j]
        
        t = time.time()
        sim_j = Jaccard_similarity(doc_a, doc_b)
        total_time_j += time.time() - t 
        
        t = time.time()
        resemblance_est = np.mean([a == b for a, b in zip(min_hash_a, min_hash_b)])
        total_time_min_hash += time.time() - t 
        
        errors.append((sim_j - resemblance_est))
        print('{}-{}：{:.4f} ≈ {:.4f}'.format(i, j, sim_j, resemblance_est))
print('Average error:', np.mean(np.abs(errors)))   
print('Time Difference: {:.4}s:{:.4}s'.format(total_time_j, total_time_min_hash))

t = 128
rb_list = [
    [32, 4],
    [16, 8],
    [8, 16],
    [4, 32],
]
plt.figure()

for r, b in rb_list:
    assert r * b == t 
    p = np.linspace(0, 1, 1000)
    fp = 1 - (1 - p**r)**b
    plt.plot(p, fp)

plt.legend(['r={};b={}'.format(r, b) for r, b in rb_list])
plt.xlabel('p')
plt.ylabel('f(p)')
plt.show()
plt.close()