Czy istnieje funkcja skrótu dla zbioru liczb całkowitych (tj. Wielu), która ma dobre gwarancje teoretyczne?

36

Ciekawe, czy istnieje sposób przechowywania skrótu zbioru liczb całkowitych, który ma następujące właściwości, najlepiej:

Wykorzystuje spację O (1)
Można go zaktualizować, aby odzwierciedlał wstawianie lub usuwanie w czasie O (1)
Dwie identyczne kolekcje (tj. Kolekcje, które mają te same elementy o tych samych wielokrotnościach) zawsze powinny mieć skrót do tej samej wartości, a dwie odrębne kolekcje powinny mieć skrót do różnych wartości z dużym prawdopodobieństwem (tj. Funkcja jest niezależna lub parami niezależna)

Jedną z początkowych prób byłoby przechowywanie modulo produktu losowej liczby pierwszych skrótów poszczególnych elementów. Spełnia to 1 i 2, ale nie jest jasne, czy to, czy też ścisła odmiana, spełnia 3.

Pierwotnie opublikowałem to na StackOverflow .

* Właściwości 1 i 2 można nieco rozluźnić, powiedzmy, O (log n) lub mały podliniowy wielomian. Chodzi o to, czy możemy zidentyfikować wiele zestawów i rzetelnie przetestować równość bez przechowywania samych elementów.

ds.algorithms ds.data-structures hash-function

— Jerry
źródło

Jaka jest twoja reprezentacja multisets? To znaczy, jak kodujesz multiset jako ciąg bitowy? Jeśli naprawdę chcesz uzyskać operacje w czasie

(niezależnie od rozmiaru multisetu), myślę, że powinieneś jawnie kodować.

O (1)

$O(1)$

— Jukka Suomela

Kodowanie zbiorów nie jest ważne. Funkcja skrótu powinna być niezależna od reprezentacji zbiorów. Gdybym używał kanonicznej reprezentacji zbioru skrótów, to każdy standardowy skrót w reprezentacji bitowej zbioru spełniałby 3, a prawdopodobnie 1, ale nie 2. Powinienem dodać, że dwie równe kolekcje powinny zawsze mieć skrót o tej samej wartości.

— poniedziałek

Co dokładnie masz na myśli przez 2? Czy masz stary zestaw, stary kod skrótu i nowy element i chcesz obliczyć nowy kod skrótu? A może dostajesz tylko stary kod skrótu i nowy element?

— Mihai

Idealnie nie byłby potrzebny stary zestaw. Nie musisz nawet być w stanie wykonywać zapytań członkowskich (ważne, biorąc pod uwagę ograniczenia miejsca), po prostu testować równość, prawdopodobnie poprzez porównywanie wartości skrótu, które mają małe prawdopodobieństwo fałszywie dodatniego.

— poniedziałek

17

Jeśli uważasz, że zestawy żyją we wszechświecie , dość łatwo jest rozwiązać problem z czasem aktualizacji . Wszystko czego potrzebujesz to szybka funkcja skrótu dla wektora liczb , z szybkimi „lokalnymi aktualizacjami”. $[u]$ $O(\lg u)$ $u$

, gdzie jest wystarczająco dużą liczbą pierwszą, a jest równomiernie narysowane z . Po dodaniu lub usunięciu elementu , trzeba dodać / odjąć z kodu skrótu, który zajmuje czas korzystania dziel i rządź do potęgowania. Ponieważ wielomian stopnia $h(\vec{x}) = \big(\sum_{i=1}^{u} x_i a^i \big) \bmod{p}$ $p$ $a$ $[p]$ $i$ $a^i$ $O(\lg i)$ $u$ może mieć tylko pierwiastki , prawdopodobieństwo zderzenia dla dwóch różnych zbiorów wynosi . Można to zrobić bardzo małe, przyjmując, że jest wystarczająco duże (na przykład i pracujesz w „podwójnej precyzji”). Jeśli zestawy są znacznie mniejsze niż , możesz oczywiście rozpocząć od skrócenia wszechświata do mniejszego wszechświata. $u$ $O(u/p)$ $p$ $p=u^2$ $[u]$

Czy ktoś zna rozwiązanie z prawdopodobieństwem kolizji przy mieszaniu do zakresu ? To powinno być możliwe. $O(1/p)$ $[p]$

— Mihai
źródło

0

Carter i Wegman opisują to w nowych funkcjach skrótu oraz ich zastosowaniu w uwierzytelnianiu i ustawianiu równości ; jest bardzo podobny do tego, co opisujesz. Zasadniczo komutatywną funkcję skrótu można aktualizować pojedynczo dla wstawiania i usuwania oraz dopasowań o wysokim prawdopodobieństwie w O (1).

— KWillets
źródło

Myślę, że działa to tylko na zestawach, a nie na multisetach (jak zadawane pytanie). Z sekcji 5, na dole strony 274: „DODAJ (x, S) - Dodaje element x do zestawu o nazwie S. Tej operacji nie można użyć, jeśli x jest już członkiem S.”

— jbapple,

Masz rację; Brakowało mi części „multi”. Wydaje się prawdopodobne, że funkcja skrótu poradziłaby sobie z duplikatami, choć nie mam na to żadnych wzmianek.

— KWillets,

-2

Jakość funkcji skrótu zawsze będzie zależeć od właściwości elementów, które musi mieszać. Czy możesz coś o tym powiedzieć? Na przykład sugestia produktu jest prawdopodobnie słabą funkcją skrótu, jeśli elementy x_i multiset zwykle mają wiele małych czynników pierwszych. Ale możesz to poprawić w tym przypadku, po prostu biorąc iloczyn wszystkich x_i + p mod q dla niektórych liczb pierwszych p i q.

— TonyK
źródło

1

Tak, to jest powód do zebrania skrótów poszczególnych elementów przed ich pomnożeniem.

— poniedziałek

Co? Sugestią PO jest po prostu pomnożenie ich wszystkich razem, prawda? Mówię, że jeśli dodasz stałą przed każdym z nich, prawdopodobnie uzyskasz lepszy skrót.

— TonyK,

-5

A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1 
N = size of set before addition/removal<P>
Add X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U+X)&M)<<16) + ((V^X)&M)
H *= A
H += N+1

Remove X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U-X)&M)<<16) + ((V^X)&M)
H *= A
H += N-1

suma pozwala nam mieć wiele wystąpień o tej samej wartości
xor pozwala nam mieć zestawy tej sumy na tę samą kwotę

— Louis Reinitz
źródło