STR Строки и тексты Алгоритм
Алгоритм Рабина — Карпа
Также: Rabin–Karp algorithm · Karp–Rabin · алгоритм Карпа — Рабина · поиск по отпечаткам · fingerprint string matching
Поиск по отпечаткам: хеш окна катится по тексту за три действия на букву, а буквы сравниваются только там, где хеш окна совпал с хешем образца. Один образец так ищут нечасто — для этого есть способы быстрее. Сила алгоритма в другом: тысячи образцов одной длины ищутся за один проход, и на этом стоят программы, которые находят копии в коде и в текстах.
Сцены этого каталога пишут разные авторы, и иногда функция переезжает из файла в файл копированием. Найдём все такие куски. Каждое окно в 60 знаков каждого файла — больше шестисот тысяч окон — получает отпечаток, полиномиальный хеш, и окна с одинаковыми отпечатками в разных файлах сравниваются буквами. Слева — матрица: какая доля каждого файла встречается в каждом другом. Справа — два файла друг против друга: точка — общее окно, скопированный кусок — диагональ. Нажимайте на клетки матрицы, меняйте длину окна и модуль.
Возьмём пару, которая открывается первой: dijkstra.js, сцену статьи об алгоритме Дейкстры, и dynamic-programming-intro.js, сцену вводной статьи о динамике. Из 20 213 окон первого файла 2750 есть во втором, они складываются в 32 куска, всего 4638 знаков. Самый длинный, 528 знаков, — функция marker, которая рисует на карте булавку с буквой A или B. Второй, 426 знаков, расставляет подписи на карте так, чтобы они не наезжали друг на друга. Третий, 381 знак, — свой переключатель seg, хотя в общей библиотеке сайта такая функция уже есть. Это и есть отчёт программы поиска копий: что вынести в общий модуль.
Посмотрите на счётчик ложных тревог. Даже при модуле 2³¹ − 1 одна нашлась: два разных окна этих файлов получили один отпечаток. Переключите модуль на 10⁵ + 3: общих окон столько же, 2750, а ложных тревог уже 4300 — разных окон с одинаковым отпечатком. Каждую ловит проверка буквами, поэтому ответ не меняется, меняется только работа. Так устроен весь алгоритм Рабина — Карпа: хеш быстро отсеивает почти всё, а буквы сравниваются только там, где он сказал «может быть».
Идея
Сравнивать с образцом не окно текста, а его отпечаток — число. Отпечаток окна, сдвинутого на одну букву, получается из предыдущего за три действия: убрать вклад ушедшей буквы, умножить на основание, прибавить пришедшую. Где отпечатки разные, окно точно не образец. Где равны, окно скорее всего образец, и это проверяют буквами. Образцов может быть много: их отпечатки кладут в хеш-таблицу, и тот же один проход по тексту ищет все сразу.
Отпечаток — полиномиальный хеш: окно ts…ts+m−1 читается как число в системе с основанием b и берётся по модулю простого p. Если hs — отпечаток окна с позиции s, то
$$h_{s+1} = \bigl((h_s - t_s \cdot b^{m-1})\cdot b + t_{s+m}\bigr) \bmod p.$$Степень bm−1 по модулю p считают один раз заранее. Совпадение hs с отпечатком образца называют попаданием, а попадание, при котором буквы всё-таки разные, — ложной тревогой.
Окно едет по тексту
Ниже окно из шести букв ищет «Наташу» в коротком куске первой части «Войны и мира», где она встречается трижды. Под каждой буквой — столбик окна, которое с неё начинается. Модуль можно взять смешно маленьким, 13 или 101, чтобы ложные тревоги было видно глазами.
При p = 13 отпечаток — число от 0 до 12, и окно получает отпечаток «Наташи» примерно в каждом тринадцатом случае. Листинг ниже прогоняет поиск по всей первой части романа, 244 495 окон:
p found hash hits false expected false
13 42 18686 18644 18804.1
101 42 2537 2495 2420.3
10007 42 54 12 24.4
2147483647 42 42 0 0.0
Вхождений всегда 42 — проверка буквами не даёт ошибиться. Меняется только число ложных тревог, и оно идёт за формулой: около (число окон − число вхождений)/p. При модуле 2³¹ − 1 ложных тревог нет ни одной, и буквы сравниваются только там, где «Наташа» действительно есть.
Почему это верно и быстро
Алгоритм Рабина — Карпа с проверкой буквами находит все вхождения образца и только их. Если основание b выбрано случайно из 0, …, p − 1 и p — простое, большее кода любой буквы, то ложных тревог в среднем не больше (n − m + 1)(m − 1)/p, и ожидаемое время работы — O(n + m + occ · m), где occ — число вхождений, если p ≥ n · m.
Равные строки дают равные отпечатки, поэтому ни одно вхождение не пропущено; любое попадание проверяется буквами, поэтому ни одно лишнее не сообщено. Окно, которое не совпадает с образцом, даёт ложную тревогу, только если основание — корень ненулевого многочлена степени не выше m − 1, разности двух строк: таких оснований не больше m − 1 из p (доказательство — в статье о полиномиальном хеше). Окон n − m + 1, и по линейности среднего ложных тревог не больше (n − m + 1)(m − 1)/p. Каждая стоит не больше m сравнений, так что при p ≥ n · m вся их работа в среднем меньше m. Остальное — n обновлений отпечатка, m действий на отпечаток образца и m сравнений на каждое настоящее вхождение.
Худший случай от этого не исчезает: если образец — aaa, а текст — aaa…a, каждое окно — вхождение, и проверка стоит n · m, как наивный поиск. Но эта работа нужна, только чтобы подтвердить вхождения. Если вам достаточно ответа «вероятно, да», проверку можно убрать: тогда время всегда O(n + m), но ответ может быть ложным с вероятностью, которую оценивает теорема. Первый вариант — алгоритм Лас-Вегас, всегда верный и обычно быстрый, второй — Монте-Карло, всегда быстрый и обычно верный (подробнее — Лас-Вегас и Монте-Карло).
Код
Сначала поиск одного образца с двумя счётчиками — попаданий и ложных тревог. Модуль здесь меньше 2³¹, поэтому произведение двух остатков помещается в 64-битное целое и в Go обходится без 128-битной арифметики.
Теперь копии. common_windows кладёт все окна первого файла в словарь «отпечаток → позиции», а окна второго катит мимо и для каждого попадания сравнивает буквы. Это тот же алгоритм, только образцов не один, а двадцать девять тысяч — все окна первого файла. Соседние общие окна складываются в куски. Перед сравнением пробелы, отступы и переводы строк сжимаются до одного пробела: копия с другими отступами — всё ещё копия.
Много образцов за один проход
Для одного образца Рабин — Карп редко лучший выбор: КМП линеен без всяких вероятностей, а встроенный поиск со своими фильтрами быстрее обоих. Но если образцов тысяча, другие способы ищут их по очереди, тысячу раз проходя текст. Рабину — Карпу хватает одного прохода: на каждом окне он смотрит, есть ли его отпечаток в хеш-таблице отпечатков образцов, и это стоит O(1), сколько бы образцов ни было.
Замер: первая часть романа, от одного до десяти тысяч образцов по 16 букв, каждый взят из того же текста. Одна серия — Рабин — Карп с таблицей отпечатков, другая — встроенный поиск, вызванный для каждого образца по очереди (str.count и strings.Count).
Встроенный поиск дорожает ровно вместе с числом образцов. Проход Рабина — Карпа стоит почти одинаково и при одном образце, и при десяти тысячах. В Python цикл по буквам медленный, и встроенный поиск, написанный на C, выигрывает, пока образцов меньше нескольких тысяч; при десяти тысячах проход Рабина — Карпа уже втрое быстрее. В Go граница — около десятка образцов.
Есть ограничение: окно одной длины ищет образцы только этой длины. Если длины разные, проходов столько, сколько разных длин, — либо нужен автомат Ахо — Корасик, который ищет образцы любой длины за один проход без всяких вероятностей.
Как ищут копии
Программы, которые ищут скопированный код, устроены как вторая сцена, только аккуратнее. PMD CPD, детектор копий из набора анализаторов PMD, сменил три алгоритма: сначала жадное покрытие строк Майкла Уайза, потом преобразование Барроуза — Уилера, а нынешнюю версию Стив Хокинс построил на алгоритме Карпа — Рабина. jscpd разбирает файлы на токены по правилам каждого языка и ищет повторяющиеся последовательности токенов скользящим хешем Рабина — Карпа. Токены вместо знаков дают важное: можно сравнивать код, не обращая внимания на пробелы и комментарии, а при желании — и на имена переменных, и тогда находятся копии, в которых всё переименовали.
Точечная диаграмма из сцены — старый способ увидеть повторы. Биологи рисуют так сравнение двух последовательностей ДНК, а книга «Object-Oriented Reengineering Patterns» советует тот же рисунок для поиска скопированного кода: диагональ из точек — скопированный кусок. Короткие параллельные отрезки в стороне от диагонали — общие идиомы, например одинаковые строчки импорта.
Если сравнивать надо не два файла, а каждую новую работу со всем архивом, хранить отпечатки всех окон дорого. Тогда хранят выборку отпечатков, но выбирают её так, чтобы любой общий кусок длиннее порога оставил хотя бы один общий отпечаток, — это просеивание (winnowing) Шлаймера, Уилкерсона и Эйкена 2003 года, на котором работает MOSS, система поиска списывания в программах. Как оно устроено — в главе курса «Иголка в стоге». А если нужны не точные копии, а почти одинаковые документы, отпечатки окон сравнивают как множества — это MinHash.
Сколько это стоит
| Задача | Время в среднем | В худшем случае |
|---|---|---|
| один образец длины m | O(n + m + occ · m) | O(n · m) |
| k образцов одной длины | O(n + k · m + occ · m) | O((n + k) · m) |
| общие окна двух текстов | O(n + n′ + общих · m) | O(n · n′) |
| самый длинный общий кусок | O((n + n′) log n) | — |
Память — O(1) на один образец и O(k) на таблицу отпечатков. Худший случай — когда почти каждое окно приходится сравнивать буквами: либо вхождений очень много, либо противник подобрал строки с одинаковым отпечатком. От второго защищает случайное основание и простой модуль; от первого не защищает ничто, но тогда и ответ состоит из n вхождений. Последняя строка таблицы — задача ниже: если общий кусок длины L есть, то есть и длины L − 1, поэтому длину ищут двоичным поиском по ответу, а каждую проверку делает Рабин — Карп.
Где ещё работает
- Стандартная библиотека Go.
strings.Indexищет длинные образцы фильтром по первому байту, а если фильтр часто ошибается, переключается на Рабина — Карпа: основание 16 777 619, модуль 2³², попадания проверяются сравнением строк. На русском тексте так происходит почти сразу — у всех русских букв в UTF-8 первый байт D0 или D1, об этом в статье о наивном поиске. - Двумерный поиск. Карп и Рабин сразу заметили, что метод переносится на картинки: отпечаток строки окна катится вдоль строки, а отпечатки строк складываются в отпечаток прямоугольника тем же приёмом по столбцам.
- Сравнение больших файлов. Отпечатки кусков дешевле пересылать и хранить, чем сами куски: на этом держатся системы, которые ищут одинаковые фрагменты в архивах и резервных копиях, — подробнее в статье о полиномиальном хеше.
История
Ричард Карп и Михаэль Рабин описали поиск по отпечаткам в техническом отчёте 1981 года, а журнальная статья вышла в 1987-м, в IBM Journal of Research and Development, под названием «Efficient randomized pattern-matching algorithms». Строку битов они читали как число и брали остаток от деления на случайное простое число; от выбора простого зависела и вероятность ошибки. Рабин в те годы много занимался алгоритмами, которые пользуются случайностью: его вероятностная проверка простоты, тест Миллера — Рабина, напечатана в 1980 году. Обоим авторам к тому времени уже вручили премию Тьюринга: Рабину — в 1976 году вместе с Даной Скоттом за недетерминированные автоматы, Карпу — в 1985-м за работы по алгоритмам и NP-полноте.
Задачи
В задаче нужно найти самый длинный кусок, общий для двух текстов, — например, для двух сцен этого каталога. Для одной длины это Рабин — Карп с таблицей отпечатков, а длину находит двоичный поиск.
Самый длинный общий кусокДанные: Исходный код сцен каталога legost.in «Война и мир», Л. Н. Толстой, общественное достояние