Asocjacyjne mieszanie skrótów

14

Rozważ mało pojedynczo połączoną listę w czysto funkcjonalnym otoczeniu. Jego pochwały śpiewano ze szczytów górskich i nadal będą śpiewane. Zajmę się tutaj jedną z wielu jego mocnych stron i pytaniem, w jaki sposób można ją rozszerzyć na szerszą klasę czysto funkcjonalnych sekwencji opartych na drzewach.

Problem jest następujący: Chcesz przetestować prawie pewną strukturalną równość w czasie O (1) za pomocą silnego skrótu. Jeśli funkcja skrótu jest strukturalnie rekurencyjna, tj. Hash (x: xs) = mix x (hash xs), wówczas możesz transparentnie buforować wartości skrótu na listach i aktualizować je w czasie O (1), gdy element zostanie skonwertowany na istniejącą listę . Większość algorytmów dla list skrótów jest strukturalnie rekurencyjna, więc takie podejście jest wyjątkowo przydatne w praktyce.

Załóżmy jednak, że zamiast pojedynczo połączonych list masz sekwencje drzewiaste, które obsługują konkatenację dwóch sekwencji o długości O (n) w czasie O (log n). Aby buforowanie skrótów działało tutaj, funkcja mieszania skrótów musi być asocjatywna, aby przestrzegać stopni swobody drzewa w reprezentowaniu tej samej sekwencji liniowej. Mikser powinien pobrać wartości skrótu poddrzewa i obliczyć wartość skrótu całego drzewa.

Właśnie tam byłem sześć miesięcy temu, kiedy spędziłem dzień nad rozmyślaniem i badaniem tego problemu. Wydaje się, że w literaturze nie zwrócono uwagi na struktury danych. Natknąłem się na algorytm haszujący Tillicha-Zemora z kryptografii. Opiera się na mnożeniu macierzy 2x2 (co jest asocjacyjne), gdzie bity 0 i 1 odpowiadają dwóm generatorom subalgebry z wpisami w polu Galois.

Moje pytanie brzmi: co przegapiłem? W literaturze na temat kryptografii i struktur danych muszą znajdować się dokumenty istotne, których nie udało mi się znaleźć podczas wyszukiwania. Wszelkie uwagi dotyczące tego problemu i możliwych miejsc do zbadania będą mile widziane.

Edycja: Interesuje mnie to pytanie zarówno na miękkich, jak i kryptograficznie mocnych końcach spektrum. Z drugiej strony można go stosować do tablic mieszających, w których należy unikać kolizji, ale nie są one katastrofalne. Z drugiej strony można go wykorzystać do testowania równości.

Per Vognsen
źródło

Odpowiedzi:

2

Dodano : Po przeczytaniu komentarzy Pera, myślę, że ta odpowiedź jest tylko (słabą) odmianą algorytmu mieszającego Tillicha-Zemora, który jest już wspomniany w pytaniu. Wycofuję tę odpowiedź, ale zostawiam ją z nadzieją, że (i komentarze) może być pouczająca dla niektórych czytelników.


Edycja : Wcześniejsza wersja tej odpowiedzi sugerowała użycie operacji monoidu na [ m ], ale jak zauważył Per w komentarzu, pożądane jest użycie operacji grupowej.

Ta odpowiedź dotyczy budowania funkcji skrótu dla tabel skrótów, która jest łatwa do wdrożenia. Nie należy oczekiwać możliwej do udowodnienia gwarancji jakości.

Zakładając, że masz już funkcję skrótu dla każdego elementu sekwencji do zbioru skończonego [ m ] = {1,…, m }, co powiesz na interpretację każdego elementu [ m ] jako elementu w grupie skończonej G i użycie operacja grupowa na G ? Możesz użyć dowolnego mapowania od [ m ] do G , ale pożądane jest, aby mapowanie było iniekcyjne, abyśmy nie stracili informacji w wartości skrótu każdego elementu. Pożądane jest również, aby grupa nie była przemienna, aby funkcja skrótu mogła wychwycić różnicę w kolejności elementów w sekwencji.

Niewiele wiem o grupach skończonych, które pozwalają na szybkie operacje, ale sądzę, że takie grupy są znane w teorii kodowania. Korzystanie z symetrycznej grupy porządku co najmniej m może nie być takie złe.

Tsuyoshi Ito
źródło
1
Tak, mieszanie Tillicha-Zemora wykorzystuje również mnożenie macierzy. To, co sugerujesz, nie może działać bez dalszych modyfikacji a la Tillich-Zemor. Na przykład musisz unikać pojedynczych macierzy, w przeciwnym razie gromadzisz się przy wartości 0, niszcząc statystyki mieszania. Tillich-Zemor pracuje nad polem Galois; wcześniejsza wersja ich algorytmu miała problemy, ponieważ korzystały z generującego wielomianu, który miał nieoptymalne statystyki, więc dane pole Galois może być bardzo ważne.
Per Vognsen
@Per: Rozumiem. Dziękuję za wyjaśnienie. A co powiesz na użycie skończonych grup? Zmieniłem odpowiedź na to.
Tsuyoshi Ito
Zgadzam się. Najlepszym sposobem generowania nieskończonych rodzin grup jest użycie grup macierzy nad polami skończonymi (por. Twierdzenie o klasyfikacji dla skończonych prostych grup), więc wydaje się, że algorytmy tej postaci będą typu Tillicha-Zemora.
Per Vognsen
@Per: Nie znam teorii grup i nie rozumiem, dlaczego grupy macierzy nad polami skończonymi są lepsze niż grupy symetryczne w tym kontekście. Czy możesz to rozwinąć?
Tsuyoshi Ito
1
Jest kilka powodów. Po pierwsze, nie można wydajnie obliczać w dużych grupach symetrycznych, a grupy muszą być rzędu 2 ^ 128 dla odporności na kolizje. W przeciwieństwie do tego można bardzo wydajnie obliczyć za pomocą macierzy na charakterystycznych 2 skończonych polach, szczególnie jeśli wybierzesz wielomian rzadkiego generatora; to tylko kilka drobnych manipulacji.
Per Vognsen
1

Prawie uniwersalna rodzina funkcji mieszających

{ha(x)=aiximodp:aZp}

ha(x)+a|x|ha(y)=ha(xy)a|x|O(1)Zp

xyO(min(|x|,|y|)/p)

jbapple
źródło
1

nn,ny,yny=H(y,y)HO(1)O(lgn)

H(x1,,xm)x1,,xmm

DW
źródło