Блог пользователя Burunduk1

Автор Burunduk1, 10 лет назад, По-русски

Добрый день.

Это пост о мелочах в реализации хешей.

Сегодня ребята гуглили "как писать полиномиальные хеши", но нагулили лишь две ссылки на тему "как не надо писать полиномиальные хеши" — e-maxx и habr.

А можно писать иначе — short и full. Последняя версия устойчива к антихеш тестам, её можно копипастить.

Теперь подробно. Есть два способа. Оба для краткости будут написаны по модулю 264, то есть падают на строке Туе-Морса.

Общая часть:

const int P = 239017; // Если брать простой модуль, здесь стоит писать rand()!
// s - строка, n - её длина

Первый способ (я пишу так):

// deg[] = {1, P, P^2, P^3, ...}
// h[] = {0, s[0], s[0]*P + s[1], s[0]*P^2 + s[1]*P + s[2], ...}
unsigned long long h[n + 1], deg[n + 1];
h[0] = 0, deg[0] = 1;
for (int i = 0; i < n; i++) {
  h[i + 1] = h[i] * P + s[i];
  deg[i + 1] = deg[i] * P;
}
auto get_hash = [&]( int l, int r ) { // [l..r]
  return h[r + 1] - h[l] * deg[r - l + 1];
};

Второй способ:

// deg[] = {1, P, P^2, P^3, ...}
// h[] = {s[0], s[0] + s[1]*P, s[0] + s[1]*P + s[2]*P^2, ...}
unsigned long long h[n], deg[n];
h[0] = s[0], deg[0] = 1;
for (int i = 1; i < n; i++) {
  deg[i] = deg[i - 1] * P;
  h[i] = h[i - 1] + s[i] * deg[i];
}
auto get_hash = [&]( int l, int r ) { // [l..r]
  if (l == 0)
    return h[r];
  return h[r] - h[l - 1];
};

Отличия здесь два

Направление s0Pn - 1 + s1Pn - 2 + ... + sn - 1 или s0 + s1P + s2P2 + ... + sn - 1Pn - 1?

В первом способе, чтобы сравнить две строки [l1..r1] и [l2..r2], достаточно написать get_hash(l1, r1) == get_hash(l2, r2). То есть, функция get_hash честно возвращает хеш. Можно, например, найти количество различных подстрок, положив все хеши в хеш-таблицу.

Во втором случае функция get_hash на самом деле возвращает не хеш, а хеш, домноженный на некоторую степень P, поэтому придётся писать так deg[r2] * get_hash(l1, r1) == deg[r1] * get_hash(l2, r2) (на e-maxx правда чуть страшнее). А использовать хеши иначе не получится. Можно модифицировать функцию get_hash, использовать честный хеш true_hash(l, r) = deg[n - r - 1] * get_hash(l, r), но у такого способа есть минус — мы предполагаем, что знаем максимальную длину строки. Это не всегда удобно, а при онлайн-решениях иногда и не правда.

У второго способа ещё есть вариация с делением по модулю. Так писать точно не нужно.

С чего начинать массив h? С 0 или с s[0]?

Если мы начинаем с 0, мы получаем более короткий и быстрый код (да, да, чтобы if-у выполниться, нужно время!). Оценивая скорость, заметьте, что умножений будет столько же.

Если же мы начинаем в s[0], то получаем массив длины n, то есть экономим O(1) памяти.

Как лучше, решайте сами. Я всем рекламирую первый вариант. Если есть конструктивные замечания или альтернативные версии, буду рад услышать.

Выбор простого модуля

Отдельный привет всем, кто говорит "число P можно выбирать любым". P должно быть больше размера алфавита. Если это так, то хеш, вычисленный без взятия по модулю, как длинное число, инъективен. Иначе уже на этапе вычисления без модуля могут быть коллизии. Примеры, как нельзя делать: алфавит "a..z", P = 13, алфавит ASCII 33..127, P = 31.

P.S. Кстати, как правильно пишется "хеш", или "хэш"? Моя версия — "хеш".

UPD: Подсказывают, что, если писать без unsigned, получится Undefined Behaviour. Спасибо Лёше Левину.

