Y a-t-il des implémentations de travail de la fonction de hachage roulante utilisée dans l'algorithme de recherche de chaîne Rabin-Karp?

Question

Je cherche à utiliser une fonction de hachage roulant afin que je puisse prendre des hachages de n-grammes d'une très grande chaîne.

Par exemple:

"stackoverflow", divisé en 5 grammes serait:

"pile", "tacko", "ackov", "ckove", "kover", « overf », « verfl », « erflo », « rflow »

Ceci est idéal pour une fonction de hachage de roulement car après je calcule le premier hachage n-gramme, les suivantes sont relativement pas cher pour calculer parce que je il suffit de laisser tomber la première lettre du premier hachage et ajouter le nouvelle dernière lettre du deuxième hash.

je sais qu'en général cette fonction de hachage est généré en tant que:

H = c un ^{k - 1} + c un ^{k - 2} + c un ^{k - 3} + ... + c _k un où a est une constante et c1, ..., ck sont les caractères d'entrée.

Si vous suivez ce lien sur le Rabin-Karp string search algorithm, il indique que "a" est généralement un grand premier. Je veux que mes hachages soient stockés dans des entiers de 32 bits, donc quelle doit être la taille "a", de sorte que je ne déborde pas de mon entier?

Existe-t-il une implémentation existante de cette fonction de hachage quelque part que je pourrais déjà utiliser?

---

Voici une implémentation que j'ai créé:

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

} 

J'utilise 101 comme mon premier. Est-ce important si mes hachages vont déborder? Je pense que c'est souhaitable mais je ne suis pas sûr.

Est-ce que cela semble être la bonne façon de procéder?

Answer 1

Comme je comprends que c'est une minimisation de fonction pour:

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

où maxchar = 62 (pour A-Za-z0-9). Je viens de le calculer par Excel (OO Calc, exactement) :) et un max A qu'il trouve est 76, ou 73, pour un nombre premier.

Answer 2

Je me souviens d'une implémentation légèrement différente qui semble provenir d'un livre d'algorithmes de sedgewick (il contient aussi un exemple de code - essayez de le chercher). voici un résumé ajusté aux entiers 32 bits:

vous utilisez l'arithmétique modulo pour empêcher votre entier de déborder après chaque opération.

initialement fixé:

• c = text ("stackoverflow")
• M = longueur des "n-grammes"
• d = taille de votre alphabet (256)
• q = un grand prime pour que (d + 1) * q ne déborde pas (8.355.967 pourrait être un bon choix)
• dM = d ^M-1 q mod

premier calcul de la valeur de hachage du premier n-gramme:

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

et pour chaque n-gramme suivant:

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 raison pour laquelle vous devez ajouter d * q avant de soustraire la le caractère le plus ancien est parce que vous pourriez rencontrer des valeurs négatives dues aux petites valeurs provoquées par l'opération modulo précédente.

erreurs incluses mais je pense que vous devriez avoir l'idée. essayez de trouver l'un des livres d'algorithmes de sedgewick pour plus de détails, moins d'erreurs et une meilleure description. :)

Answer 3

Vous ne savez pas quel est votre objectif ici, mais si vous essayez d'améliorer les performances, l'utilisation de math.pow vous coûtera beaucoup plus cher que vous économisez en calculant une valeur de hachage.

Je vous suggère de commencer par rester simple et efficace et vous trouverez très probablement que c'est assez rapide.