-
1. Data: 2013-03-08 04:10:04
Temat: w poszukiwaniu funkcji hash
Od: "M.M." <m...@g...com>
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
-
2. Data: 2013-03-08 23:38:08
Temat: Re: w poszukiwaniu funkcji hash
Od: Wojciech Muła <w...@g...com>
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.
-
3. Data: 2013-03-09 00:25:44
Temat: Re: w poszukiwaniu funkcji hash
Od: "M.M." <m...@g...com>
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
-
4. Data: 2013-03-10 15:33:23
Temat: Re: w poszukiwaniu funkcji hash
Od: Wojciech Muła <w...@g...com>
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.
-
5. Data: 2013-03-10 23:42:01
Temat: Re: w poszukiwaniu funkcji hash
Od: "M.M." <m...@g...com>
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.