Rápida implementación de balanceo de hash

Question

necesito un hash del balanceo para buscar patrones en un archivo. (Estoy tratando de usar el Rabin-Karp string search algorithm).

que comprender cómo un buen Hash obras y cómo un buen balanceo Hash debería funcionar, pero soy incapaz de encontrar la manera de poner en práctica de manera eficiente la división (o multiplicación inversa) al rodar el hash. También leí que rsync usa la versión móvil de adler32, pero eso no parece un hash aleatorio.

Lo ideal sería que será grande si usted me puede apuntar a un/implementación optimizada C C++, pero los punteros en la dirección correcta ayudará.

Answer 1

de Cipher idea de "base primordial" debería funcionar bastante bien - aunque la solución que publicó parece un poco rara.

no creo que haya ninguna necesidad de multiplicación inversa en este método. Aquí está mi solución:

Digamos que la cadena que tenemos hash es "abc", y queremos agregar "d" y quitar "a".

Al igual que Cipher, mi algoritmo de hash básica será:

unsigned hash(const string& s) 
{ 
    unsigned ret = 0; 
    for (int i = 0; i < s.size(); i++) 
    { 
     ret *= PRIME_BASE; //shift over by one 
     ret += s[i]; //add the current char 
     ret %= PRIME_MOD; //don't overflow 
    } 
    return ret; 
} 

Ahora, para implementar deslizamiento:

hash1 = [0]*base^(n-1) + [1]*base^(n-2) + ... + [n-1] 

Nos gustaría añadir algo al final y quite el primer valor , por lo

hash2 = [1]*base^(n-1) + [2]*base^(n-2) + ... + [n] 

En primer lugar podemos añadir la última letra:

hash2 = (hash1 * PRIME_BASE) + newchar; 
=> [0]*base^n + [1]*base^(n-1) + ... + [n-1]*base + [n] 

Luego sólo hay que restar el primer carácter:

hash2 -= firstchar * pow(base, n); 
=> [1]*base^(n-1) + ... + [n] 

Una nota importante: hay que tener cuidado con desbordamiento. Usted puede optar por dejar que se desborde unsigned int, pero creo que es mucho más propenso a la colisión

Aquí está mi aplicación (pero también más rápido!):

#include <iostream> 
#include <string> 
using namespace std; 

const unsigned PRIME_BASE = 257; 
const unsigned PRIME_MOD = 1000000007; 

unsigned hash(const string& s) 
{ 
    long long ret = 0; 
    for (int i = 0; i < s.size(); i++) 
    { 
     ret = ret*PRIME_BASE + s[i]; 
     ret %= PRIME_MOD; //don't overflow 
    } 
    return ret; 
} 

int rabin_karp(const string& needle, const string& haystack) 
{ 
    //I'm using long longs to avoid overflow 
    long long hash1 = hash(needle); 
    long long hash2 = 0; 

    //you could use exponentiation by squaring for extra speed 
    long long power = 1; 
    for (int i = 0; i < needle.size(); i++) 
     power = (power * PRIME_BASE) % PRIME_MOD; 

    for (int i = 0; i < haystack.size(); i++) 
    { 
     //add the last letter 
     hash2 = hash2*PRIME_BASE + haystack[i]; 
     hash2 %= PRIME_MOD; 

     //remove the first character, if needed 
     if (i >= needle.size()) 
     { 
      hash2 -= power * haystack[i-needle.size()] % PRIME_MOD; 
      if (hash2 < 0) //negative can be made positive with mod 
       hash2 += PRIME_MOD; 
     } 

     //match? 
     if (i >= needle.size()-1 && hash1 == hash2) 
      return i - (needle.size()-1); 
    } 

    return -1; 
} 

int main() 
{ 
    cout << rabin_karp("waldo", "willy werther warhol wendy --> waldo <--") << endl; 
} 

Answer 2

de escribir este un tiempo atrás. Está escrito en C# pero está muy cerca de c, solo tendrá que agregar un par de parámetros. Este debería funcionar pero no he probado esta versión, eliminé un par de líneas que ignorarían los caracteres o los caracteres que no son palabras. Espero que esto ayude

private const int primeBase = 101; 
//primeBase^2*[0]+primeBase^1*[1]+primeBase^0*[2] 
//== 
//primeBase*(primeBase*[0]+[1])+[2] 
public static int primeRollingHash(String input, int start, int end) 
{ 
    int acc = 0; 
    for (int i = start; i <= end; i++) 
    { 
     char c = input[i]; 
     acc *= primeBase; 
     acc += c; 
    } 
    return acc; 
} 

public static int primeRollingHash(String input) 
{ 
    return primeRollingHash(input, 0, input.Length - 1); 
} 

public static int rollHashRight(int currentHashValue, String input, 
           int start, int newEnd) 
{ 
    if (newEnd == input.Length) 
     return currentHashValue; 
    int length = newEnd - start - 1; 
    int multiplier = primeBase; 
    char newChar = input[newEnd]; 
    int firstValue = input[start]; 
    if(length>0) 
     firstValue *= length * primeBase; 
    return (currentHashValue - firstValue) * multiplier + newChar; 
} 

Answer 3

Algunos consejos para una implementación rápida:

1. Evitar el módulo n operación (% en C como idiomas) utiliza la máscara n - 1, donde n es 2^k, incluye las operaciones para la búsqueda en la tabla hash. Sí, es posible producir un buen hash con módulos no primos.
2. Escoja multiplicadores y exponentes con buenas figuras de mérito, ver this paper para más detalles.