MinHash Jaccard Estimate

Problem

Estimate the Jaccard similarity of two string collections with num_hashes independent MinHash functions and return the fraction of matching signature minima. Hash each string with a deterministic FNV-style rolling hash, then for each seed i compute min over elements of (x * (i + 1) + offset) mod 1000000007 as that signature position. Return 0.0 when num_hashes <= 0 or either collection is empty.

Hint

Identical sets always produce identical minima, so every signature position matches.

Test cases

case 1

in: [["the","cat","sat"],["the","cat","ran"],4]

expected: 0.5

case 2

in: [["a","b"],["a","b"],8]

expected: 1

case 3

in: [["a"],["b"],5]

expected: 0

case 4

in: [["a","b","c"],["c","b","a"],10]

expected: 1

Starter codePython

def minhash_jaccard(a, b, num_hashes):
    # Your code here
    pass

4 test cases · run your code against them in the editor