Закрепление материала: Поиск

Модуль "Поиск" • урок 6 из 7 • ~9 минут

Краткое резюме модуля

За прошедшие уроки мы разобрали следующие важные алгоритмы и концепции:

• Линейный и бинарный поиск - базовые алгоритмы для массивов. Линейный поиск универсален, но работает за O(N). Бинарный поиск требует отсортированных данных и произвольного доступа по индексу, но находит элемент за O(log N).
• Наивный поиск подстроки - прикладывает образец ко всем позициям текста. В худшем случае работает за O(N*M) из-за неэффективных возвратов назад по тексту.
• Алгоритм КМП - решает проблему возвратов с помощью предварительно вычисленной префикс-функции, гарантируя линейное время O(N+M). Указатель по тексту двигается только вперед.
• Алгоритм Бойера-Мура - сверяет символы справа налево и использует эвристику "плохого символа" для больших скачков по тексту. Чаще всего разбирают именно эту упрощенную версию, без правила хорошего суффикса. На практике является самым быстрым со сложностью до O(N/M) в лучшем случае.
• Алгоритм Рабина-Карпа - заменяет сравнение строк сравнением их числовых хешей. Идеален для поиска множества образцов одновременно (например, в системах антиплагиата).

Ключевые идеи

• Барьер: микро-оптимизация линейного поиска, при которой искомый элемент помещается в конец массива, чтобы избавиться от лишней проверки выхода за границы в цикле.
• Префикс-функция (ПФ): ячейка ПФ[i] хранит для куска образца P[0..i] длину наибольшего начала, совпадающего с концом этого куска. При несовпадении после j совпавших символов окно едет вперед на j - ПФ[j-1].
• Таблица сдвигов d: та же таблица в другой нумерации - по позиции несовпадения: d[j] = ПФ[j-1] при d[0] = -1, и сдвиг записывается как j - d[j]. В усиленном варианте добавляют условие P[d[j]] не равно P[j], и в таблице появляются новые -1, а сдвиги становятся длиннее.
• Плохой символ: эвристика алгоритма Бойера-Мура. Если при сравнении с конца обнаружен символ, которого вообще нет в образце, окно сдвигается сразу за этот символ.
• Хороший суффикс: второе правило полного Бойера-Мура: если хвост образца совпал, а дальше сорвалось, образец сдвигают до следующего такого же хвоста внутри себя. Комбинированная стратегия считает оба сдвига и берет больший.
• Схема Горнера: способ посчитать хеш окна за один проход - на каждом символе умножить накопленное значение на основание и прибавить вес буквы. Так Рабин-Карп получает исходные числа образца и первого окна.
• Скользящий (кольцевой) хеш: математический трюк алгоритма Рабина-Карпа, позволяющий пересчитать хеш нового окна текста на основе предыдущего за константное время O(1).
• Коллизия: ситуация, когда разные строки дают одинаковое числовое значение хеша. Требует обязательной посимвольной проверки при совпадении хешей в алгоритме Рабина-Карпа; если строки при этом разошлись, говорят о холостом срабатывании.

Чтобы уложить модуль в голове, по каждому алгоритму поиска по образцу достаточно помнить крючок-образ, плюсы и минусы:

Развитие методов поиска по образцу

Пять алгоритмов модуля - это не вся тема, а ее классическое ядро. Поиском по образцу занимались и до Бойера и Мура, и во все последующие десятилетия; полезно знать хотя бы направления, в которых развивалась тема.

Поиск нескольких образцов за один проход

Идею КМП можно растянуть с одного образца на целый список. Алгоритм Ахо-Корасик (1975) строит из всех образцов бор - дерево их общих начал - и добавляет в него те же ссылки отката, что и префикс-функция, только ведут они теперь не вдоль строки, а по дереву. Один проход по тексту находит вхождения всех образцов сразу. В модуле встречались еще два ответа на тот же вопрос: обобщение Калинина в уроке про КМП и поиск по хеш-таблице у Рабина-Карпа.

Предобработка текста вместо предобработки образца

Все пять алгоритмов устроены одинаково: предобрабатывается образец, а текст затем прочитывается целиком. Значит, каждый новый запрос стоит не меньше O(N), даже если текст не менялся. Если же текст постоянен, а искать в нем будут многократно, разумнее один раз построить индекс по самому тексту: суффиксное дерево (Укконен, 1995), суффиксный массив (Манбер и Майерс, 1990) или FM-индекс (Феррагина и Манци, 2000). Тогда ответ на запрос стоит порядка длины образца и от длины текста не зависит вовсе. Так устроены полнотекстовый поиск и программы выравнивания ДНК, где текст - геном, а образцов миллионы.

Какие алгоритмы применяются в стандартных библиотеках

Ни чистый КМП, ни чистый Бойер-Мур в стандартных библиотеках обычно не применяются. В glibc функции strstr и memmem используют алгоритм two-way (Крошмор и Перрен, 1991): он дает линейное время и при этом обходится постоянной дополнительной памятью, без таблицы на весь алфавит. В Python внутри in и .find() работает FastSearch, сочетание Бойера-Мура-Хорспула с алгоритмом воскресного дня, а с версии 3.10 на длинных образцах включается тот же two-way - как страховка от квадратичного худшего случая.

Смежные задачи

Рядом лежит вопрос не "есть ли вхождение", а "насколько похоже". Расстояние Левенштейна и его вариант Дамерау-Левенштейна считают, сколькими правками одна строка превращается в другую; алгоритмы Нидлмана-Вунша и Смита-Ватермана выравнивают последовательности в биоинформатике; алгоритм bitap (Баэса-Йейтс и Гоннет, 1992) ищет с заданным числом ошибок, сводя сравнение к битовым операциям. Это уже отдельная тема, но выросла она из той же задачи.

Не остановилась и теория. Для поиска подстроки известен квантовый алгоритм Рамеша и Виная: он справляется за время порядка корня из длины текста плюс корня из длины образца. Классическому алгоритму в худшем случае приходится прочитать текст целиком, квантовому хватает порядка корня от его длины.

Проверьте себя