Hashowanie zbiorów liczb całkowitych do testów włączenia

Szukam funkcji skrótu nad zestawami H (.) I relacją R (.,.) Tak, że jeśli A jest zawarte w B, to R (H (A), H (B)). Oczywiście R (.,.) Musi być łatwe do zweryfikowania (czas stały), a H (A) należy obliczyć w czasie liniowym.

Jednym z przykładów H i R jest:

$H(A) = \bigvee_{x\in A} 1 << (h(x) \mod k)$ , gdzie k to stała liczba całkowita, a h (x) funkcja skrótu nad liczbami całkowitymi.
R (H (A), H (B)) = ((H (A) i H (B)) == H (A))

Czy są jakieś inne dobre przykłady? (dobro jest trudne do zdefiniowania, ale intuicyjnie, jeśli R (H (A), H (B)), to whp A jest uwzględnione w B).

Późniejsza edycja :

Szukam rodziny funkcji skrótu. Mam wiele zestawów; 3 - 8 elementów w każdym zestawie; 90% z nich ma 3 lub 4 elementy. Przykładowa funkcja skrótu, którą podałem, nie jest zbyt dobrze rozłożona w tym przypadku.
Liczba bitów H (.) (W moim przykładzie k), które powinny być małe (tj. H (.) Musi mieścić się w liczbie całkowitej lub długiej).
Jedną fajną właściwością R jest to, że jeśli H (.) Ma k bitów, to R (.,.) Jest prawdziwe dla par (3 ^ k - 2 ^ k) / 4 ^ k, tj. dla bardzo niewielu par.
Filtry Bloom są szczególnie dobre w przypadku dużych zestawów. Próbowałem użyć BF do tego problemu, ale optymalne wyniki były tylko z jedną funkcją.

(crosspost z stackoverflow , nie otrzymałem wystarczająco dobrej odpowiedzi)

ds.algorithms hash-function Alexandru
źródło

„bicz” nad czym? Czy zakładasz, że twoje dane wejściowe pochodzą z określonej dystrybucji?

Jukka Suomela

Czy naprawdę szukasz pojedynczej, stałej funkcji skrótu, a nie rodziny funkcji skrótu?

Jukka Suomela

@Jukka: Myślę, że ma na myśli, jeśli R (H (A), H (B)), to z dużym prawdopodobieństwem dochodzimy do wniosku, że A jest podzbiorem B. Prawdopodobieństwo jest przejmowane przez losowe wybory A i B, a także wewnętrzne rzuty monetą H i R (jeśli występują).

MS Dousti

Szukam rodziny funkcji skrótu. Moje zestawy są zwykle małe (3–8 elementów każdy; 90% z nich ma 3 lub 4 elementy), więc podana przeze mnie funkcja skrótu nie jest zbyt dobrze rozłożona.

Alexandru

Jedną fajną właściwością R jest to, że jeśli H (.) Ma n bitów, to R (.,.) Jest prawdziwe dla par (3 ^ n - 2 ^ n) / 4 ^ n, tj. dla bardzo niewielu par.

Alexandru

Odpowiedzi:

(Ta odpowiedź była pierwotnie w komentarzach, ale przenoszę ją do osobnej odpowiedzi według sugestii Suresha).

W przypadku aplikacji z bardzo małymi zestawami prawdopodobnie chcesz, aby liczba funkcji mieszania Blooma była dość duża, aby zminimalizować liczbę wyników fałszywie dodatnich. Aby zaoszczędzić czas obliczeń, sugeruję następującą odmianę filtra Blooma. Załóżmy, że masz trzy tradycyjne funkcje skrótu , , dla elementów, z których każdy wytwarza ciągi bitowe. Hashuj każdy element do bitowej i tych trzech funkcji skrótu. Wynikowe wartości skrótu elementu będą wynosić około $k$ $h_1$ $h_2$ $h_3$ $m$ $2^{-3}=1/8^{th}$ te. Mieszaj każdy zestaw bitowo lub skrótami jego elementów składowych. Ponieważ twoje zestawy zawierają 3-8 elementów, wynikowe wartości skrótu będą znajdować się w sąsiedztwie wartości połowy, co jest prawdopodobnie tym, co chcesz najlepiej utrzymać na niskim poziomie fałszywie dodatnich wyników.

Różnica między powyższym schematem polega na tym, że tradycyjny filtr Blooma jest analogiczny do różnicy między klasycznym modelem losowym Erdos a losowymi wykresami nieregularnymi. Powyższy schemat ma efektywną liczbę skrótów Blooma różni się nieco wokół średniej ale jest dość duży, więc ta różnica nie powinna mieć znaczenia. $G_{n,p}$ $d$ $k$ $m/8$ $m/8$

Warren Schudy
źródło

Jest to szczególnie dobre dla dużych m (32 lub 64), jak sugerowałeś.

Alexandru

Spróbowałbym użyć filtra Blooma jako skrótu z relacją taką samą, jak twoja propozycja. Obliczenie najlepszego rozmiaru filtra liczby funkcji skrótu dla twojej aplikacji nie powinno być zbyt trudne; inspirację znajdziesz w artykule Bloom Bloom w Wikipedii . W zależności od tego, jak bardzo chcesz uniknąć fałszywych alarmów, wystarczy coś takiego jak i . $m$ $k$ $m=64$ $k=4$

Warren Schudy
źródło

Do aplikacji z bardzo małymi zestawami prawdopodobnie potrzebujesz dość dużych. Może to być dość powolne w przypadku tradycyjnego podejścia. Zamiast tego sugeruję następujące.

k

$k$

Warren Schudy,

(Kontynuacja poprzedniego komentarza) Jest to zasadniczo odmiana filtrów Bloom. Załóżmy, że masz trzy funkcje skrótu , , dla elementów wytwarzających ciągi bitowe. Hash element do bitów i tych trzech. Powstałe skróty będą miały około 1/8 1s. Hashuj zestaw bitów lub skrótów jego elementów składowych. Ponieważ twoje zestawy zawierają 3-8 elementów, wynikowe wartości skrótu będą miały w niebrodzinach połowę, co prawdopodobnie pomoże utrzymać współczynnik fałszywie dodatnich na niskim poziomie.

h_{1}

$h_1$

h_{2}

$h_2$

h_{3}

$h_3$

m

$m$

Warren Schudy,

Zaletą tej odmiany jest tylko to, że lepiej wykorzystuje równoległość związaną z operacjami słownymi, które ma większość komputerów.

Warren Schudy,

Warren, powinieneś opublikować to jako odpowiedź. Zasługuje na kilka głosów

Suresh Venkat

@Warren, @Suresh: Myślę, że sensowniejsze byłoby połączenie tych dwóch ściśle powiązanych odpowiedzi, a następnie usunięcie komentarzy. Łatwiej byłoby naśladować, zwłaszcza, że jedna z odpowiedzi odnosi się do parametrów zdefiniowanych w drugiej.

Jukka Suomela