Там кто-либо работает реализации прокручивающейся хеш-функции, используемой в алгоритме поиска строки Rabin-Karp?
Я надеюсь использовать прокручивающуюся хеш-функцию, таким образом, я могу взять хеши n-грамм очень большой строки.
Например:
"stackoverflow", разбитый в 5 граммов, был бы:
"стек", "tacko", "ackov", "ckove", "kover", "overf", "verfl", "erflo", "rflow"
Это идеально для прокручивающейся хеш-функции, потому что после того, как я вычисляю первый n-граммный хеш, следующие являются относительно дешевыми для вычисления, потому что я просто должен отбросить первую букву первого хеша и добавить новую последнюю букву второго хеша.
Я знаю, что в целом эта хеш-функция сгенерирована как:
H = c1ak − 1+ c2ak − 2+ c3ak − 3+... + cka0, где константы и 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 в качестве своего начала. Имеет значение, если мои хеши переполнятся? Я думаю, что это желательно, но я не уверен.
Это походит на правильный способ пойти об этом?
3 ответа
Я помню немного другую реализацию, которая, похоже, взята из одной из книг по алгоритмам Седжвика (она также содержит пример кода - попробуйте найти его). вот сводка, скорректированная до 32-битных целых чисел:
вы используете арифметику по модулю, чтобы предотвратить переполнение целого числа после каждой операции.
изначально установлено:
- c = текст ("stackoverflow")
- M = длина "n-граммов"
- d = размер вашего алфавита (256)
- q = большое простое число так что (d + 1) * q не переполняется (8355967 может быть хорошим выбором)
- dM = d M-1 mod q
сначала вычислить хеш-значение первого n -gram:
h = 0
for i from 1 to M:
h = (h*d + c[i]) mod q
и для каждого следующего n-грамма:
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
причина, по которой вы должны добавить d * q перед вычитанием самого старого символа, заключается в том, что вы можете столкнуться с отрицательными значениями из-за небольших значений, вызванных предыдущей операцией по модулю . Включены
ошибки, но я думаю, вы должны уловить идею. попробуйте найти одну из книг по алгоритмам Седжвика, чтобы получить более подробную информацию, меньше ошибок и лучшее описание. :)
Как я понимаю, это минимизация функции для:
2^31 - sum (maxchar) * A^kx
где maxchar = 62 (для A-Za-z0-9). Я только что вычислил его в Excel (OO Calc, точно) :) и максимум A, который он нашел, это 76, или 73, для простого числа.
Хотите стать умным? Не используйте репозитории внутри контроллеров. Вместо этого используйте доменные службы. Это не звучит так плохо, когда вы думаете, что один контроллер интегрирует работу многих служб, не так ли?
-121--2809760-PostgreSQL обычно прослушивает порт 5432, который по умолчанию не открыт в брандмауэре Windows. Но единственная машина, на которой необходимо переконфигурировать брандмауэр, это та, на которой запущен PostgreSQL. Если у вас много клиентских компьютеров, ни один из них не должен требовать изменений брандмауэра (если у них нет ограничений на исходящий трафик, что редко бывает).
Надеюсь, это поможет.
-121--1948966-Не уверен, какова ваша цель, но если вы пытаетесь улучшить производительность, использование math.pow обойдется вам гораздо дороже, чем вы экономите, вычисляя скользящее значение хэша.
Я предлагаю вам начать с того, чтобы оставаться простым и эффективным, и вы с большой вероятностью обнаружите, что это достаточно быстро.