UPD: Чтобы хеш точно нельзя было сломать, можно точку P выбирать как max(Σ, rand()). Версия full пропатчилась. Спасибо Kaban-5, nk.karpov.

  • Проголосовать: нравится
  • +127
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Скажите, а почему нельзя писать хеши как на e-maxx?

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

А где же эталонный вариант, как писать надо, чтоб хэши не падали, в том числе и на строке Туэ-Морса?

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Сейчас еще модно делать защиту от взломов на CF: 2 модуля выбирать не 109 + 7 и 109 + 9, а два рандомных больших простых числа)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Скажите, а почему именно 2 модуля?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну нужно >=2 чтобы не случилось просто коллизии случайно. Можно брать и больше, просто тогда программа будет работать дольше)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    А как бы их покороче ещё сгенерить эти два случайных простых числа...

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну мы обычно делали так: шли циклом от 10^9 и проверяли чила на простоту за корень. Как только сгенили приличное число простых(~10), выбираем из них 2 рандомных различных.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        Почему бы просто не тыкать в случайные большие числа и проверять на простоту? Кажется, это должно не сильно долго работать. А то может найтись маньяк, который заранее нагенерит 45 котрпримеров для всех пар 10 простых(Интересная идея! Надо будет попробовать поманьячить).

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +19 Проголосовать: не нравится

          Как маньяк узнает, какую под какую пару пускать тест в ход, если пара случайно выбирается?

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Ну если задача специфичная, то он может эти примеры склеить друг с другом

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Можно просто выбрать случайное число и от него искать следующее простое

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Так может зашить штук 10, а потом случайно 2 из них выбрать?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Как будто эти два не рандомные)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Казалось бы, зачем случайный модуль, если я могу взять случайную точку.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Хм, да, так вроде проще. Круто)

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Казалось бы зачем два простых модуля, когда можно взять один 10e18 + 3 :)

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +17 Проголосовать: не нравится

          По нему перемножать дольше? Я умею только через long double, который не везде есть.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            В gcc есть __int128. Правда, я только слышал о нём, но ни разу не пользовался.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Он есть ещё в меньшем числе мест.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                а где вообще есть? я уже не первый раз вижу, но никогда не удовалась скомпилировать такой код. Нужны какие-то спе библиотеки??

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 лет назад, # ^ |
                    Проголосовать: нравится +29 Проголосовать: не нравится

                  Нужна 64-битная версия gcc. Например, под Windows это может быть tdm-gcc-64.

»
10 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

