Пользователь
0,0
рейтинг
23 апреля 2012 в 23:37

Разработка → Полиномиальные хеши и их применение из песочницы

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

Введение


Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p2s2 +… + pn-1sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Конечно, чтобы сравнить 2 строки, мы можем написать подобную функцию (будем считать, что длины строк s и t совпадают и равны n):

boolean equals(char[] s, char[] t) {
	for (int i = 0; i < n; i++)
		if (s[i] != t[i]) {
			return false;
		}
	}
	return true;
}

Однако в худшем случае эта функция обязана проверить все символы, что дает асимптотику O(n).

Сравнение строк с помощью хешей


Теперь посмотрим, как справляются с этой задачей хеши. Так как хеш — это всего лишь число, для их сравнения нам потребуется O(1) времени. Правда, для того, чтобы посчитать хеш одной подстроки наивным способом, требуется O(n) времени. Поэтому потребуется немного повозиться с математическими формулами и научиться находить за O(n) хеши сразу всех подстрок. Давайте сравним подстроки sL..R и tX..Y (одинаковой длины). Пользуясь определением хеша, мы можем записать:

sL + psL+1 +… + pR-L-1sR-1 + pR-LsR = tX + ptX+1 +… + pY-X-1tY-1 + pY-XtY

Проведем небольшие преобразования в левой части (в правой части все будет происходить аналогично). Запишем хеш подстроки s0..R, он нам понадобится:

hash(s0..R) = s0 + ps1 +… + pL-1sL-1 + pLsL + pL+1sL+1 +… + pR-1sR-1 + pRsR

Разобьем это выражение на две части…

hash(s0..R) = (s0 + ps1 +… + pL-1sL-1) + (pLsL + pL+1sL+1 +… + pR-1sR-1 + pRsR)

… и вынесем из второй скобки множитель pL:

hash(s0..R) = (s0 + ps1 +… + pL-1sL-1) + pL(sL + psL+1 +… + pR-L-1sR-1 + pR-LsR)

Выражение в первой скобке есть не что иное, как хеш подстроки s0..L-1, а во второй — хеш нужной нам подстроки sL..R. Итак, мы получили, что:

hash(s0..R) = hash(s0..L-1) + pLhash(sL..R)

Отсюда вытекает следующая формула для hash(sL..R):

hash(sL..R) = (1 / pL)(hash(s0..R) — hash(s0..L-1))

Аналогично, для второй нашей подстроки будет выполнено равенство hash(tX..Y) = (1 / pX)(hash(t0..Y) — hash(t0..X-1)).

Внимательно глядя на эти формулы, можно заметить, что для вычисления хеша любой подстроки нам необходимо знать лишь хеши префиксов этой строки s0..0, s0..1, ..., s0..n-2, s0..n-1. А, так как хеш каждого следующего префикса выражается через хеш предыдущего, их несложно посчитать линейным проходом по строке. Все сразу за O(n) времени. Степени числа p тоже надо заранее предпросчитать и сохранить в массиве.

Пример кода:

// сохраняем в массиве степени числа p, которые нам могут понадобиться
pow[0] = 1;
for (int i = 1; i <= MAX; i++) {
	pow[i] = pow[i - 1] * p;
}

// считаем хеши префиксов строки s
hs[0] = s[0];
for (int i = 1; i < n; i++) {
	hs[i] = hs[i - 1] + pow[i] * s[i];
}

// считаем хеши префиксов строки t
ht[0] = t[0];
for (int i = 1; i < m; i++) {
	ht[i] = ht[i - 1] + pow[i] * t[i];
}

