funkcja skrótu dla ciągu znaków

124

Pracuję na tablicy mieszającej w języku C i testuję funkcję skrótu dla ciągu znaków.

Pierwszą funkcją, którą wypróbowałem, jest dodanie kodu ascii i użycie modulo (% 100), ale mam słabe wyniki przy pierwszym teście danych: 40 kolizji na 130 słów.

Ostateczne dane wejściowe będą zawierały 8 000 słów (jest to słownik przechowywany w pliku). Tablica skrótów jest zadeklarowana jako int table [10000] i zawiera pozycję słowa w pliku txt.

Pierwsze pytanie brzmi: jaki jest najlepszy algorytm dla ciągu haszującego? i jak określić rozmiar tablicy skrótów?

z góry dziękuję !

:-)

lilawood
źródło
11
Jeśli twoja tablica haszująca zawiera 10K wpisów, dlaczego miałbyś używać modulo 100? Uzyskanie 40 zderzeń ze 130 słów nie jest zaskakujące przy tak małym module.
Carey Gregory
13
Zobacz burtleburtle.net/bob/hash/evahash.html i partow.net/programming/hashfunctions, dla których znajdują się zasoby o różnych hashowaniu (od ogólnego do ciągu znaków do krypto).
4
Aby wyjaśnić @CareyGregory: zdajesz sobie sprawę, że zgodnie z podstawową prawdą matematyczną, 130 elementów w 100 wiaderkach (tj. Mod 100) musi spowodować 30 kolizji (gdzie kolizja jest liczona za każdym razem, gdy wkładany jest drugi, trzeci itp. Przedmiot) wiadro), prawda? Więc jesteś tylko trochę powyżej tego.
derobert
4
@lilawood: OK, to właśnie pomyślałem, ale aby być lepszym testem, powinieneś użyć 80 słów z tablicą mieszającą zawierającą 100 wpisów. To dałoby takie same proporcje, jak dane na żywo i nie wymusiłoby kolizji.
Carey Gregory
4
Możliwy duplikat dobrej funkcji skrótu dla ciągów znaków
MJ Rayburn

Odpowiedzi:

186

Miałem dobre wyniki z djb2Danem Bernsteinem.

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}
cnicutar
źródło
37
strona, do której link znajduje się w odpowiedzi, jest bardzo interesująca.
Adrien Plisson
2
jak program kończy pętlę while? = S
Daniel N.
1
@ danfly09 Gdy c wynosi zero. Odpowiednikiem while (c = * str ++) byłoby (0! = (C = * str ++))
rxantos.
5
@Josepas funkcja skrótu powinna w idealnym przypadku zwrócić taką size_tlub inną taką wartość bez znaku (taką jak długość bez znaku w tym kodzie). Rozmówca jest odpowiedzialny za podejmowanie modulo rezultatu, aby dopasować go do tablicy mieszającej. Obiekt wywołujący kontroluje przedział tabeli, do którego jest mieszany; nie funkcja. Po prostu zwraca pewną liczbę bez znaku.
WhozCraig
6
niesamowity. ten algorytm wybił piekło z haszowania Murmur, skrótów wariantów FNV i wielu innych! +1
David Haim
24

Po pierwsze, generalnie nie chcesz używać kryptograficznego skrótu do tabeli skrótów. Algorytm, który jest bardzo szybki jak na standardy kryptograficzne, jest nadal potwornie powolny jak na standardy tablic mieszania.

Po drugie, chcesz mieć pewność, że każdy bit danych wejściowych może / wpłynie na wynik. Prostym sposobem na to jest obrócenie bieżącego wyniku o pewną liczbę bitów, a następnie XOR aktualnego kodu skrótu z bieżącym bajtem. Powtarzaj, aż dojdziesz do końca struny. Zauważ, że generalnie nie chcesz, aby rotacja była parzystą wielokrotnością rozmiaru bajtu.

Na przykład, zakładając typowy przypadek 8-bitowych bajtów, możesz obrócić o 5 bitów:

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

Edycja: Należy również pamiętać, że 10000 gniazd rzadko jest dobrym wyborem dla rozmiaru tabeli mieszania. Zwykle potrzebujesz jednej z dwóch rzeczy: albo potrzebujesz liczby pierwszej jako rozmiaru (wymaganej do zapewnienia poprawności przy niektórych typach rozdzielczości skrótu), albo potęgi 2 (więc zmniejszenie wartości do prawidłowego zakresu można zrobić prostym maska ​​bitowa).

