Zestaw probabilistyczny bez fałszywych trafień?

Tak więc filtry Bloom są całkiem fajne - są zestawami, które obsługują sprawdzanie członkostwa bez fałszywych negatywów, ale z niewielką szansą na fałszywy pozytyw. Ostatnio jednak chciałem mieć „filtr Blooma”, który gwarantuje coś przeciwnego: żadnych fałszywych alarmów, ale potencjalnie fałszywych negatywów.

Moja motywacja jest prosta: biorąc pod uwagę ogromny strumień przedmiotów do przetworzenia (z duplikatami), chcielibyśmy uniknąć przetwarzania przedmiotów, które widzieliśmy wcześniej. Przetwarzanie duplikatu nie zaszkodzi, to tylko strata czasu. Gdybyśmy jednak zaniedbali przetwarzanie elementu, byłoby to katastrofalne. Dzięki „odwrotnemu filtrowi Blooma” można przechowywać widoczne przedmioty przy niewielkim nakładzie miejsca i unikać przetwarzania duplikatów z dużym prawdopodobieństwem, testując członkostwo w zestawie.

Jednak nie mogę znaleźć czegoś takiego. Najbliższe, jakie znalazłem, to „ wyretuszowane filtry Blooma ”, które pozwalają handlować wybranymi fałszywie dodatnimi wynikami w celu uzyskania wyższego wskaźnika fałszywie ujemnych wyników. Nie wiem jednak, jak dobrze radzi sobie ich struktura danych, gdy chce się usunąć wszystkie fałszywe alarmy.

Ktoś widział coś takiego? :)

Jedną z odpowiedzi jest użycie dużej tabeli skrótów, a kiedy się zapełni, zacznij zastępować w niej elementy zamiast znajdować (nieistniejące) puste miejsca w innych miejscach. Nie dostajesz ładnej stałej liczby fałszywych odpowiedzi, którą robisz z filtrami Bloom, ale jest to lepsze niż nic. Uważam, że jest to standard, np. W oprogramowaniu szachowym do śledzenia pozycji, które zostały już przeszukane.

Odpowiedź na to pytanie brzmi „nie”. Aby zrozumieć dlaczego, możemy pomyśleć o bardzo ekstremalnym przypadku i o tym, jak działałby zwykły filtr kwitnienia w porównaniu z teoretycznym filtrem kwitnienia „Bizzaro World”, który możemy nazwać „filtrem mroku”.

Wspaniałe w filtrze Bloom jest to, że można wykonywać jednostronne testy przynależności do elementów (z fałszywymi trafieniami) przy użyciu struktury danych o ustalonym rozmiarze w odniesieniu do prawdopodobieństwa błędu i liczby przechowywanych elementów. Te rozmiary tych elementów sami nie mają znaczenia w ogóle. Na przykład, gdybyśmy skonfigurowali filtr Blooma do przechowywania do 1000 elementów z mniejszym niż 3% błędem, wówczas moglibyśmy przechowywać 1000 nieco różnych wersji całego korpusu Wikipedii, z jedną literą zmienioną w każdej, i nadal byśmy uzyskamy potrzebne mi dane, a struktura danych byłaby bardzo mała (mniej niż kilobajt). Oczywiście obliczenie tych skrótów będzie wyzwaniem, ale zasada nadal obowiązuje.

Teraz rozważ przechowywanie tych samych masywnych strun w filtrze mroku! Teraz możemy mieć tylko fałszywe negatywy. Jeśli więc powiemy „tak, ta wersja całego korpusu Wikipedii znajduje się w tym zestawie”, musimy mieć całkowitą rację. Oznacza to, że haszowanie nam nie pomoże, ponieważ zawsze będzie jakiś inny ciąg hashujący do tej samej wartości. Jedynym sposobem, aby powiedzieć „tak” i mieć pewność, jest zapisanie całego łańcucha lub niektórych równoważnych danych o tej samej długości. Zawsze nie mogliśmy tego zapisać i powiedzieć „nie”, ale ostatecznie poziom błędu nas dogoni. Najlepsze, co mogliśmy zrobić, to kompresja, sprowadzenie rozmiaru struktury do iloczynu entropii przechowywanych danych i pożądanej dokładności.

Więc niestety filtr mroku nie istnieje. Buforowanie jest jedynym rozwiązaniem, ale tak naprawdę nie jest przeciwieństwem filtra Blooma, ponieważ jego rozmiar będzie proporcjonalny do iloczynu ilości przechowywanych informacji i pożądanego stopnia dokładności filtra. Oczywiście w wielu rzeczywistych sytuacjach duże dane mogą być reprezentowane przez identyfikator, więc buforowanie może być nadal całkiem akceptowalne. Ale zasadniczo różni się od potężnego filtra kwitnienia.

Chcesz tylko pamięci podręcznej , ale zastanawiasz się nad tym w dziwny sposób.

ZASTRZEŻENIE: Nie jestem ekspertem w dziedzinie pamięci podręcznych, więc może to być naiwny pomysł, a także może być znany pomysł, o którym nigdy wcześniej nie słyszałem. Więc przepraszam, jeśli nie przytoczę jego odniesienia (jeśli istnieje); i poinformuj mnie, czy istnieje odniesienie do edycji postu i dodania go. (Podejrzewam, że może mieć referencję, ponieważ jest tak intuicyjna).

Szybkie rozwiązanie, zainspirowane Strilanc, może po prostu zachować asocjacyjną mapę maksymalnych wpisów (gdzie jest stałe), kojarząc element z liczbą wyświetleń. Gdy mapa asocjacyjna jest pełna i napotkasz nowy przedmiot, którego nie ma na mapie, odwróć monetę, aby ją dodać lub nie. Jeśli chcesz go dodać, usuń element z prawdopodobieństwem odwrotnie proporcjonalnym do liczby wyświetleń.$c$$c$

Użyłem drzew AVL (a czasem czerwono-czarnych) z częściowymi elementami, które działają jak filtr bez fałszywych negatywów. Używaj tylko pierwszych X bajtów elementu podczas wstawiania lub zapytania drzewa. Ponieważ struktura danych nie ma postaci probabilistycznej, nie ma ryzyka fałszywie dodatniego wyniku kolizji bitów. I w przeciwieństwie do buforowania całego przedmiotu, to podejście daje obliczalne maksymalne miejsce. Możesz dostroić liczbę fałszywych alarmów, biorąc pod uwagę różne długości prefiksów / głębokości drzewa w porównaniu do kosztu fałszywych alarmów i przestrzeni.

Myślę, że można udowodnić dolną granicę, stwierdzając, że powyższa struktura danych nie może istnieć. Zasadniczo, jeśli struktura danych wykorzystuje m bitów, to ustalony wektor bitowy (reprezentacja wejścia) może odpowiadać co najwyżej (((un) + n eps) \ select (un)) zestawom przez argument zliczający. Biorąc pod uwagę, że 2 ^ m razy liczba ta musi być co najmniej (u \ wybierz n) (wszystkie zbiory muszą być reprezentowane), otrzymujemy dolną granicę, która jest zasadniczo bardzo bliska dokładnego przechowywania zbioru S.