Asocjacyjne mieszanie skrótów

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.

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.

Prawie uniwersalna rodzina funkcji mieszających

$h_a(\vec{x}) + a^{|\vec{x}|}h_a(\vec{y}) = h_a(\vec{x} \circ \:\vec{y})$$\circ$$a^{|\vec{x}|}$$O(1)$$\mathbb{Z}_p$

$\vec{x} \neq \vec{y}$$O(\min(|\vec{x}|,|\vec{y}|)/p)$

$n$$n',n''$$y',y''$$n$$y=H(y',y'')$$H$$O(1)$$O(\lg n)$

$H(x_1,\dots,x_m)$$x_1,\dots,x_m$$m$