Jerry Coffin
źródło
To nie jest c, ale byłbym zainteresowany twoimi przemyśleniami na temat tej powiązanej odpowiedzi: stackoverflow.com/a/31440118/3681880
Suragch
1
@Suragch: Odkąd to napisałem, sporo procesorów zaczęło zawierać albo specjalny sprzęt do przyspieszania obliczeń SHA, co uczyniło go znacznie bardziej konkurencyjnym. To powiedziawszy, wątpię, czy twój kod jest tak bezpieczny, jak myślisz - na przykład liczby zmiennoprzecinkowe IEEE mają dwa różne wzorce bitowe (0 i -0), które powinny generować te same skróty (będą porównywane jako równe sobie ).
Jerry Coffin
@Jerry Coffin, której biblioteki potrzebuję do funkcji rol ()?
thanos.
@ thanos.a: Nie jestem świadomy tego, że znajduje się on w bibliotece, ale zrobienie własnego zajmuje tylko jedną lub dwie linie kodu. Przesuń jeden fragment w lewo, drugi w prawo lub je razem.
Jerry Coffin
8

Wikipedia pokazuje ładną funkcję skrótu ciągów o nazwie Jenkins One At A Time Hash. Cytuje również ulepszone wersje tego skrótu.

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}
RushPL
źródło
8

Istnieje wiele istniejących implementacji haszujących dla C, od standardowej biblioteki C hcreate / hdestroy / hsearch, po te w APR i glib , które także zapewniają wbudowane funkcje haszujące. Zdecydowanie polecam używanie ich zamiast wymyślania własnej tablicy mieszającej lub funkcji skrótu; zostały mocno zoptymalizowane pod kątem typowych zastosowań.

Jeśli jednak zbiór danych jest statyczny, najlepszym rozwiązaniem jest prawdopodobnie użycie idealnego skrótu . gperf wygeneruje dla Ciebie idealny hash dla danego zbioru danych.

Nick Johnson
źródło
hsearch wyszukuje porównując ciągi lub adres ptr ciągu? Myślę, że to tylko sprawdzenie adresu PTR? Próbowałem użyć różnych wskaźników, ale tej samej skali. hsearch nie powiodło się, informując, że nie znaleziono żadnych elementów
mk ..
3

djb2 ​​ma 317 kolizji dla tego 466k angielskiego słownika, podczas gdy MurmurHash nie ma żadnego dla 64-bitowych haszów i 21 dla 32-bitowych haszów (około 25 należy się spodziewać dla 466k losowych 32-bitowych haszów). Zalecam używanie MurmurHash, jeśli jest dostępne, jest bardzo szybkie, ponieważ zajmuje kilka bajtów na raz. Ale jeśli potrzebujesz prostej i krótkiej funkcji skrótu do skopiowania i wklejenia do swojego projektu, polecam użycie szmerów w wersji jednobajtowej:

uint32_t inline MurmurOAAT32 ( const char * key)
{
  uint32_t h(3323198485ul);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e995;
    h ^= h >> 15;
  }
  return h;
}

uint64_t inline MurmurOAAT64 ( const char * key)
{
  uint64_t h(525201411107845655ull);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e9955bd1e995;
    h ^= h >> 47;
  }
  return h;
}

Optymalny rozmiar tabeli skrótów jest - w skrócie - możliwie największy, a jednocześnie mieści się w pamięci. Ponieważ zwykle nie wiemy lub nie chcemy sprawdzić, ile mamy dostępnej pamięci, a może się to nawet zmienić, optymalny rozmiar tablicy mieszania to około dwukrotność oczekiwanej liczby elementów, które mają być przechowywane w tabeli. Alokacja znacznie większej ilości sprawi, że tabela haszująca będzie szybsza, ale przy szybko malejących zwrotach, co spowoduje, że tabela będzie mniejsza niż ta, spowoduje to wykładnicze spowolnienie. Dzieje się tak, ponieważ istnieje nieliniowy kompromis między złożonością przestrzenną i czasową dla tabel skrótów, przy optymalnym współczynniku obciążenia 2-sqrt (2) = 0,58 ... najwyraźniej.

Wolfgang Brehm
źródło
2

Po pierwsze, czy 40 kolizji dla 130 słów zostało zakodowanych do 0..99? Nie możesz oczekiwać idealnego haszowania, jeśli nie podejmujesz działań, aby to się stało. Zwykła funkcja skrótu przez większość czasu nie będzie miała mniej kolizji niż generator losowy.

Funkcja skrótu o dobrej reputacji to MurmurHash3 .

Wreszcie, jeśli chodzi o rozmiar tabeli skrótów, to naprawdę zależy, jaki rodzaj tablicy masz na myśli, szczególnie, czy kosze są rozszerzalne, czy jednopunktowe. Jeśli łyżki są rozszerzalne, znowu jest wybór: wybierasz średnią długość łyżki dla posiadanej pamięci / ograniczeń prędkości.

Pascal Cuoq
źródło
1
Oczekiwana liczba kolizji z skrótami to n - m * (1 - ((m-1)/m)^n) = 57.075.... 40 kolizji jest lepszych niż można by się spodziewać przypadkowo (46 do 70 przy p-score 0,999). Omawiana funkcja skrótu jest bardziej jednolita, niż gdyby była losowa lub jesteśmy świadkami bardzo rzadkiego zdarzenia.
Wolfgang Brehm
2

