MAXimal | |
добавлено: 11 Jun 2008 10:39 Содержание [скрыть] Алгоритмы хэширования в задачах на строкиАлгоритмы хэширования строк помогают решить очень много задач. Но у них есть большой недостаток: что чаще всего они не 100%-ны, поскольку есть множество строк, хэши которых совпадают. Другое дело, что в большинстве задач на это можно не обращать внимания, поскольку вероятность совпадения хэшей всё-таки очень мала.
Определение хэша и его вычислениеОдин из лучших способов определить хэш-функцию от строки S следующий: h(S) = S[0] + S[1] * P + S[2] * P^2 + S[3] * P^3 + ... + S[N] * P^N где P - некоторое число. Разумно выбирать для P простое число, примерно равное количеству символов во входном алфавите. Например, если строки предполаются состоящими только из маленьких латинских букв, то хорошим выбором будет P = 31. Если буквы могут быть и заглавными, и маленькими, то, например, можно P = 53. Во всех кусках кода в этой статье будет использоваться P = 31. Само значение хэша желательно хранить в самом большом числовом типе - int64, он же long long. Очевидно, что при длине строки порядка 20 символов уже будет происходить переполнение значение. Ключевой момент - что мы не обращаем внимание на эти переполнения, как бы беря хэш по модулю 2^64. Пример вычисления хэша, если допустимы только маленькие латинские буквы: const int p = 31; long long hash = 0, p_pow = 1; for (size_t i=0; i<s.length(); ++i) { // желательно отнимать 'a' от кода буквы // единицу прибавляем, чтобы у строки вида 'aaaaa' хэш был ненулевой hash += (s[i] - 'a' + 1) * p_pow; p_pow *= p; } В большинстве задач имеет смысл сначала вычислить все нужные степени P в каком-либо массиве.
Пример задачи. Поиск одинаковых строкУже теперь мы в состоянии эффективно решить такую задачу. Дан список строк S[1..N], каждая длиной не более M символов. Допустим, требуется найти все повторяющиеся строки и разделить их на группы, чтобы в каждой группе были только одинаковые строки. Обычной сортировкой строк мы бы получили алгоритм со сложностью O (N M log N), в то время как используя хэши, мы получим O (N M + N log N). Алгоритм. Посчитаем хэш от каждой строки, и отсортируем строки по этому хэшу. vector<string> s (n); // ... считывание строк ... // считаем все степени p, допустим, до 10000 - максимальной длины строк const int p = 31; vector<long long> p_pow (10000); p_pow[0] = 1; for (size_t i=1; i<p_pow.size(); ++i) p_pow[i] = p_pow[i-1] * p; // считаем хэши от всех строк // в массиве храним значение хэша и номер строки в массиве s vector < pair<long long, int> > hashes (n); for (int i=0; i<n; ++i) { long long hash = 0; for (size_t j=0; j<s[i].length(); ++j) hash += (s[i][j] - 'a' + 1) * p_pow[j]; hashes[i] = make_pair (hash, i); } // сортируем по хэшам sort (hashes.begin(), hashes.end()); // выводим ответ for (int i=0, group=0; i<n; ++i) { if (i == 0 || hashes[i].first != hashes[i-1].first) cout << "\nGroup " << ++group << ":"; cout << ' ' << hashes[i].second; }
Хэш подстроки и его быстрое вычислениеПредположим, нам дана строка S, и даны индексы I и J. Требуется найти хэш от подстроки S[I..J]. По определению имеем: H[I..J] = S[I] + S[I+1] * P + S[I+2] * P^2 + ... + S[J] * P^(J-I) откуда: H[I..J] * P[I] = S[I] * P[I] + ... + S[J] * P[J], H[I..J] * P[I] = H[0..J] - H[0..I-1] Полученное свойство является очень важным. Действительно, получается, что, зная только хэши от всех префиксов строки S, мы можем за O (1) получить хэш любой подстроки. Единственная возникающая проблема - это то, что нужно уметь делить на P[I]. На самом деле, это не так просто. Поскольку мы вычисляем хэш по модулю 2^64, то для деления на P[I] мы должны найти к нему обратный элемент в поле (например, с помощью Расширенного алгоритма Евклида), и выполнить умножение на этот обратный элемент. Впрочем, есть и более простой путь. В большинстве случаев, вместо того чтобы делить хэши на степени P, можно, наоборот, умножать их на эти степени. Допустим, даны два хэша: один умноженный на P[I], а другой - на P[J]. Если I < J, то умножим перый хэш на P[J-I], иначе же умножим второй хэш на P[I-J]. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать. Например, код, который вычисляет хэши всех префиксов, а затем за O (1) сравнивает две подстроки: string s; int i1, i2, len; // входные данные // считаем все степени p const int p = 31; vector<long long> p_pow (s.length()); p_pow[0] = 1; for (size_t i=1; i<p_pow.size(); ++i) p_pow[i] = p_pow[i-1] * p; // считаем хэши от всех префиксов vector<long long> h (s.length()); for (size_t i=0; i<s.length(); ++i) { h[i] = (s[i] - 'a' + 1) * p_pow[i]; if (i) h[i] += h[i-1]; } // получаем хэши двух подстрок long long h1 = h[i1+len-1]; if (i1) h1 -= h[i1-1]; long long h2 = h[i2+len-1]; if (i2) h2 -= h[i2-1]; // сравниваем их if (i1 < i2 && h1 * p_pow[i2-i1] == h2 || i1 > i2 && h1 == h2 * p_pow[i1-i2]) cout << "equal"; else cout << "different"; Применение хэшированияВот некоторые типичные применения хэширования:
Определение количества различных подстрокПусть дана строка S длиной N, состоящая только из маленьких латинских букв. Требуется найти количество различных подстрок в этой строке. Для решения переберём по очереди длину подстроки: L = 1 .. N. Для каждого L мы построим массив хэшей подстрок длины L, причём приведём хэши к одной степени, и отсортируем этот массив. Количество различных элементов в этом массиве прибавляем к ответу. Реализация: string s; // входная строка int n = (int) s.length(); // считаем все степени p const int p = 31; vector<long long> p_pow (s.length()); p_pow[0] = 1; for (size_t i=1; i<p_pow.size(); ++i) p_pow[i] = p_pow[i-1] * p; // считаем хэши от всех префиксов vector<long long> h (s.length()); for (size_t i=0; i<s.length(); ++i) { h[i] = (s[i] - 'a' + 1) * p_pow[i]; if (i) h[i] += h[i-1]; } int result = 0; // перебираем длину подстроки for (int l=1; l<=n; ++l) { // ищем ответ для текущей длины // получаем хэши для всех подстрок длины l vector<long long> hs (n-l+1); for (int i=0; i<n-l+1; ++i) { long long cur_h = h[i+l-1]; if (i) cur_h -= h[i-1]; // приводим все хэши к одной степени cur_h *= p_pow[n-i-1]; hs[i] = cur_h; } // считаем количество различных хэшей sort (hs.begin(), hs.end()); hs.erase (unique (hs.begin(), hs.end()), hs.end()); result += (int) hs.size(); } cout << result;
|