Казалось бы, мы теперь во всеоружии и умеем сравнивать 2 любые подстроки за O(1). Но не все так просто: математические формулы нуждаются в некоторой доработке. К примеру, подобный код:
if ((hs[R] - hs[L - 1]) / pow[L] == (ht[Y] - ht[X - 1]) / pow[X]) { ... }
работать не будет.
  • Замечание первое: L (или X) может оказаться равным нулю, и при вычислении hs[L - 1] произойдет выход за границы массива. Однако если L равно нулю, то интересующий нас хеш подстроки sL..R хранится в точности в hs[R]. Поэтому правильнее вместо hs[L - 1] писать так:
    L == 0 ? 0 : hs[L - 1]
    .
  • Замечание второе: даже тип long содержит всего 64 бита (я использую Java), а наши строки могут быть длиной в несколько тысяч, и при вычислении хешей неизбежно произойдет переполнение. Эту проблему решить проще всего: надо закрыть на нее глаза. Ну, или почти закрыть: хеши у нас будут считаться, по сути, по модулю 264 (и поэтому не потребуется выполнять операции взятия остатка от деления — красота!). Число p для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 264, т.е. оно должно быть нечетным). Почему так, я здесь рассказывать не буду — об этом можно почитать в книжках по алгебре. Конечно, неизбежно появляется вероятность коллизии, но она крайне мала, поэтому при решении олимпиадных задач можно ей просто пренебречь.
  • Замечание третье: так как все операции мы теперь выполняем по модулю, деление для нас недоступно (точнее, доступно, но писать это довольно неэффективно). Поэтому от него надо избавляться. Делается это довольно просто, способом, который в школе называют «пропорцией»: выражение приводится к общему знаменателю, и вместо деления используется умножение:
    if ((hs[R] - (L == 0 ? 0 : hs[L - 1])) * pow[X] ==
        (ht[Y] - (X == 0 ? 0 : ht[X - 1])) * pow[L]) { ... }
    

Теперь мы более подробно рассмотрим задачи, где можно применять хеши.

Задачи, решаемые с помощью хешей


1. Сравнение подстрок

Первое, и главное, применение, как уже было сказано, это быстрое сравнение двух подстрок — на нем основываются все остальные алгоритмы с хешами. Код в прошлом разделе довольно громоздкий, поэтому я напишу более удобный код, который будет использоваться в дальнейшем.
Следующая функция вычисляет хеш подстроки sL..R, умноженный на pL:
long getHash(long[] h, int L, int R) {
	long result = h[R];
	if (L > 0) result -= h[L - 1];
	return result;
}

Теперь сравнение двух подстрок мы выполняем следующей строчкой:
if (getHash(hs, L, R) * pow[X] == getHash(ht, X, Y) * pow[L]) { ... }

Умножение на степени числа p можно назвать «приведением к одной степени». Первый хеш был умножен на pL, а второй — на pX — значит, чтобы сравнение происходило корректно, их надо домножить на недостающий множитель.
Примечание: имеет смысл сначала проверить, совпадают ли длины подстрок. Если нет, то строки в принципе не могут быть равны, и тогда можно не проверять вышезаписанное условие.

2. Поиск подстроки в строке за O(n + m)

Хеши позволяют искать подстроку в строке за асимптотически минимальное время. Это делает так называемый алгоритм Рабина-Карпа.
Пусть есть строка s длины n, в которой мы хотим найти все вхождения строки t длины m. Найдем хеш строки t (всей строки целиком) и хеши всех префиксов строки s, а затем будем двигаться по строке s окном длины m, сравнивая подстроки si..i+m-1.
Код:
// считаем хеш строки t
long ht = t[0];
for (int i = 1; i < m; i++) {
	ht += pow[i] * t[i];
}

// проверяем все позиции
for (int i = 0; i + m <= n; i++) {
	if (getHash(h, i, i + m - 1) == ht * pow[i]) {
		// обнаружено совпадение на позиции i
	}
}

3. Нахождение z-функции за O(n log n)

Z-функцией строки s называется массив z, i-ый элемент которого равен наидлиннейшему префиксу подстроки, начинающейся с позиции i в строке s, который одновременно является и префиксом всей строки s. Значение z-функции в нулевой позиции будем считать равным длине строки s, хотя некоторые источники принимают его за ноль (но это не критично).

Конечно, есть алгоритм нахождения z-функции за O(n). Но когда его не знаешь или не помнишь (а алгоритм довольно громоздкий), на помощь приходят хеши.

Идея следующая: для каждого i = 0, 1, ..., n-1 будем искать zi бинарным поиском, т.е. на каждой итерации сокращая интервал возможных значений вдвое. Это корректно, потому что равенство s0..k-1 = si..i+k-1 обязательно выполняется для всех k, меньших zi, и обязательно не выполняется для больших k.