А зачем брать точку простой? Нужно лишь брать точку с большим порядком по модулю основания хэша, в идеале первообразный корень (конечно, больший размера алфавита). Эти вещи, как я понимаю, слабо коррелируют.

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Вы меня простите, но точку надо брать случайной (написать в коде rand()), тогда всё будет нормально работать. Иначе любому хэшу, можно легко подобрать коллизию. Я умею строить например для модулей порядка 1e36 не слишком большой тест из двух букв, за разумное время.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    А можешь подробнее рассказать, как его строить?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Коля скорее всего имеет в виду метод Капуна

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

          Насколько я понял, Коля говорит так

          1. Если и точка, и модуль детерминированы, то легко ломать (по ссылке алгоритм)

          2. Значит, нужны или случайная точка, или случайный модуль. Случайную точку брать проще, так как она не обязана быть простой.

          UPD: (s0 + s1 * P) % M. Здесь M — модуль, а P — точка, которую мы подставляем в многочлен.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Понятно. Просто мне, как человеку, который пишет на джаве, можно воспользоваться функцией nextProbablePrime у BigInteger, поэтому я в последнее время делаю модуль случайным простым, а точку константой.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        В первом приближении да, но когда элементов становится мало (<40) можно в лоб перебирать все подмножества. Это заметно уменьшает размер теста.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        А можно этот метод чуточку поподробнее описать?

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +22 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Спасибо!

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится

            А есть какое-нибудь объяснение, почему это работает и с какой асимптотикой?

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится +40 Проголосовать: не нравится

              Мы хотим сгенерить 2 строки длины n над алфавитом {a, b}, у котороых (P, M) хеш одинаковый. Hash(s0s1...sn - 1) == Hash(t0t1...tn - 1) ⇔ ΣiPicoefi = 0 (mod M). Здесь coefi ∈ {-1, 0, +1}.

              Осталось найти такие коэффициенты.

              Возьмём a0 = {P0 mod M, P1 mod M, ... Pn - 1 mod M}.

              Мы верим, что a0 содержит n случайных равномерно распределённых чисел от 0 до M.

              Теперь из ai получим ai + 1.
              Диапазон чисел в ai обозначим за Mi (M0 = M).

              1. b = Sorted(ai).
              2. ai + 1 = {b[1] — b[0], b[3] — b[2], ...}

              Длина ai + 1 в два раза меньше, чем длина ai.
              Поскольку b[i+1] — b[i] ≈ Mi/n, то диапазон массива ai + 1 примерно в n раз меньше диапазона массива ai.

              Мы верим, что если числа в ai распределены равномерно, то и числа в ai + 1 распределены примерно равномерно.

              Алгоритм завершается, как только b[0] = 0.

              Оцени n при котором диапазон успеет сойтись от M к единице: n(n/2)(n/4)(n/8)... ≥ M ⇔ nlogn / 21 + 2 + ... + logn ≥ M ⇔ 2log2n - logn(logn + 1) / 2 ≥ M ⇔ 2log2n / 2 ≥ M ⇔ logn ≥ n.

              Подставляем M = 1018, получаем n ≥ 2048.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится +8 Проголосовать: не нравится

                Круто, спасибо!

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                Rev. 7   Проголосовать: нравится +1 Проголосовать: не нравится

                Позволь позанудничать. В своей оценке ты дважды делаешь преобразования не тождественные, а приводящие к более сильным неравенствам, поэтому знак должен быть не ⇔, а ⇐ или ∵. Тождественно вот так (по-прежнему предполагая, что n есть степень двойки):

                Правда, после округления до степени двойки для M = 1018 всё равно получается n ≥ 2048.

                А логарифм в ТеХе пишется так: \log.

                …А вообще за объяснение спасибо!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

                  Спасибо за строгую версию рассуждений =)

                  А логарифм в ТеХе пишется так

                  Мне не нравится вёрстка tex-а на CF, без нужды стараюсь tex-ом здесь не пользоваться.

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

У меня есть конструктивное замечание: зачем вообще упомянут второй способ, если он во всех отношениях хуже?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Валер, а ты переходил по ссылкам на хабр и емакс? Только поэтому. Потому что многие так пишут.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Да, переходил, конечно. То есть, чтобы показать, чем этот вариант плох? Окей.

»
10 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

Вот так лучше вообще не делать, так как без srand() это бесполезно, иначе работает неправильно с вероятностью под Windows, где Σ — размер алфавита, то есть почти гарантированно упадёт на каком-нибудь тесте.

Кстати, если уж так хочется избежать взлома, то инициализроваться надо не от time(), а от чего-то, что может принимать очень много разных значений за короткий промежуток времени, так как взломщик-маньяк может склеить контрпримеры для всех значений time() на минуту вперёд.

P. S. Первое замечание уже поправили, но как-то не очень надёжно выглядит...

P. P. S. "почти гарантированно упадёт на каком-нибудь тесте" — неправда, туплю, вероятность значима только есть тестов 2000 или больше.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Насколько я понимаю, если модуль простой, P можно брать любым больше Σ. Почему нет? У меня в коде стоит max(239, rand()). В посте сейчас тоже поправлю.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      Когда я начинал писать комментарий, было просто rand(). Второй пункт всё равно в силе, да и max(239, rand()) очень часто бывает равным 239.

      UPD: Ок, я идиот, нужно тестов 200 конкретно против точки 239, чтобы это упало с хорошей вероятностью.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +21 Проголосовать: не нравится

        Ну ооочень часто :D

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        В нормальных системах rand() возвращает число из [0, 231 - 1], если писать хэши по двум модулям и брать основания независимо, то вероятность события которое описанно  < 10 - 15. Но если быть совсем честным, можно использовать то, что лежит в random, говорят там генераторы случайных чисел написанны хорошо.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Если есть С++11, то можно делать так: srand(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now() - chrono::high_resolution_clock::time_point()).count()).

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      #include <x86intrin.h>
      srand(rdtsc());
      

      И под MSVC

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      хотел написать, что в C++11 есть std::random_device, но выяснилось, что в MinGW этот класс всегда возвращает одни и те же числа.

      Кстати, high_resolution_clock в MinGW тоже не совсем "high resolution": возвращает время с точностью только до микросекунд, а не до нано.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ничего себе! Интересно, в libstdc++ примут патчи, исправляющие это безобразие добавлением специального кода для Windows?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        FWIW, код std::random_device из libc++ подсказывает, что на Windows можно использовать функцию rand_s.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

      Чуть короче:

      srand(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count())
      