Chociaż djb2, jak pokazano na stackoverflow przez cnicutar , jest prawie na pewno lepszy, myślę, że warto również pokazać hashe K&R :

1) Najwyraźniej okropny algorytm haszujący, przedstawiony w pierwszej edycji K&R ( źródło )

unsigned long hash(unsigned char *str)
{
    unsigned int hash = 0;
    int c;

    while (c = *str++)
        hash += c;

    return hash;
}

2) Prawdopodobnie całkiem przyzwoity algorytm haszujący przedstawiony w wersji 2 K&R (zweryfikowany przeze mnie na str. 144 książki); Uwaga: pamiętaj o usunięciu % HASHSIZEz instrukcji return, jeśli planujesz wykonać pomiar modułu do długości swojej tablicy poza algorytmem wyznaczania wartości skrótu. Polecam również wykonanie zwrotu i typu „hashval” unsigned longzamiast simple unsigned(int).

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval % HASHSIZE;
}

Zauważ, że z tych dwóch algorytmów jasno wynika, że ​​jednym z powodów, dla których hash 1.edycji jest tak okropny, jest to, że NIE bierze pod uwagę kolejności znaków w łańcuchach , więc hash("ab")zwróci tę samą wartość co hash("ba"). Jednak nie jest tak w przypadku skrótu drugiej edycji, który zwróciłby (znacznie lepiej!) Dwie różne wartości dla tych ciągów.

Funkcje mieszające GCC C ++ 11 używane dla unordered_map(szablonu tablicy skrótów) i unordered_set(szablonu zestawu skrótów) wyglądają następująco.

Kod:

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}
Gabriel Staples
źródło
2

Wypróbowałem te funkcje skrótu i ​​otrzymałem następujący wynik. Mam około 960 ^ 3 wpisów, każdy o długości 64 bajtów, 64 znaki w innej kolejności, wartość skrótu 32bit. Kody stąd .

Hash function    | collision rate | how many minutes to finish
==============================================================
MurmurHash3      |           6.?% |                      4m15s
Jenkins One..    |           6.1% |                      6m54s   
Bob, 1st in link |          6.16% |                      5m34s
SuperFastHash    |            10% |                      4m58s
bernstein        |            20% |       14s only finish 1/20
one_at_a_time    |          6.16% |                       7m5s
crc              |          6.16% |                      7m56s

Dziwną rzeczą jest to, że prawie wszystkie funkcje skrótu mają 6% współczynnik kolizji moich danych.

Xiaoning Bian
źródło
Chociaż ten link może odpowiedzieć na pytanie, lepiej jest zawrzeć tutaj zasadnicze części odpowiedzi i podać link do odniesienia. Odpowiedzi zawierające tylko łącze mogą stać się nieprawidłowe, jeśli połączona strona ulegnie zmianie.
thewaywewewewewewewby by
Głos za dobrą tabelą, umieszczenie kodu źródłowego każdego z tych skrótów w odpowiedzi jest również niezbędne. W przeciwnym razie linki mogą się zepsuć i pecha.
Gabriel Staples,
Oczekiwana liczba kolizji powinna wynosić 9,112499989700318E + 7 lub 0,103 * 960³, gdyby skróty były naprawdę losowe, więc nie zdziwiłbym się, gdyby znajdowały się wokół tej wartości, ale 0,0616 * 960³ wydaje się trochę nie tak, jakby skróty są rozłożone bardziej równomiernie, niż można by się spodziewać przez przypadek, a przy długości 64 bajtów zdecydowanie należy zbliżyć się do tego limitu. Czy możesz udostępnić zestaw ciągów, który zaszyfrowałeś, abym mógł spróbować go odtworzyć?
Wolfgang Brehm
0

Jedną z rzeczy, których użyłem z dobrymi wynikami, jest następująca (nie wiem, czy została już wspomniana, ponieważ nie pamiętam jej nazwy).

Obliczasz wstępnie tabelę T z losową liczbą dla każdego znaku w alfabecie twojego klucza [0,255]. Haszujesz swój klucz 'k0 k1 k2 ... kN', biorąc T [k0] xor T [k1] xor ... xor T [kN]. Możesz łatwo pokazać, że jest to tak samo losowe, jak twój generator liczb losowych, a jego obliczeniowo bardzo wykonalne, a jeśli naprawdę napotkasz bardzo złą instancję z dużą ilością kolizji, możesz po prostu powtórzyć całość, używając świeżej partii liczb losowych.

Michael Nett
źródło
Jeśli się nie mylę, to cierpi na ten sam problem, co K&R 1st w odpowiedzi Gabriela; tzn. „ab” i „ba” będą miały tę samą wartość.
Johann Oskarsson