Rabin-Karp: Пошук у тексті за допомогою конічного хеша

Порівняння чисел замість символів

Найпростіший спосіб знайти шаблон довжиною m у тексті довжиною n — це спробувати кожну початкову позицію та порівнювати символ за символом: O(n*m) у найгіршому випадку. Хитрий трюк 1987 року Рабіна та Карпа полягав у тому, щоб обчислити хеш шаблону один раз і обчислити хеш кожного вікна довжиною m у тексті, а потім порівнювати дешеві цілі числа замість дорогих рядків. Два вікна можуть бути рівними лише якщо їхні хеші рівні, тому майже всі позиції виключаються за допомогою одного порівняння цілих чисел.

Поліноміальне хешування з конічним хешем

Хеш розглядає рядок символів як цифри числа в деяй базі b, зменшену за модулем простого q, щоб вона помістилася в машинне слово:

H(s0 s1 ... s(m-1)) = ( s0*b^(m-1) + s1*b^(m-2) + ... + s(m-1) ) mod q Це точно так само, як ви обчислюєте десяткове значення рядка цифр, лише в базі b з символами як значення цифр і все обгорнуто за модулем q, щоб числа ніколи не переповнювалися.

H(s0 s1 ... s(m-1)) = ( s0*b^(m-1) + s1*b^(m-2) + ... + s(m-1) ) mod q

Переміщення вікна за константною часом (O(1))

Поліноміальна форма обрана спеціально так, щоб хеш вікна можна було оновлювати поступово замість перерахунку з нуля. Переміщення вікна на один символ вправо видаляє внесок лідерної цифри, зміщує всі інші цифри на рівень вверх і додає новий хвостовий символ:

text[i..i+m-1] -> text[i+1..i+m], b^(m-1) попередньо обчислено h = ( (h - text[i] * bPow) * b + text[i + m] ) mod q; if (h < 0) h += q; // підтримуємо невід'ємний залишок Одна множення, одне віднімання, одна додавання, один модуль — однакова постійна вартість незалежно від того, наскільки довгим є шаблон. Саме тому існує Rabin-Karp: наївний перераховуючи кожне вікно коштувало б O(m) на зміщення, знищуючи перевагу хешування взагалі.

// text[i..i+m-1] -> text[i+1..i+m], b^(m-1) precomputed once
h = ( (h - text[i] * bPow) * b + text[i + m] ) mod q;
if (h < 0) h += q;   // keep the remainder non-negative

Основа, модуль і зіткнення, які не зникають

Збіг хешу є кандидатом, а не доказом. Різні рядки можуть зіткнутися на одній самій величині за модулем q, тому реальна реалізація завжди перевіряє символ шаблону посимвово проти зібраного значення перед тим, як повідомляти про збіг — хибні позитивні результати, які просочуються, надзвичайно рідкісні, щоб цей крок перевірки майже ніколи не коштував дорого в середньому. Вибір q як великого простого числа та b як значення, що не пов'язане з розміром алфавіту (або випадкове b під час виконання), запобігає конструкції супротивником тексту, який навмисно зійде на одне й те саме, використання двох незалежних хешів паралельно робить випадкові зіткнення незначними.

Середнє O(n+m), найгірше O(n*m)

З хорошою хешуванням, хеш практично кожного вікна відрізняється від шаблону, тому очікуваний час виконання становить O(n + m): один прохід для хешування тексту та невелика кількість перевірок O(m) для рідкісних справжніх та хибних збігів. Найгірший випадок все ще O(n*m), досягнутий лише в тому випадку, якщо супротивник змушує масові зіткнення — тому алгоритми, такі як Knuth-Morris-Pratt або Z-алгоритм, обидва з найгіршим випадком O(n+m) без використання випадковості, переважно використовуються, коли гарантія важливіша за простоту. Перевага Rabin-Karp проявляється в іншому: оскільки два хеші однакової довжини завжди можна безпосередньо порівняти, він легко узагальнюється для пошуку багатьох шаблонів одночасно шляхом хешування всіх з них у набір для пошуку.

За межами пошуку в тексті

Однакові переміщувані вікна хешу лежать в основі інструментів далеко за межами зіставлення рядків. Виявники плагіату та детектори дублювання вмісту хешують перекриваючись k-грами документа, щоб створити дешевий відбиток пальця. Структурування контентом на основі частин у rsync і системах резервного копіювання з видаленням дублікатів використовує руйнуючий хеш для визначення меж блоків таким чином, щоб вставлення одного байта на початку файлу не переміщував усі блоки після нього — змінюються лише ті блоки, які були змінені. Будь-де, де вам потрібно виявляти рухомий шаблон всередині потоку без повторного сканування всього з нуля, є кандидатом на використання тієї ж хитрості.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Rabin-Karp і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.