Код:
int[] z = new int[n];
for (int i = 0; i < n; i++) {
	int left = 1, right = n - i; // текущий интервал значений
	while (left <= right) {
		// находим middle - середину интервала
		int middle = (left + right) / 2;
		// и проверяем, совпадают ли подстроки s[0..middle-1] и s[i..i+middle-1]
		if (getHash(h, 0, middle - 1) * pow[i] == getHash(h, i, i + middle - 1)) {
			// если совпадают, то ответ как равен минимум middle, и надо проверить большие значения
			z[i] = middle;
			left = middle + 1;
		} else {
			// если не совпадают, надо проверить меньшие значения
			right = middle - 1;
		}
	}
}

4. Поиск лексикографически минимального циклического сдвига строки за O(n log n).

Существует алгоритм Дюваля, который позволяет решать эту задачу за O(n), однако я знаю некоторых довольно сильных олимпиадных программистов, которые так и не разобрались в нем. Пока они будут в нем разбираться, мы снова применим хеши.

Алгоритм следующий. Сначала примем саму строку s за лучший (лексикографически минимальный) ответ. Затем для каждого циклического сдвига с помощью бинарного поиска найдем длину максимального общего префикса этого сдвига и текущего лучшего ответа. После этого достаточно сравнить следующие за этим префиксом символы и, если надо, обновить ответ.
Еще заметим, что для удобства здесь рекомендуется приписать строку s к самой себе — не придется делать операции взятия по модулю при обращениям к символам строки s. Будем считать, что это уже сделано.

