Я хочу использовать функцию хеш-ролика, чтобы я мог принимать хэши n-граммов очень большой строки.
Например:
"stackoverflow", разбитый на 5 граммов, будет:
"stack", "tacko", "ackov", "ckove", "" kover "," overf "," verfl "," erflo "," rflow"
Это идеальное решение для функции хеш-ролика, поскольку после вычисления первого n-граммного хэша следующие вычисления относительно дешевы для вычисления, потому что мне просто нужно отбросить первую букву первого хэша и добавить новую последнюю букву второй хеш.
Я знаю, что в общем случае эта хэш-функция генерируется как:
H = c 1 a k - 1 + c 2 a k - 2 + c 3 a k - 3 +... + c k a 0 где a - константа и c1,...., ck - входные символы.
Если вы следуете этой ссылке в строчном алгоритме поиска Rabin-Karp, в нем говорится, что "a" обычно является большим большим числом.
Я хочу, чтобы мои хэши были сохранены в 32-битных целых числах, поэтому насколько велика простое число "a", так что я не переполняю свое целое число?
Существует ли существующая реализация этой хэш-функции где-то, что я уже мог использовать?
Вот реализация, которую я создал:
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"));
}
}
Я использую 101 как мое основное. Это имеет значение, если мои хеши будут переполняться? Я думаю, что это желательно, но я не уверен.
Это похоже на правильный путь?
