Комментарии 19
А есть еще такая штука: Алгоритм Кнута — Морриса — Пратта, вы в прошлой статье о ней по-моему не упомянали.
Здесь Morris-Pratt algorithm есть даже визуализация, которая помогает понять как идет процесс поиска по этому алгоритму.
Спасибо, жду Кнута-Морриса-Прата и префиксные/суфиксные деревья ;)
про то, как перейти от брутфорса к МП, а от МП к КМП хотел в следующий раз обзор сделать… вот только не знаю — есть ли смысл, поскольку:
1) есть хорошие визуализации, вроде этой (спасибо el777 )
2) немногим это будет полезно
хотя…
я конечно стараюсь писать то, как я это представляю, ознакомившись с другими источниками. может быть кому-то будет интересна мелочь, которую он не замечал (в принципе это и есть повод писать и читать статьи — менять систему отсчёта для знакомых вещей так сказать).
одним словом — попробую написать что-то интересное или неочевидное в давно известном алгоритме
1) есть хорошие визуализации, вроде этой (спасибо el777 )
2) немногим это будет полезно
хотя…
я конечно стараюсь писать то, как я это представляю, ознакомившись с другими источниками. может быть кому-то будет интересна мелочь, которую он не замечал (в принципе это и есть повод писать и читать статьи — менять систему отсчёта для знакомых вещей так сказать).
одним словом — попробую написать что-то интересное или неочевидное в давно известном алгоритме
Перенесите в «Алгоритмы», что ли… Такие вещи достойны того, чтоб появится на главной.
на главной сразу после habrahabr.ru/linker/go/48275/ смотрится отвратно, ИМХО.
Да главное, чтоб было. А то ведь топики из личных блогов потом не найти будет, на сколько я знаю. Да и вообще, что теперь, блог «алгоритмы» не наполнять соответствующим контентом?
хм. мы читаем алгоритмы, а не эстетствуем по поводу оформления итп. Так что не думаю что вот так надо к этому критично относится :)
Плохая хеш функция.
f(ab) == f(ba)
private int GetHashOfString(string s)
{
int result = 0;
for (int i = 0; i < s.Length; i++)
{
result += s[i];
}
return result;
}
И как следствие дополнительный код, который выливается в проверке по символьно.
if (patternHash == substringHash)
{
bool success = true;
for (int j = 0; j < patternLength; j++)
…
Попробуйте в ХФ учитывать позицию символа, а не только его код. Временные затраты будут небольшие, а вот количество ложных проверок уменьшиться.
f(ab) == f(ba)
private int GetHashOfString(string s)
{
int result = 0;
for (int i = 0; i < s.Length; i++)
{
result += s[i];
}
return result;
}
И как следствие дополнительный код, который выливается в проверке по символьно.
if (patternHash == substringHash)
{
bool success = true;
for (int j = 0; j < patternLength; j++)
…
Попробуйте в ХФ учитывать позицию символа, а не только его код. Временные затраты будут небольшие, а вот количество ложных проверок уменьшиться.
Пожалуйста, читайте внимательнее.
Разве умножение кода символа на экспоненциально зависящее от позиции этого самого символа может дать симметричную хеш-функцию?
private int GetHashOfString(string s, int q, int b)
{
int result = 0;
int length = s.Length;
for (int i = 0; i < length; i++)
result = (b * result + s[i]) % q;
return result;
}
Разве умножение кода символа на экспоненциально зависящее от позиции этого самого символа может дать симметричную хеш-функцию?
Что-то я не понимаю, откуда выгода в скорости в алгоритме с такой сложной хеш-функцией, когда надо инициализировать со-процессор, выполнить несколько арифметических операций для каждого символа, ведь количество тактов затраченных на эти действия будет больше, чем количество тактов затраченных на сравнение и условный переход.
Хотя… если думать в рамках быстрого процессорного кеша, содержащего данные от хеш-функции оригинала и сравнения и медленной оперативной памяти, то да, количество доступов к оперативной памяти сильно сокращается
Хотя… если думать в рамках быстрого процессорного кеша, содержащего данные от хеш-функции оригинала и сравнения и медленной оперативной памяти, то да, количество доступов к оперативной памяти сильно сокращается
м-м-м… как бы сказать :)
берём брутфорс: два вложенных цикла. Сложность перемножается. То есть O(n*m), где n — длина строки, а m — длина шаблона.
берём алгоритм Рабина-Карпа: Предварительные вычисления сложности O(m) и потом опять два цикла, причём вложенный практически не запускается в холостую. Если взять base и q очень большими (но всё же простыми) числами, влазящими в int32, то на практике внутренний цикл можно не запускать — с огромной вероятностью совпадение хеш-значений будет свидетельствовать о совпадении строк.
Таким образом, сложность алгоритма в среднем случае O(m+n), что меньше O(m*n). В худшем случае сложность будет O(n*m), хотя вероятность такого случая на практике крайне мала.
берём брутфорс: два вложенных цикла. Сложность перемножается. То есть O(n*m), где n — длина строки, а m — длина шаблона.
берём алгоритм Рабина-Карпа: Предварительные вычисления сложности O(m) и потом опять два цикла, причём вложенный практически не запускается в холостую. Если взять base и q очень большими (но всё же простыми) числами, влазящими в int32, то на практике внутренний цикл можно не запускать — с огромной вероятностью совпадение хеш-значений будет свидетельствовать о совпадении строк.
Таким образом, сложность алгоритма в среднем случае O(m+n), что меньше O(m*n). В худшем случае сложность будет O(n*m), хотя вероятность такого случая на практике крайне мала.
там нет ни одной float-point операции, следовательно, и сопр использоваться не будет.
Согласен поповоду «слабой» хэш функции подбор будет работать быстрее, но хотелось бы увидеть тест для MD5 — сравнение брутфорса и описанного в топике метода, с длиной строки 7-8 символов.
Интересно, в жизни бы до такого не додумался)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Альтернатива брутфорсу. Текстовый поиск с хеш-функцией