funkcja skrótu dla ciągu znaków

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ę !

:-)

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;
}

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).

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;
}

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.

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.

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.

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.

• Jest to częściowa odpowiedź na pytanie, jakie są używane funkcje skrótu GCC C ++ 11 , stwierdzając, że GCC używa implementacji „MurmurHashUnaligned2” autorstwa Austina Appleby'ego ( http://murmurhash.googlepages.com/ ).
• W pliku „gcc / libstdc ++ - v3 / libsupc ++ / hash_bytes.cc”, tutaj ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc ) znalazłem wdrożenia. Oto przykład zwracanej wartości „32-bitowy rozmiar_t” (pobrano 11 sierpnia 2017 r.):

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;
}

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.

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.