Comments 41
Делить нельзя.
0
Автор не делит, читайте статью.
+4
Да, точно. Стоит воздержаться от кода с делением в таком случае.
-3
UFO just landed and posted this here
Ну я об этом же.
0
Обратный элемент по модулю 2^64 может не существовать.
+2
Другими словами, если хочется заниматься делением без задних мыслей, то стоит сам хеш в принципе всюду вычислять по большому простому модулю.
+1
Достаточно, чтобы p было нечетным. Тогда q=1/p существует, и вычисляется элементарно.
+1
Мне другие условия кажутся правильными, но если вы считаете это достаточным, то элементарно найдете обратный элемент для 3 по модулю 9. :-)
0
Жаль, что кто-то находит мой комментарий оскорбительным. Я лишь хотел подвести к мысли, что в кольце вычетов по модулю, обратимыми элементами являются числа, взаимно простые с модулем. Собственно, это конструктивно получается из способа нахождения обратного числа, например, расширенным алгоритмом Эвклида. Исходя из этих соображений и предложил модуль брать простым.
0
К сожалению, 9, в отличие от 2^64, не является степенью двойки. А обратный элемент (для нечетных p) ищется в 5 строчек:
Потому что в Z/2^64Z порядок любого нечетного элемента это степень двойки. А расширенный алгоритм Евклида в этих условиях не очень-то напишешь (очень трудно стартовать, учитывая, что 2^64 в long long не входит).
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 не входит).
+1
Спасибо, я как-то проскочил ваше обозначение, когда читал, и отчего-то подумал, что P — это модуль. Нечетные числа со степенью двойки, конечно, взаимно просты и все существует.
А я правильно понимаю, что ваш код должен бинарно возводить p в степень (2^64-2), как Ферма завещал? А то условие цикла слегка сбивает с толку. %)
А я правильно понимаю, что ваш код должен бинарно возводить p в степень (2^64-2), как Ферма завещал? А то условие цикла слегка сбивает с толку. %)
0
UFO just landed and posted this here
А поиск подстроки можно сделать еще и без дополнительного массива? Круто.
0
Зачем? Хватит двух счетчиков. И даже одного:
если m — длина строки, которую ищем, а p1=p^m, то переход от позиции s к s+1 выглядит так:
hash1=hash1*p-a[s]*p1+a[s+m];
(хеш считается «для перевернутой строки», по схеме Горнера).
если m — длина строки, которую ищем, а p1=p^m, то переход от позиции s к s+1 выглядит так:
hash1=hash1*p-a[s]*p1+a[s+m];
(хеш считается «для перевернутой строки», по схеме Горнера).
+2
… а я все читаю «Поминальные хэши»…
-1
Замечательная статья!
Я конечно не раз пользовался такими хешами, но не подозревал, что можно решать с их помощью столько всяких задач=)
Использовать нечётное число P вместе с модулем M = 2^64 — хорошая идея.
На самом деле можно использовать любой модуль M при вычислениях. Желательно, чтобы M и P были взаимно простыми (например, P=2 и M=10^9 — совсем плохая идея), а P имело большой порядок по модулю M (например, P=10 и M=10^9+1 — не слишком хороший выбор). Можно использовать хеши по нескольким модулям, если коллизии всё-таки возникают.
Я конечно не раз пользовался такими хешами, но не подозревал, что можно решать с их помощью столько всяких задач=)
Использовать нечётное число P вместе с модулем M = 2^64 — хорошая идея.
На самом деле можно использовать любой модуль M при вычислениях. Желательно, чтобы M и P были взаимно простыми (например, P=2 и M=10^9 — совсем плохая идея), а P имело большой порядок по модулю M (например, P=10 и M=10^9+1 — не слишком хороший выбор). Можно использовать хеши по нескольким модулям, если коллизии всё-таки возникают.
+1
По существу полиномиальный хэш — это представление строки в виде числа в сколькаторичной системе и последующий перевод в десятичную (например в случае отбора геномов (ATCG) удобно использовать пятеричную: ATCGCACA=12343131(5)=121666(10)). Кто на первом курсе матан учил — удивления не испытывает от таких преобразований.
Полиномиальные хэши мрут аки мухи и улетают так же в переполнение если нам достаются случайные строки юникода (по два байта на символ).
Так же правило «Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны.» может перестать выполняться если одна из строчек ускакала в переполнение хэша и переполнила достаточно чтобы быть равной второй строчке.
Хорошо, что автор вспомнил про полиномиальные хэши, но жаль что не указал на их узость применения и ненадежность (пароли бы я в них не хранил точно).
Полиномиальные хэши мрут аки мухи и улетают так же в переполнение если нам достаются случайные строки юникода (по два байта на символ).
Так же правило «Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны.» может перестать выполняться если одна из строчек ускакала в переполнение хэша и переполнила достаточно чтобы быть равной второй строчке.
Хорошо, что автор вспомнил про полиномиальные хэши, но жаль что не указал на их узость применения и ненадежность (пароли бы я в них не хранил точно).
-1
И всё же у одинаковых строк хэши обязательно равны. Другое дело, что строки, хэши которых равны, не обязательно одинаковы.
0
Если мы пытаемся сравнить строки посредством сравнения хэшей мы можем при равенстве хэшей сказать только «Высока вероятность того что строки равны» и начать сравнивать строки дабы убедится в этом. А если известно равенство строк, то непонятно к чему вычислять для каждой строки хэш по отдельности.
В общем, искать все слова «фру» в анне карениной методом полиномиальных хэшей — смертельно для системы
В общем, искать все слова «фру» в анне карениной методом полиномиальных хэшей — смертельно для системы
-1
Не путайте порядок действий! Когда сравниваются хеши, сами строки еще не начинали сравниваться.
0
Просто по мне полиномиальные хэши хороши не при сравнении, а при сортировке коротких строчек.
И порядок я не путаю. просто если есть две строчки по 5 символов сравнивать их хэшами просто непростительно, а если сортировать их с помощью полиномиального хэша — то весьма толково получается. главное полиномы и коды подобрать. Хотя и тут тоже дурость. В общем както непонятно. Могу вас уверить, полиномиальный хэш узкоспециален, как отвертка звездочка. Иногда без него никуда, но обычно он нафиг не нужен обычному человеку.
И порядок я не путаю. просто если есть две строчки по 5 символов сравнивать их хэшами просто непростительно, а если сортировать их с помощью полиномиального хэша — то весьма толково получается. главное полиномы и коды подобрать. Хотя и тут тоже дурость. В общем както непонятно. Могу вас уверить, полиномиальный хэш узкоспециален, как отвертка звездочка. Иногда без него никуда, но обычно он нафиг не нужен обычному человеку.
-1
ДВЕ строки по 5 символов сравнивать — дурость, согласен.
А вот среди 100500 строк искать пары…
Или еще пример — хеш-таблица. Ее полезность вы тоже отрицаете?
Что же насчет узкоспециальности — так тогда почти любой алгоритм/структура данных узкоспециальной получается. Это что, вообще повод не учить их?
А вот среди 100500 строк искать пары…
Или еще пример — хеш-таблица. Ее полезность вы тоже отрицаете?
Что же насчет узкоспециальности — так тогда почти любой алгоритм/структура данных узкоспециальной получается. Это что, вообще повод не учить их?
0
Я не говорю что хэши зло и должны быть свалены в кучу и сожжены. Я про то, что автор забыл про то что при вычислении полиномиального хэша нужно учитывать набор символов которые могут входить в строку (это раз) и полиномиальные хэши обладают переменной длинной, что весьма неудобно (это два). Полиномиальные хэши автивно использовались в криптографии еще в докомпьютерные времена, еще до того как дедушка Ньтон свой бином раскрутил, тогда это было здорово и круто. Но давайте не будем пытаться воткнуть паровой движок в наше время. полиномиальные хэши нужны для общего развития, так же как и сортировка пузырьком, но никто не говорит что это круто, здорово и эффективно, хотя и полезно на первых шагах в алгоритмике. Просто не стоит зацикливаться на основах.
-1
Учитывать набор символов — зачем?! Все, что действительно нужно учитывать — значение p должно быть больше 65535, иначе появятся совсем уж тривиальные коллизии. Что еще нужно учитывать?
Сравнивать полиномиальные хеши и сортировку пузырьком — некорректно. Сортировка пузырьком ушла в прошлое с появлением STL с его функцией sort, которая также плавно стала стандартной частью библиотеки любого современного языка. А полиномиальные хеши используются до сих пор.
Сравнивать полиномиальные хеши и сортировку пузырьком — некорректно. Сортировка пузырьком ушла в прошлое с появлением STL с его функцией sort, которая также плавно стала стандартной частью библиотеки любого современного языка. А полиномиальные хеши используются до сих пор.
0
Глупо долбить сразу все. Если у вас генная цепочка в качестве строки с символьными значениями А, Т, Ц, Г — то на кой чет использовать 65535-ричку? Призрак эффективности кода вас не преследует? Зря. Адаптация и оптимизация кода под задачи — не главнейшая цель, но ей так явно пренебрегать не стоит. Кстати если вы не посчитали, то подскаху: 65535 = это 2 в 16-й степени. Тоесть при длине строки в 64 -16=48 символов вы уже упираетесь в переполнение. Так как полиномиальный хэш удобен для работы с подстроками — таким образом вы себе рубите эффективность применения на корню. Так как равенство хэшей уже начинает показывать не равенство строк, а только подозрение на равенство.
Кстати паровые двигатели тоже до сих пор используются — с ребенком недавеча собрали. Но в машину к себе я его ставить не буду.
А тем кто в реальных приложениях сортировку пузырьком использует — я бы руки отрывал. Кстати sort в некоторых случаях внедрена именно как сортировка пузырьком. Ужас ужас…
N^2 его етить.
И простите уж за ересь, но MD5, SHA1, CRC32 и другие уже давно и активно используются. Считаются за N, сравниваются за 1, и вообще молодцы.
Кстати паровые двигатели тоже до сих пор используются — с ребенком недавеча собрали. Но в машину к себе я его ставить не буду.
А тем кто в реальных приложениях сортировку пузырьком использует — я бы руки отрывал. Кстати sort в некоторых случаях внедрена именно как сортировка пузырьком. Ужас ужас…
N^2 его етить.
И простите уж за ересь, но MD5, SHA1, CRC32 и другие уже давно и активно используются. Считаются за N, сравниваются за 1, и вообще молодцы.
-1
> Тоесть при длине строки в 64 -16=48 символов вы уже упираетесь в переполнение.
Вы случайно не забыли, что полиномиальный хеш всегда вычисляется по некоторому модулю? И если этот модуль равен 2^64, то переполнение можно (и нужно) игнорировать?
> Так как равенство хэшей уже начинает показывать не равенство строк, а только подозрение на равенство.
Разумеется. В том-то и суть хеширования.
А то, что назвали вы, называется не хешированием, а упаковкой.
> MD5, SHA1, CRC32 и другие уже давно и активно используются
Тут согласен. Но полиномиальные хеши еще не ушли. В частности, для тех же самых подстрок их использовать проще, чем CRC32
PS А в CRC32 как, равенство хешей означает равенство строк, или нет?
Вы случайно не забыли, что полиномиальный хеш всегда вычисляется по некоторому модулю? И если этот модуль равен 2^64, то переполнение можно (и нужно) игнорировать?
> Так как равенство хэшей уже начинает показывать не равенство строк, а только подозрение на равенство.
Разумеется. В том-то и суть хеширования.
А то, что назвали вы, называется не хешированием, а упаковкой.
> MD5, SHA1, CRC32 и другие уже давно и активно используются
Тут согласен. Но полиномиальные хеши еще не ушли. В частности, для тех же самых подстрок их использовать проще, чем CRC32
PS А в CRC32 как, равенство хешей означает равенство строк, или нет?
0
При хэшировании пароля несовпадение хэшей разных строк — критичное требование.
Признаю что CRC32 — плохой пример.
Но всеже я сторонник подхода от артиллерии — снаряд должен соответствовать цели. Не стоит всё пытаться решать одним методом. Следует иметь представление о некотором наборе средств и выбирать наиболее подходящее для решения задачи. Признаю что я из тех маньяков которые впиливают ассемблерные вставки, игнорируют штатные библиотеки в пользу самописных процедур с целью экономии памяти и т.д. Но что тут скажешь — у меня есть оправдание: Тяжелое детство, Спектрум 48к, БК, МК-52, олимпиады по программированию и родители инженеры исковеркали мою жизнь. Возможно я для Вас и моральный урод, но уж такой я есть.
Признаю что CRC32 — плохой пример.
Но всеже я сторонник подхода от артиллерии — снаряд должен соответствовать цели. Не стоит всё пытаться решать одним методом. Следует иметь представление о некотором наборе средств и выбирать наиболее подходящее для решения задачи. Признаю что я из тех маньяков которые впиливают ассемблерные вставки, игнорируют штатные библиотеки в пользу самописных процедур с целью экономии памяти и т.д. Но что тут скажешь — у меня есть оправдание: Тяжелое детство, Спектрум 48к, БК, МК-52, олимпиады по программированию и родители инженеры исковеркали мою жизнь. Возможно я для Вас и моральный урод, но уж такой я есть.
-1
Я не понял, вы разрабатываете СКУД с авторизацией по ДНК, что ли?
Каким это образом вы так плавно перешли от алфавита ATCG к паролям?
> Но всеже я сторонник подхода от артиллерии — снаряд должен соответствовать цели.
Не заметил. Автор привел примеры, где использование полиномиального хеша оправдано. Вы начали приводить какие-то свои примеры со странными требованиями к хешу. Да, в ваших случаях полиномиальные хеши не подходят. Но это ваши цели, а цели автора снаряд вполне соответствует.
Каким это образом вы так плавно перешли от алфавита ATCG к паролям?
> Но всеже я сторонник подхода от артиллерии — снаряд должен соответствовать цели.
Не заметил. Автор привел примеры, где использование полиномиального хеша оправдано. Вы начали приводить какие-то свои примеры со странными требованиями к хешу. Да, в ваших случаях полиномиальные хеши не подходят. Но это ваши цели, а цели автора снаряд вполне соответствует.
+1
Все мое творчество сводится к двум вещам: к тому что политомиальные хэши узкоспециальны и то что не следует их применять без анализа задачи. Так же я упираю на то что не следует упираться в основание 65535, а по возможности ограничиваться набором используемых символов, а не делать счетчик имени всемогутора. В целом никакой критики автора и полиномиальных хэшей. Хотя да. Они за пиццей не бегают и такси вызвать не могут.
Ваше же творчество больше напоминает типичный троллинг.
Приношу всем извинения и удаляюсь.
Ваше же творчество больше напоминает типичный троллинг.
Приношу всем извинения и удаляюсь.
-1
Замечание второе: даже тип long содержит всего 64 бита (я использую Java), а наши строки могут быть длиной в несколько тысяч, и при вычислении хешей неизбежно произойдет переполнение. Эту проблему решить проще всего: надо закрыть на нее глаза. Ну, или почти закрыть: хеши у нас будут считаться, по сути, по модулю 264 (и поэтому не потребуется выполнять операции взятия остатка от деления — красота!).
так нельзя делать, почему написано тут: codeforces.ru/blog/entry/4898
так нельзя делать, почему написано тут: codeforces.ru/blog/entry/4898
0
Sign up to leave a comment.
Полиномиальные хеши и их применение