Comment calculer la similarité de deux textes avec Jaccard similitude de deux sac via MinHash?

Question

J'ai les deux textes suivants:

text0 = "AAAAAAAAAAAA";

text1 = "AAAAABAAAAAA";

J'utilise 4 bardeaux. Ainsi, text0 = {AAAA}, text1 = {AAAA, AAAB, AABA, ABAA, BAAA}. Ensuite, la similarité de Jaccard est sim = 1/5 = 0,2.

---

Je ne veux pas ce résultat. Parce que les deux textes semblent avoir des similitudes élevées.

Je veux utiliser la similarité de sac comme suit:

text0 = {AAAA, AAAA, AAAA, AAAA, AAAA, AAAA, AAAA, AAAA, AAAA},

text1 = {AAAA, AAAA, AAAB, AABA, ABAA, BAAA, AAAA, AAAA, AAAA}.

Si vous utilisez ces deux sacs, son similaire est sim = 5/9. C'est beaucoup plus élevé que 0.2.

Est-ce que MinHash peut faire celui-ci?

Answer 1

Pour les sacs que vous pouvez utiliser le hachage pondéré minwise, voir

S. Ioffe, Improved consistent sampling, weighted minhash and l1 sketching, 2010

ou

A. Shrivastava, Simple and Efficient Weighted Minwise Hashing, 2016.

Si les multiplicités sont toujours de petits nombres entiers, vous pouvez également utiliser un hachage miniforme non pondéré en rendant les entrées uniques, par ex. par numérotation:

text0 = {AAAA1, AAAA2, AAAA3, AAAA4, AAAA5, AAAA6, AAAA7, AAAA8, AAAA9},

text1 = {AAAA1, AAAA2, AAAB1, AABA1, ABAA1, BAAA1, AAAA3, AAAA4, AAAA5}.