¿Hay alguna implementación funcional de la función hash rolling utilizada en el algoritmo de búsqueda de cadenas de Rabin-Karp?

Question

Estoy buscando utilizar una función hash rodante para poder tomar hashes de n-grams de una cadena muy grande.

Por ejemplo:

"stackoverflow", dividido en 5 gramos sería:

"pila", "tacko", "ackov", "ckove", "kover", "overf", "verfl", "erflo", "rflow"

Esto es ideal para una función hash rodadura porque después de calculo el primero de n-gramas de hash, los siguientes son relativamente baratos para calcular porque simplemente tiene que soltar la primera letra del primer hash y agregar el nueva última letra del segundo hash.

sé que en general se genera esta función hash como:

H = c un ^{k - 1} + c un ^{k - 2} + c un ^{k - 3} + ... + c _{k a donde a es una constante y c1, ..., ck son los caracteres de entrada.}

Si sigue este enlace en el Rabin-Karp string search algorithm, indica que "a" suele ser un gran primo.

Quiero que mis hashes se almacenen en enteros de 32 bits, entonces, ¿cuán grande debe ser una prima "a", de modo que no desborde mi número entero?

¿Existe una implementación existente de esta función hash en alguna parte que ya podría usar?

---

Aquí es una aplicación que creé:

public class hash2 
{ 

    public int prime = 101; 

    public int hash(String text) 
    { 
     int hash = 0; 

     for(int i = 0; i < text.length(); i++) 
     { 
      char c = text.charAt(i); 
      hash += c * (int) (Math.pow(prime, text.length() - 1 - i)); 
     } 

     return hash; 
    } 

    public int rollHash(int previousHash, String previousText, String currentText) 
    { 

     char firstChar = previousText.charAt(0); 
     char lastChar = currentText.charAt(currentText.length() - 1); 

     int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1)); 
     int hash = (previousHash - firstCharHash) * prime + lastChar; 

     return hash; 
    } 

    public static void main(String[] args) 
    { 
     hash2 hashify = new hash2(); 

     int firstHash = hashify.hash("mydog"); 
     System.out.println(firstHash); 
     System.out.println(hashify.hash("ydogr")); 
     System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr")); 
    } 

} 

estoy usando 101 como mi mejor momento. ¿Importa si mis hashes se desbordarán? Creo que esto es deseable, pero no estoy seguro.

¿Esto parece ser la forma correcta de hacerlo?

Answer 1

Como entiendo que es una minimización de la función:

2^31 - sum (maxchar) * A^kx 

donde maxchar = 62 (por A-Za-z0-9). Acabo de calcularlo por Excel (OO Calc, exactamente) :) y se encontró un máximo de A es 76, o 73, para un número primo.

Answer 2

Recuerdo una implementación ligeramente diferente que parece ser de uno de los libros de algoritmos de sedgewick (también contiene un código de ejemplo - intente buscarlo). He aquí un resumen ajustado a enteros de 32 bits:

se usa aritmética de módulo para evitar que su entero se desborde después de cada operación.

inicialmente SET:

• c = texto ("stackoverflow")
• M = longitud de los "n-gramas"
• d = tamaño de su alfabeto (256)
• q = un primo grande de manera que (d + 1) * q no se desborde (8355967 podría ser una buena opción)
• dM = d ^M-1 mod q

primero calcular el valor hash de la primera de n-gramas:

h = 0 
for i from 1 to M: 
    h = (h*d + c[i]) mod q 

y para cada siguiente de n-gramas:

for i from 1 to lenght(c)-M: 
    // first subtract the oldest character 
    h = (h + d*q - c[i]*dM) mod q 

    // then add the next character 
    h = (h*d + c[i+M]) mod q 

la razón por la que hay que añadir d * q antes de restar el el carácter más antiguo se debe a que podría encontrarse con valores negativos debido a valores pequeños causados ​​por la operación del módulo anterior.

errores incluidos, pero creo que debería tener la idea. Intente encontrar uno de los libros de algoritmos de sedgewick para obtener detalles, menos errores y una mejor descripción. :)

Answer 3

No estoy seguro de cuál es su objetivo aquí, pero si está tratando de mejorar el rendimiento, usar math.pow le costará mucho más de lo que ahorra al calcular un valor de hash móvil.

Le sugiero que empiece por ser simple y eficiente y es muy probable que encuentre que es lo suficientemente rápido.