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