»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +42 Проголосовать: не нравится

Есть небольшое общее замечание, пока у меня не получается сделать из него что-либо конкретное. Речь идет об оценке вероятности ошибки сравнения строк для реализации, в которой рандомизируется MUL и фиксируется MOD в полиномиальном хеше.

Для начала, несколько общих моментов. Пусть P(x) — многочлен степени n по модулю p (разницу hash(s1) — hash(s2) можно рассматривать как такой многочлен).

Несколько утверждений:
1. Вероятность того, что заданный x является корнем случайного многочлена P равна 1/p (является корнем при ровно одном свободном члене).
2. Среднее количество различных корней многочлена P равно 1 (предыдущее утверждение суммируется по всем x).
3. В худшем случае число корней многочлена P равно n.

Таким образом, для полиномиального хеша при случайном MUL для случайных различных строк s1 и s2 вероятность равенства hash(s1)=hash(s2) равна 1/MOD, а в худшем случае относительно s1 и s2 данная вероятность равна max(|s1|,|s2|)/MOD. В общем, худший случай существенно отличается от среднего.

Если получится построить пример для приложенного кода lcp такой, что все сравнения будут проходить по худшему случаю, вероятность провала каждого запроса lcp будет иметь порядок |s|^2/(p1*p2).

К сожалению, построение многочлена, имеющего много корней в ограничениях на коэффициенты многочлена наталкивается (на моем уровне знаний алгебры) на технические сложности. Если я правильно считаю оценки, вероятность того, что при k << p случайный многочлен имеет k различных корней равна (1/k!), т.е. случайная генерация не приводит к результату. Единственное известное мне достаточно быстрое построение многочлена в ограничениях на коэффициенты, имеющего один заданный корень (тот-самый-алгоритм-с-разностями), дает степень порядка , что существенно выше степени минимального такого многочлена и, похоже, неприменимо для задачи. В общем, нужны дальнейшие исследования.

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

На всякий случай хочу проверить: правильно ли я понимаю, что при простых модулях точку можно брать любую, большую размера алфавита (или большую или равную?) и меньшую каждого модуля? И что 239 в твоём коде — это просто красивое число, большее любого встречаемого в задачах алфавита, но его спокойно можно заменить на, например, 256 или real_alphabet_size+1?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, всё так.

    P.S. С вероятностью правда непонятки. I_love_natalia разбирался, но вопросы остались.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А почему " если писать без unsigned, получится Undefined Behaviour " ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Потому что переполнение знаковых типов (например, int или long long) — undefined behavior по стандарту языка.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Можете привести небольшой пример на коллизию

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Здравствуйте! Хотелось бы узнать правильно ли я рассуждаю: при нахождении хеша подстроки в том варианте, котором используете вы, там вычитание двух хешей return h[r + 1] — h[l] * deg[r — l + 1] после данной операции ответ будет по модулю 2^64, получим ли мы при этом правильный ответ? Дело в том что на некоторых сайтах предлагается к ответу прибавить base: h = ((hash[r] — hash[l — 1] * pow[r — l + 1]) % base + base) % base, обязательно ли это?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    если делать в unsigned long long, как написано здесь, это необязательно. если же модуль будет другой, то так делать нужно

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А может кто-нибудь сюда скинуть коды невзламываемых реализаций хэша с acm.math.spbu? А то не открывается почему-то сайт

upd. заработал

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

А где можно найти объяснение работоспособности формулы, используемой в первом способе?

h[r + 1] - h[l] * deg[r - l + 1];

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно выписать, что за многочлены хранятся в этих двух позициях в массиве h, а потом вычесть один из другого.