MinHaketo

En komputoscienco, MinHaketo (aŭ la mininuma-sepdependa-permuta loko-zorga haketado) estas tekniko por rapide taksi la similecon de du aroj. La teknikon inventis Andrei Broder^[1], kaj oni unue uzis por la AltaVista serĉilo por detekti kaj forigi kopiojn de retpaĝo el la serĉrezulto.^[2] Ĝi ankaŭ uziĝas por granda arigado, ekzemple arigi fajloj per simileco de iliaj enhavaj vortoj^[1].

Ĝakarda simileco kaj minimuma haketvaloro

La Ĝakarda simileco estas ofteuzita mezuro de simileco inter du aroj. Por aroj A kaj B oni difinas la mezuron kiel la kardinalo de ilia komunaĵo dividita de kardinalo de ilia kunaĵo.

J(A,B)={{|A\cap B|} \over {|A\cup B|}}.

La valoro egalas al 0 kiam la du aroj estas disaj kaj 1 kiam ili estas samaj, alie inter 0 kaj 1. La mezuro estas pli proksima al 1 kiam la du aroj estas pli similaj. La celo de MinHaketo estas rapide taksi J(A,B), sen vere komputi la komunaĵon kaj kunaĵon.

Nun h estu haketofunckio el anoj de A kaj B al diskinktaj entjeroj. Por aro S, h_min(S) estu la minimuma ano de S laŭ h—t.e. la ano x de S tia, ke h(x) estas minimuma. Nun se oni mezurus h_min en A kaj B, la rezulto estus sama, kiam la minimuma elemento de la kunaĵo A ∪ B estas ankaŭ en la komunaĵo A ∩ B. La probablo de tio estas ekzakte la frakcio antaŭa. Tial

Pr[ h_min(A) = h_min(B) ] = J(A,B),

Alivorte, se r estu hazarda variablo kiu estas 1 kiam h_min(A) = h_min(B) kaj 0 alie, r estus senbiasa takso de J(A,B). Maloportune, r havas tro grandan variancon por esti utila por la Ĝakarda simileco per si mem. La ideo de MinHaketo estas malgrandigi ĝian variacon, per sumi multajn variablojn tiajn ĉi.

Algoritmo

Per pluraj haketfunkcioj

La plej simpla versio de MinHaketo uzas k malsamajn haketfunkciojn.

Por taksi J(A,B) ĉimaniere, komputu la k haketfunkciojn en A kaj B. y estu la nombro da haketfunckioj tia, ke h_min(A) = h_min(B), do y/k estas la takso. Tiu ĉi takso estas la meznombro de k malsamaj hazardaj variabloj inter 0-1, kiuj estas senbiasaj taksoj de J(A,B). Tial, la meznombro estas ankaŭ senbiasa takso. Laŭ norma Ĉernofa neekvacio por sumo de hazardaj variabloj inter 0-1 havas atenditan eraron $O(1/{\sqrt {k}})$ ^[3].

Per unu haketfunkcio

Estus longe komputi multe da haketfunkcioj, do alia versio de MinHash evitas tion per uzi unur unu haketfunkcio por elekti multe da valoroj de la aroj, anstataŭ elekti unu valoro po funkcioj. h estu haketfunkcio. S estu aro kun pli multa ol k elemento en la fonto-aro de h, h_(k)(S) estu la subaro de la k anoj de S kun la plej malgrandaj valoroj laŭ h. La subaro h_(k)(S) estas "priskribilo" de S, kaj la similecon de du aroj oni taksas per kompari iliajn priskribilojn.

Speciale, X = h_(k)(h_(k)(A) ∪ h_(k)(B)) = h_(k)(A ∪ B) estas aro da k elementoj en A ∪ B. Ĉar h estas bona haketfunkcio, ĉiu subaro de k elementoj eblus elektiĝi egalprobable. Do X estas simpla hazarda specimenado de A ∪ B. La subaro Y = X ∩ h_(k)(A) ∩ h_(k)(B) estas la aro de elementoj de X, kiuj ankaŭ apartenas al A ∩ B. Tial, |Y|/k estas senbiasa takso de J(A,B).

La malsamo inter versio per multaj haketfunkcioj kaj unu haketfunkcio estas X ĉiam havas k anoj, sed pluraj haketfunkcioj povas elekti la saman minimumon, do estus malpli da elementoj ol k. Tamen, kiam k estas malgranda rilate al S, tio ĉi estas ignorebla.

Laŭ norma Ĉernofa neekvacio por specimenado sen remeto, la takso hasvas atenditan eraron $O(1/{\sqrt {k}})$ , same al la versio per multaj haketfunkcioj.

Tempokosto

Oni povas komputi la takson |Y|/k en tempo O(k) el la du priskribiloj por ambaŭ versioj. La priskribilon de aro oni povas komputi en tempo lineare rilata al kardinalo de la aro. Do la tekniko malkostas multe da tempo, kiam oni devas taksi similecon inter multaj paroj da aroj, kontraste al plena komparo inter anoj de aroj. Speciale, por aroj de kardinalo n la versio per multaj haketfunkcioj kostas tempon O(n k). La versio per unu funkcio kostas nur tempon O(n) por komputi la k minimimajn haketvalorojn, alprene $n\gg k$ .

Vidu ankaŭ

Referencoj

↑ ^1,0 ^1,1 Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael (1998), "Min-wise independent permutations", Proc. 30th ACM Symposium on Theory of Computing (STOC '98), New York, NY, USA: Association for Computing Machinery, pp. 327–336, doi:10.1145/276698.276781
↑ Broder, Andrei Z. (1997), "On the resemblance and containment of documents", Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, IEEE, pp. 21–29, doi:10.1109/SEQUEN.1997.666900, archived from the original on 2015-01-31, https://web.archive.org/web/20150131043133/http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf, retrieved 2017-04-13 Arkivita kopio. Arkivita el la originalo je 2015-01-31. Alirita 2017-04-13 .
↑ Vassilvitskii, Sergey (2011), COMS 6998-12: Dealing with Massive Data (lecture notes, Columbia university), http://www.cs.columbia.edu/~coms699812/lecture1.pdf

[:0-1] 1,0 ^1,1 Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael (1998), "Min-wise independent permutations", Proc. 30th ACM Symposium on Theory of Computing (STOC '98), New York, NY, USA: Association for Computing Machinery, pp. 327–336, doi:10.1145/276698.276781

[bcfm-2] Broder, Andrei Z. (1997), "On the resemblance and containment of documents", Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, IEEE, pp. 21–29, doi:10.1109/SEQUEN.1997.666900, archived from the original on 2015-01-31, https://web.archive.org/web/20150131043133/http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf, retrieved 2017-04-13 Arkivita kopio. Arkivita el la originalo je 2015-01-31. Alirita 2017-04-13 .

[3] Vassilvitskii, Sergey (2011), COMS 6998-12: Dealing with Massive Data (lecture notes, Columbia university), http://www.cs.columbia.edu/~coms699812/lecture1.pdf

[1]

[2]

[3]