Zastanawiam się, czy istnieje wydajny algorytm, albo może
wręcz jakaś metoda analityczna, do budowy różnowartościowych
funkcji hash.

Mamy zbiór X, elementami zbioru X jest N liczb
całkowitych x_i. Zwykle N jest większe od 10 i mniejsze
od 10tys. Liczby całkowite x_i zwykle należą do przedziału
od -10^6 do +10^6. Trzeba znaleźć różnowartościową
funkcję h, która odwzoruje wszystkie elementy X w ciąg
liczb naturalnych od 1 do M. Idealnie jakby M było
równe N, ale jeśli M < N*3 to też nie będzie źle.

Chodzi o to, aby funkcja h była możliwie prosta i
żeby dało się ją wydajnie zaimplementować. Przykładem
funkcji h może być:
h( x_i ) = ( (x_i + a_1 ) * (x_i + a_2) * ... * (x_i + a_n) ) % M;
gdzie n jest możliwe małe, najlepiej gdy 2<=n<=3.

Moje pytanie sprowadza się do tego, czy istnieje efektywny
algorytm, który na wejście otrzyma parę: zbiór X i M, a
na wyjściu poda a_1, a_2, a_n.

Oczywiście funkcja h nie musi być taka jak podałem w
przykładzie, może lepiej sprawdzi się operacja xor:
h( x_i ) = ( (x_i xor a_1 ) * (x_i xor a_2) * ... * (x_i xor a_n) ) % M;

Trzeba przeiterować po wszystkich a_i żeby dowiedzieć się
czy dla danego X i M istnieje różnowartościowa funkcja H,
czy można to jakoś sprawniej osiągnąć?

Pozdrawiam

do góry

W dniu piątek, 8 marca 2013 04:10:04 UTC+1 użytkownik M.M. napisał:
> Zastanawiam się, czy istnieje wydajny algorytm, albo może
> wręcz jakaś metoda analityczna, do budowy różnowartościowych
> funkcji hash.

Takie funkcje mieszające nazywają się "doskonałymi" (perfect) --
piszę to jedynie dla ułatwienia dalszego googlania.

Tu masz uniwersalny algorytm:
http://stevehanov.ca/blog/index.php?id=119

w.

do góry

W dniu piątek, 8 marca 2013 23:38:08 UTC+1 użytkownik Wojciech Muła napisał:
> W dniu piątek, 8 marca 2013 04:10:04 UTC+1 użytkownik M.M. napisał:
>
> > Zastanawiam się, czy istnieje wydajny algorytm, albo może
> > wręcz jakaś metoda analityczna, do budowy różnowartościowych
> > funkcji hash.
> Takie funkcje mieszające nazywają się "doskonałymi" (perfect) --
> piszę to jedynie dla ułatwienia dalszego googlania.
> Tu masz uniwersalny algorytm:
> http://stevehanov.ca/blog/index.php?id=119
Tamten, o ile dobrze zrozumiałem, wymaga dużo pamięci na jakąś tabelę
pośrednią.

Algorytm CHD
http://cmph.sourceforge.net/
wymaga tylko 2.07 bita na klucz, ale jak na razie nie rozumiem jak
on działa.

Pozdrawiam

do góry

W dniu sobota, 9 marca 2013 00:25:44 UTC+1 użytkownik M.M. napisał:
> > Tu masz uniwersalny algorytm:
> > http://stevehanov.ca/blog/index.php?id=119
>
> Tamten, o ile dobrze zrozumiałem, wymaga dużo pamięci na jakąś tabelę
> pośrednią.
>
> Algorytm CHD
> http://cmph.sourceforge.net/
> wymaga tylko 2.07 bita na klucz, ale jak na razie nie rozumiem jak
> on działa.

Hanov opisuje właśnie CHD; autorzy CHD kompresują tablice pośrednie, stąd
niska średnia bitowa. Metoda kompresji jest opisana w "Simple Random Access
Compression" K.Fredriksson, F.Nikitin.

w.

do góry

W dniu niedziela, 10 marca 2013 15:33:23 UTC+1 użytkownik Wojciech Muła napisał:
> Hanov opisuje właśnie CHD; autorzy CHD kompresują tablice pośrednie, stąd
> niska średnia bitowa. Metoda kompresji jest opisana w "Simple Random Access
Compression" K.Fredriksson, F.Nikitin.
Ok, dzięki.

do góry