Должны ли мы считать два набора одинаковыми, если их строки содержат одинаковые хэши, но в разном порядке?

Question

Предположим, у нас есть сигнатуры minhash для двух наборов, и мы хотим вычислить сходство Жакара двух наборов. У нас есть:

-> S1 S2

h1 0 1

h2 1 2

h3 2 0

h4 3 3

S1 и S2 имеют одинаковые подписи в разных порядках. Является ли сходство Жакара 1/8 или 1(приблизительно)?

Answer 1

Это разные хеш-функции, таким образом h2(S1) == h1(S2) ничего не значит Нет смысла сравнивать значения разных хешей. Так что прямо отвечу - сходство здесь 0 (без коллизий), поэтому не 1/8 и не 1.