Код:
int bestPos = 0;
for (int i = 1; i < n; i++) {
	int left = 1, right = n, length = 0;
	// находим length - длину максимального общего префикса
	while (left <= right) {
		int middle = (left + right) / 2;
		if (getHash(h, bestPos, bestPos + middle - 1) * pow[i] ==
		    getHash(h, i, i + middle - 1) * pow[bestPos]) {
			length = middle;
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
	// сравниваем следующий за общим префиксом символ и обновляем ответ
	// если длина этого префикса равна n,
	// то текущий циклический сдвиг совпадает с минимальным,
	// и ответ обновлять не нужно
	if (length < n && s[i + length] < s[bestPos + length]) {
		bestPos = i;
	}
}

Примечание: по сути, внутри цикла for написан компаратор, сравнивающий лексикографически два циклических сдвига. Используя его, можно за O(n log2 n) отсортировать все циклические сдвиги.

5. Поиск всех палиндромов в строке за O(n log n).

Опять же, существует решение этой задачи за O(n). И опять мы будем решать ее с помощью хешей.

Подстрока sL..R называется палиндромом, если sL = sR, sL+1 = sR-1, и т.д. Если выражаться русским языком, то это означает, что она читается одинаково как слева направо, так и справа налево.

Возможно, вы уже знаете или догадались, при чем тут хеши. Помимо массива h[], содержащего хеши для подстрок s0..0, s0..1, ..., s0..n-2, s0..n-1, посчитаем второй массив rh[] (для «перевернутой» строки), который будем обходить справа налево. Он будет содержать соответственно хеши s0..n-1, s1..n-1, ..., sn-2..n-1, sn-1..n-1:
rh[n - 1] = s[n - 1];
for (int i = n - 2, j = 1; i >= 0; i--, j++) {
	rh[i] = rh[i + 1] + pow[j] * s[i];
}

Должно уже быть понятно, как за O(1) определять, является ли строка палиндромом. Я напишу функцию getRevHash(), аналогичную getHash(), а потом приведу необходимое условие сравнения. Вы можете самостоятельно убедиться в правильности этого выражения, проделав математические выкладки, подобные тем, что приводились в начале статьи.
long getRevHash(long[] rh, int L, int R) {
	long result = rh[L];
	if (R < n - 1) result -= rh[R + 1];
	return result;
}

boolean isPalindrome(long[] h, long[] rh, long[] pow, int L, int R) {
	return getHash(h, L, R) * pow[n - R - 1] == getRevHash(rh, L, R) * pow[L];
}

Теперь рассмотрим позицию i в строке. Пусть существует палиндром нечетной длины d с центром в позиции i (в случае четной длины — с центром между позициями i-1 и i). Если обрезать с его краев по одному символу, он останется палиндромом. И так можно продолжать, пока его длина не станет равной нулю.
Таким образом, нам достаточно для каждой позиции хранить 2 значения: сколько существует палиндромов нечетной длины с центром в позиции i, и сколько существует палиндромов четной длины с центром между позициями i-1 и i. Обратите внимание, что эти 2 значения абсолютно независимы друг от друга, и обрабатывать их надо отдельно.

Применим, как и ранее, бинарный поиск:
int[] oddCount = new int[n];
for (int i = 0; i < n; i++) {
	int left = 1, right = min(i + 1, n - i);
	while (left <= right) {
		int middle = (left + right) / 2;
		if (isPalindrome(h, rh, pow, i - middle + 1, i + middle - 1)) {
			oddCount[i] = middle;
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
}

int[] evenCount = new int[n];
for (int i = 0; i < n; i++) {
	int left = 1, right = min(i, n - i);
	while (left <= right) {
		int middle = (left + right) / 2;
		if (isPalindrome(h, rh, pow, i - middle, i + middle - 1)) {
			evenCount[i] = middle;
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
}

Теперь можно, к примеру, найти общее количество всех палиндромов в строке, или длину максимального палиндрома. Длина максимального нечетного палиндрома с центром в позиции i считается как 2 * oddCount[i] - 1, а максимального четного палиндрома — 2 * evenCount[i].
Еще раз напомню, что нужно быть внимательнее с палиндромами четной и нечетной длины — как правило, их надо обрабатывать независимо друг от друга.

Хеши в матрицах


Наконец, рассмотрим более изощренные применения хешей. Теперь наше пространство будет двумерным, и сравнивать мы будем подматрицы. К счастью, хеши очень хорошо обобщаются на двумерный случай (трехмерных и более я не встречал).

Теперь вместо числа p и массива pow у нас будут два различных числа p, q и два массива pow1, pow2: по одному числу и по одному массиву в каждом направлении: по вертикали и горизонтали.

Хешем матрицы a0..n-1, 0..m-1 будем называть сумму по всем i = 0, ..., n-1, j = 0,..., m-1 величин piqjaij.

Теперь научимся считать хеши подматриц, содержащих левый верхний элемент a00. Очевидно, что hash(a0..0, 0..0) = a00. Почти так же очевидно, что для всех j = 1,..., m-1 hash(a0..0, 0..j) = hash(a0..0, 0..j-1) + qja0j, для всех i = 1,..., n-1 hash(a0..i, 0..0) = hash(a0..i-1, 0..0) + piai0. Это напрямую вытекает из одномерного случая.

Как посчитать хеш подматрицы a0..i, 0..j? Можно догадаться, что hash(a0..i, 0..j) = hash(a0..i-1, 0..j) + hash(a0..i, 0..j-1) — hash(a0..i-1, 0..j-1) + piqjaij. Эту формулу можно получить из следующих соображений: сложим все слагаемые (хеш, напомню, это сумма нескольких слагаемых), составляющие хеш подматриц a0..i-1, 0..j и a0..i, 0..j-1. При этом мы два раза учли слагаемые, составляющие подматрицу a0..i-1, 0..j-1, так что вычтем их, чтобы они учитывались один раз. Теперь не хватает только элемента aij, умноженного на соответствующие степени p и q.

Примерно из тех же соображений, что и в первой части статьи (вы уже заметили причастность формулы включений-исключений?) строится функция для вычисления хеша произвольной подматрицы ax1..x2, y1..y2:
long getMatrixHash(long[][] h, int x1, int x2, int y1, int y2) {
	long result = h[x2][y2];
	if (x1 > 0) result -= h[x1 - 1][y2];
	if (y1 > 0) result -= h[x2][y1 - 1];
	if (x1 > 0 && y1 > 0) result += h[x1 - 1][y1 - 1];
	return result;
}

Эта функция возвращает хеш подматрицы ax1..x2, y1..y2, умноженный на величину px1qy1.

А сравнение двух подматриц aax1..ax2, ay1..ay2 и abx1..bx2, by1..by2 выполняется с помощью следующего выражения:
if (getMatrixHash(h, ax1, ax2, ay1, ay2) * pow1[bx1] * pow2[by1] ==
    getMatrixHash(h, bx1, bx2, by1, by2) * pow1[ax1] * pow2[ay1]) { ... }

Хешами также можно решать задачи, связанные с нахождением самой большой симметричной подматрицы и похожие на них. Причем я не знаю сравнимых с хешами по скорости и простоте алгоритмов, выполняющих эту работу. Здесь используются те же принципы, что и при поиске палиндромов в одномерном случае (т.е. считать «реверснутые» хеши справа налево и снизу вверх, проводить бинпоиск отдельно для подматриц четной и нечетной длины). Предлагаю попробовать решить эту задачу самостоятельно — эта статья вам поможет!

Заключение


Итак, в нашем распоряжении есть довольно неплохой аппарат, позволяющий делать многие вещи либо с лучшей возможной асимптотикой, либо лишь чуть-чуть (в логарифм раз) медленнее, чем специализированные алгоритмы. Неплохо, не так ли?
@bluesky
карма
18,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (41)

  • 0
    Делить нельзя.
    • +4
      Автор не делит, читайте статью.
      • –3
        Да, точно. Стоит воздержаться от кода с делением в таком случае.
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Ну я об этом же.
          • +2
            Обратный элемент по модулю 2^64 может не существовать.
            • +1
              Другими словами, если хочется заниматься делением без задних мыслей, то стоит сам хеш в принципе всюду вычислять по большому простому модулю.
            • +1
              Достаточно, чтобы p было нечетным. Тогда q=1/p существует, и вычисляется элементарно.
              • 0
                Мне другие условия кажутся правильными, но если вы считаете это достаточным, то элементарно найдете обратный элемент для 3 по модулю 9. :-)
                • 0
                  Жаль, что кто-то находит мой комментарий оскорбительным. Я лишь хотел подвести к мысли, что в кольце вычетов по модулю, обратимыми элементами являются числа, взаимно простые с модулем. Собственно, это конструктивно получается из способа нахождения обратного числа, например, расширенным алгоритмом Эвклида. Исходя из этих соображений и предложил модуль брать простым.
                • +1
                  К сожалению, 9, в отличие от 2^64, не является степенью двойки. А обратный элемент (для нечетных p) ищется в 5 строчек:

                  long long Inv(long long p){
                  long long q=p;
                  for(long long a=p*p;a!=1;a*=a) q*=a;
                  return q;
                  }

                  Потому что в Z/2^64Z порядок любого нечетного элемента это степень двойки. А расширенный алгоритм Евклида в этих условиях не очень-то напишешь (очень трудно стартовать, учитывая, что 2^64 в long long не входит).
                  • 0
                    Спасибо, я как-то проскочил ваше обозначение, когда читал, и отчего-то подумал, что P — это модуль. Нечетные числа со степенью двойки, конечно, взаимно просты и все существует.

                    А я правильно понимаю, что ваш код должен бинарно возводить p в степень (2^64-2), как Ферма завещал? А то условие цикла слегка сбивает с толку. %)
                    • 0
                      Дело в том, что порядок любого нечетного элемента в Z264 является степенью двойки. Этот код последовательно перебирает все такие возможности.

                      А вообще можно и возвести в степень 264-2, как мы все привыкли
                      • 0
                        Какие 2^64-2? Теорема Ферма работает только для простых модулей! Тут надо пользоваться теоремой Эйлера (a^phi(p)%p==1), и возводить в степень 2^63-1.
                        • 0
                          Да, вы правы. Надо впредь стараться думать, что пишу, и не делать это одновременно с просмотром футбола
  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Не думаю, что авторы конкурса имели в виду алгоритмы хеширования, сравнение-то быстрое, но самих подстрок слишком много — можно не успеть
    • 0
      Даешь еще больше обсуждений пока идущего соревнования!
  • 0
    А поиск подстроки можно сделать еще и без дополнительного массива? Круто.
    • +1
      Нет, массив для хешей строки s (в которой ищем) нужен; соответствующий кусок кода написан выше.
  • +2
    Зачем? Хватит двух счетчиков. И даже одного:
    если m — длина строки, которую ищем, а p1=p^m, то переход от позиции s к s+1 выглядит так:
    hash1=hash1*p-a[s]*p1+a[s+m];
    (хеш считается «для перевернутой строки», по схеме Горнера).
    • +1
      Действительно, там можно все на ходу пересчитывать, и степени, и хеш. И будет без дополнительного массива. Я об этом никогда не задумывался и писал, как мне проще.
      • 0
        Надо будет написать его для DCPU-16. Никто не разберется! :P
  • –1
    … а я все читаю «Поминальные хэши»…
  • +1
    Замечательная статья!
    Я конечно не раз пользовался такими хешами, но не подозревал, что можно решать с их помощью столько всяких задач=)

    Использовать нечётное число P вместе с модулем M = 2^64 — хорошая идея.
    На самом деле можно использовать любой модуль M при вычислениях. Желательно, чтобы M и P были взаимно простыми (например, P=2 и M=10^9 — совсем плохая идея), а P имело большой порядок по модулю M (например, P=10 и M=10^9+1 — не слишком хороший выбор). Можно использовать хеши по нескольким модулям, если коллизии всё-таки возникают.
    • 0
      А откуда берутся такие рекоммендации? Они универсальны или помогают в каких-то конкретных случаях? Например, не понимаю, почему M и P стоит брать взаимно простыми.
  • –1
    По существу полиномиальный хэш — это представление строки в виде числа в сколькаторичной системе и последующий перевод в десятичную (например в случае отбора геномов (ATCG) удобно использовать пятеричную: ATCGCACA=12343131(5)=121666(10)). Кто на первом курсе матан учил — удивления не испытывает от таких преобразований.
    Полиномиальные хэши мрут аки мухи и улетают так же в переполнение если нам достаются случайные строки юникода (по два байта на символ).
    Так же правило «Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны.» может перестать выполняться если одна из строчек ускакала в переполнение хэша и переполнила достаточно чтобы быть равной второй строчке.
    Хорошо, что автор вспомнил про полиномиальные хэши, но жаль что не указал на их узость применения и ненадежность (пароли бы я в них не хранил точно).
    • 0
      И всё же у одинаковых строк хэши обязательно равны. Другое дело, что строки, хэши которых равны, не обязательно одинаковы.
      • –1
        Если мы пытаемся сравнить строки посредством сравнения хэшей мы можем при равенстве хэшей сказать только «Высока вероятность того что строки равны» и начать сравнивать строки дабы убедится в этом. А если известно равенство строк, то непонятно к чему вычислять для каждой строки хэш по отдельности.
        В общем, искать все слова «фру» в анне карениной методом полиномиальных хэшей — смертельно для системы
        • 0
          Не путайте порядок действий! Когда сравниваются хеши, сами строки еще не начинали сравниваться.
          • –1
            Просто по мне полиномиальные хэши хороши не при сравнении, а при сортировке коротких строчек.
            И порядок я не путаю. просто если есть две строчки по 5 символов сравнивать их хэшами просто непростительно, а если сортировать их с помощью полиномиального хэша — то весьма толково получается. главное полиномы и коды подобрать. Хотя и тут тоже дурость. В общем както непонятно. Могу вас уверить, полиномиальный хэш узкоспециален, как отвертка звездочка. Иногда без него никуда, но обычно он нафиг не нужен обычному человеку.
            • 0
              ДВЕ строки по 5 символов сравнивать — дурость, согласен.
              А вот среди 100500 строк искать пары…

              Или еще пример — хеш-таблица. Ее полезность вы тоже отрицаете?

              Что же насчет узкоспециальности — так тогда почти любой алгоритм/структура данных узкоспециальной получается. Это что, вообще повод не учить их?
              • –1
                Я не говорю что хэши зло и должны быть свалены в кучу и сожжены. Я про то, что автор забыл про то что при вычислении полиномиального хэша нужно учитывать набор символов которые могут входить в строку (это раз) и полиномиальные хэши обладают переменной длинной, что весьма неудобно (это два). Полиномиальные хэши автивно использовались в криптографии еще в докомпьютерные времена, еще до того как дедушка Ньтон свой бином раскрутил, тогда это было здорово и круто. Но давайте не будем пытаться воткнуть паровой движок в наше время. полиномиальные хэши нужны для общего развития, так же как и сортировка пузырьком, но никто не говорит что это круто, здорово и эффективно, хотя и полезно на первых шагах в алгоритмике. Просто не стоит зацикливаться на основах.
                • 0
                  Учитывать набор символов — зачем?! Все, что действительно нужно учитывать — значение p должно быть больше 65535, иначе появятся совсем уж тривиальные коллизии. Что еще нужно учитывать?

                  Сравнивать полиномиальные хеши и сортировку пузырьком — некорректно. Сортировка пузырьком ушла в прошлое с появлением STL с его функцией sort, которая также плавно стала стандартной частью библиотеки любого современного языка. А полиномиальные хеши используются до сих пор.
                  • –1
                    Глупо долбить сразу все. Если у вас генная цепочка в качестве строки с символьными значениями А, Т, Ц, Г — то на кой чет использовать 65535-ричку? Призрак эффективности кода вас не преследует? Зря. Адаптация и оптимизация кода под задачи — не главнейшая цель, но ей так явно пренебрегать не стоит. Кстати если вы не посчитали, то подскаху: 65535 = это 2 в 16-й степени. Тоесть при длине строки в 64 -16=48 символов вы уже упираетесь в переполнение. Так как полиномиальный хэш удобен для работы с подстроками — таким образом вы себе рубите эффективность применения на корню. Так как равенство хэшей уже начинает показывать не равенство строк, а только подозрение на равенство.
                    Кстати паровые двигатели тоже до сих пор используются — с ребенком недавеча собрали. Но в машину к себе я его ставить не буду.
                    А тем кто в реальных приложениях сортировку пузырьком использует — я бы руки отрывал. Кстати sort в некоторых случаях внедрена именно как сортировка пузырьком. Ужас ужас…
                    N^2 его етить.
                    И простите уж за ересь, но MD5, SHA1, CRC32 и другие уже давно и активно используются. Считаются за N, сравниваются за 1, и вообще молодцы.
                    • 0
                      > Тоесть при длине строки в 64 -16=48 символов вы уже упираетесь в переполнение.

                      Вы случайно не забыли, что полиномиальный хеш всегда вычисляется по некоторому модулю? И если этот модуль равен 2^64, то переполнение можно (и нужно) игнорировать?

                      > Так как равенство хэшей уже начинает показывать не равенство строк, а только подозрение на равенство.

                      Разумеется. В том-то и суть хеширования.
                      А то, что назвали вы, называется не хешированием, а упаковкой.

                      > MD5, SHA1, CRC32 и другие уже давно и активно используются

                      Тут согласен. Но полиномиальные хеши еще не ушли. В частности, для тех же самых подстрок их использовать проще, чем CRC32
                      PS А в CRC32 как, равенство хешей означает равенство строк, или нет?
                      • –1
                        При хэшировании пароля несовпадение хэшей разных строк — критичное требование.
                        Признаю что CRC32 — плохой пример.
                        Но всеже я сторонник подхода от артиллерии — снаряд должен соответствовать цели. Не стоит всё пытаться решать одним методом. Следует иметь представление о некотором наборе средств и выбирать наиболее подходящее для решения задачи. Признаю что я из тех маньяков которые впиливают ассемблерные вставки, игнорируют штатные библиотеки в пользу самописных процедур с целью экономии памяти и т.д. Но что тут скажешь — у меня есть оправдание: Тяжелое детство, Спектрум 48к, БК, МК-52, олимпиады по программированию и родители инженеры исковеркали мою жизнь. Возможно я для Вас и моральный урод, но уж такой я есть.
                        • +1
                          Я не понял, вы разрабатываете СКУД с авторизацией по ДНК, что ли?

                          Каким это образом вы так плавно перешли от алфавита ATCG к паролям?

                          > Но всеже я сторонник подхода от артиллерии — снаряд должен соответствовать цели.

                          Не заметил. Автор привел примеры, где использование полиномиального хеша оправдано. Вы начали приводить какие-то свои примеры со странными требованиями к хешу. Да, в ваших случаях полиномиальные хеши не подходят. Но это ваши цели, а цели автора снаряд вполне соответствует.
                          • –1
                            Все мое творчество сводится к двум вещам: к тому что политомиальные хэши узкоспециальны и то что не следует их применять без анализа задачи. Так же я упираю на то что не следует упираться в основание 65535, а по возможности ограничиваться набором используемых символов, а не делать счетчик имени всемогутора. В целом никакой критики автора и полиномиальных хэшей. Хотя да. Они за пиццей не бегают и такси вызвать не могут.
                            Ваше же творчество больше напоминает типичный троллинг.
                            Приношу всем извинения и удаляюсь.
  • 0
    Замечание второе: даже тип long содержит всего 64 бита (я использую Java), а наши строки могут быть длиной в несколько тысяч, и при вычислении хешей неизбежно произойдет переполнение. Эту проблему решить проще всего: надо закрыть на нее глаза. Ну, или почти закрыть: хеши у нас будут считаться, по сути, по модулю 264 (и поэтому не потребуется выполнять операции взятия остатка от деления — красота!).

    так нельзя делать, почему написано тут: codeforces.ru/blog/entry/4898
    • 0
      Да, это правда. Той статьи на codeforces еще не было, когда я публиковал пост. Я постараюсь обновить статью, как время будет.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.