3 January 2009

Альтернатива брутфорсу. Текстовый поиск с хеш-функцией

Information Security
Ранее я уже писал об азах текстового поиска, теперь хочу продолжить и написать о том, как развиваются алгоритмы в сторону эффективности.
Итак, как Майкл Рабин и Ричард Карп разогнали алгоритм?


Почему брутфорс такой медленный? Возможно потому, что мы делаем слишком много лишних действий. Тогда появляется идея оптимизировать внутренний цикл. А как? Можно бы сравнивать строки по каким-нибудь числам, их характеризующим.
Такие числа есть, их будем получать с помощью хеш-функции.

Первое приближение


Возможно на ум приходит нечто вроде «вычислим хеш-код для шаблона и для каждой из подстрок, если они одинаковые – здесь совпадение и нашлось».
Попробуем решить проблему написанием своей хеш-функции, а также добавим код, который будет посимвольно сверять подстроку с шаблоном лишь в случае, когда хеш-коды оказались равными. Хеш-функцией строки сделаем просто сумму кодов символов, составляющих эту строку:

private int GetHashOfString(string s)
{
int result = 0;
for (int i = 0; i < s.Length; i++)
{
result += s[i];
}
return result;
}


Сама функция поиска подстроки будет выглядеть так:

public int Match(string input, string pattern)
{
int inputLength = input.Length;
int patternLength = pattern.Length;
int patternHash = GetHashOfString(pattern);
int substringHash;

for (int i = 0; i <= inputLength - patternLength; i++)
{
substringHash = GetHashOfString(input.Substring(i, patternLength));
if (patternHash == substringHash)
{
bool success = true;
for (int j = 0; j < patternLength; j++)
{
if (input[i + j] != pattern[j])
{
success = false;
break;
}
}
if (success)
return i;
}
}
return -1;
}


Разгоняем алгоритм


Опять но: для нахождения хеш-кода на каждой позиции мы совершаем ровно столько же действий, сколько и при брутфорсе. Надо оптимизировать. Наш вариант построения хеша позволяет существенно ускорить его вычисление на каждом последующем шаге: отнять ASCII-код символа, бывшего на нулевой позиции и добавление кода нового символа.

Кольцевое хеширование

Код изменится следующим образом:

...
int patternHash = GetHashOfString(pattern);
int substringHash = GetHashOfString(input.Substring(0, patternLength));

for (int i = 0; i <= inputLength - patternLength; i++)
{
if (i > 0)
substringHash =
substringHash - input[i - 1] + input[i + patternLength - 1];
if (patternHash == substringHash)
...


Продолжаем разгон?


Ещё сильнее разогнать алгоритм можно за счёт использования другой хеш-функции. Одна из таких хэш-функций интерпретирует каждую подстроку как число в некоторой системе счисления, основание которой является большим простым числом.

Запись строки в системе счисления

Как получить на новом шаге значение хеша из предыдущего значения? Так как длина шаблона у нас постоянная, то можно один раз вычислить и запомнить основание в степени длины шаблона за вычетом единицы: maxBase = 61^(length–1). Вместо вычитания значения выкидываемого кода, мы вычитаем его значение, помноженное на maxBase, то есть ‘a’*61^3.
После этого необходимо добавить новый код и помножить полученное значение на основание нашей системы (61).
Это можно записать в виде псевдокода:

substringHash = substringHash - input[i - 1];
substringHash = substringHash + input[i + patternLength - 1];
substringHash = substringHash * base; // base – основание системы


Другой вопрос: а что будет с хешем при большей длине строки (точнее при достаточно большой длине шаблона)? 61 в шестой степени (для длины 7 символов) уже не вмещается в четырёхбайтовое целое.

На помощь приходит «арифметика по модулю». Мы не будем хранить огромные числа, которые невозможно уместить в тридцатидвухразрядный int, мы будем брать их остаток от деления на некое простое число q.
На всякий случай скажу, что «арифметика по модулю» базируется на таких тождествах, как:
(a + b + c) mod x = (a mod x + b mod x + c mod x) mod x
(a * b * c) mod x = (a mod x * b mod x * c mod x) mod x


Реализуем алгоритм


Итак, хеш-функция будет состоять не из суммы кодов символов, помноженных на выбранное основание base в соответствующей степени, а из этой суммы, взятой по модулю q. Значения q и base будем выбирать больше длины алфавита, то есть для ASCII это будет > 256, а для юникода > 65536.

Наша функция для строки s длиной 3 символа будет иметь вид:
((ascii(s[0]) * base^2) mod q + (ascii(s[1]) * base^1) mod q + (ascii(s[2]) * base^0) mod q) mod q

Поскольку длина шаблона во время одного поиска остаётся неизменной, неизменной остаётся и base^(length–1) mod q. Вычисление этой величины вынесем в отдельный метод:

private int GetMaxBase(int length, int q, int b)
{
int result = 1;
for (int i = 0; i < length - 1; i++)
result = (result * b) % q;
return result;
}



Как и ранее, создадим метод для хеш-функции:

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


Теперь сама функция поиска:
public int Match(string input, string pattern, int b, int q)
{
int inputLength = input.Length;
int patternLength = pattern.Length;

находим значение base^(patternLength — 1) по модулю q
int maxBase = GetMaxBase(patternLength, q, b);
предварительно находим хеш-значения для шаблона и первой подстроки
int patternHash = GetHashOfString(pattern, q, b);
int substringHash =
GetHashOfString(input.Substring(0, patternLength), q, b);

for (int i = 0; i <= inputLength - patternLength; i++)
{

если хеш-значения совпали — сравниваем строки полностью
if (patternHash == substringHash)
{
bool success = true;
for (int j = 0; j < patternLength; j++)
{
if (input[i + j] != pattern[j])
{
success = false;
break;
}
}
if (success)
return i;
}

если мы не на последнем шаге, находим новое значение хеш-функции
if (i != inputLength - patternLength)
substringHash =
(b * (substringHash - input[i] * maxBase) +
input[i + patternLength]) % q;

если получилось отрицательное число, делаем его положительным :)
if (substringHash < 0) substringHash += q;
}
return -1;
}


Наконец-то


Вот мы и закончили. Стоит упомянуть, что временные затраты этого алгоритма даже в худшем случае не уступают алгоритму грубой силы, а в среднем на показатели алгорима вполне приятно смотреть.

Надеюсь, что в скором будущем смогу написать о том, в какую сторону двигались другие люди, пытаясь найти эффективные алгоритмы поиска подстроки. Спасибо тем, кто дочитал до конца.

Проект с тестами можно скачать здесь
Tags:текстовый поискалгоритмыалгоритм Рабина-Карпапарсингхеширование
Hubs: Information Security
+53
915 37
Comments 19
SEO-специалист
December 7, 202064,900 ₽Нетология
UX-дизайнер
December 7, 202047,940 ₽Нетология
iOS-разработчик с нуля
December 7, 202070,740 ₽Нетология