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

kmp search algorithm

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:

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

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

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

H = c ₁ a ^{k - 1} + c ₂ a ^{k - 2} + c ₃ a ^{k - 3} + ... + c _k a ⁰ donde a es una constante y c1, ..., ck son los caracteres de entrada.

Si sigue este enlace en el algoritmo de búsqueda de cadenas de Rabin-Karp , 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 "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í hay una implementació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, es una minimización de funciones para:

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

donde maxchar = 62 (para A-Za-z0-9 ). Acabo de calcularlo por Excel (OO Calc, exactamente) :) y un máximo de A que encontré 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). aquí hay un resumen ajustado a enteros de 32 bits:

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

inicialmente establecido:

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

primero calcule el valor hash del primer n-gramo:

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

y para cada n-grama siguiente:

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 debe agregar d * q antes de restar el carácter más antiguo es porque puede encontrar valores negativos debido a valores pequeños causados ​​por la operación del módulo anterior.

errores incluidos, pero creo que deberías entender 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 continuo.

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