Последовательное точное сравнение строк

Ключевые слова и синонимы

Точное сравнение с шаблоном

Постановка задачи

Пусть даны строка шаблона [math]\displaystyle{ P = p_1 p_2 ... p_m }[/math] и текстовая строка [math]\displaystyle{ T = t_1 t_2 ... t_n }[/math], представляющие собой последовательности над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math]. Задача точного сравнения строк (exact string matching, ESM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, начиная с которых P входит в T; иначе говоря, в вычислении множества [math]\displaystyle{ \{ j | 1 \le j \le n - m + 1, P = t_j t_{j + 1} ... t_{j + m - 1} \} }[/math]. Предполагается, что шаблон задается первым, после чего производится поиск его вхождения в нескольких текстах.

Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из [math]\displaystyle{ \Sigma }[/math]. Для простоты и практичности будем далее полагать m = o(n).

Основные результаты

Большинство алгоритмов решения задачи ESM содержат два этапа: этап предварительной обработки шаблона P и этап поиска в тексте T. Этап предварительной обработки служит для сбора предварительной информации о шаблоне с целью ускорения этапа поиска.

Этап поиска алгоритмов сравнения строк работает следующим образом. Вначале он выравнивает левые концы шаблона и текста, затем сравнивает выровненные символы текста и шаблона – эта операция называется попыткой или сканированием – а после обнаружения совпадения всего шаблона либо несовпадения перемещает шаблон вправо. Эта процедура повторяется до тех пор, пока правый конец шаблона не выйдет за правый конец текста. Фаза сканирования может рассматриваться как операция над текстом сквозь окно, размер которого чаще всего совпадает с длиной шаблона. Данный вид обработки называется механизмом сканирования и сдвига. Различные стратегии сканирования окна легли в основу разных алгоритмов, обладающих различными свойствами и преимуществами.

Алгоритм решения задачи ESM полным перебором выполняет проверку вхождения P на каждой позиции j строки T, где [math]\displaystyle{ 1 \le j \le n - m + 1 }[/math]. Ему не требуется этап предварительной обработки. Этот алгоритм требует O(mn) времени и константной дополнительной памяти и в среднем производит O(n) сравнений символов. Его можно сравнить со следующими границами.

Теорема 1 (Коул и коллеги, 1995 [3]). Минимальное количество сравнений символов для решения задачи ESM в наихудшем случае оказывается больше или равно n + 9/(4m)(n — m) и может быть сделано меньше или равно n + 8/(3(m + 1))(n - m).

Теорема 2 (Яо 1979 [15])). Задача ESM может быть решена за оптимальное ожидаемое время O((log m/m) x n).

Разбор текста в онлайновом режиме

Первый линейный алгоритм решения задачи ESM появился в 1970-х. Этап предварительной обработки этого алгоритма заключался в вычислении периодов префиксов шаблона или, что эквивалентно, длине самой длинной границы для всех префиксов шаблона. Граница строки является одновременно и префиксом, и суффиксом строки, отличным от нее самой. Обозначим за next[i] длину самого длинного пути в [math]\displaystyle{ p_1 ... p_{i - 1} }[/math]. Рассмотрим попытку сравнения в позиции j, где шаблон [math]\displaystyle{ p_1 ... p_m }[/math] выровнен с сегментом [math]\displaystyle{ t_j ... t_{j + m - 1} }[/math] текста. Предположим, что первое несовпадение (при сканировании слева направо) имеет место между символами [math]\displaystyle{ p_i }[/math] и [math]\displaystyle{ t_{i + j} }[/math] для [math]\displaystyle{ 1 \le i \le m }[/math]. Тогда [math]\displaystyle{ p_1 ... p_{i - 1} = t_j ... t_{i + j - 1} = u }[/math] и [math]\displaystyle{ a = p_i \ne t_{i + j} = b }[/math]. При сдвиге разумно будет ожидать, что префикс v шаблона будет соответствовать некоторому суффиксу фрагмента u текста. Таким образом, после сдвига сравнение может возобновиться для позиций [math]\displaystyle{ p_{next[i]} }[/math] и [math]\displaystyle{ t_{i + j} }[/math] без потери каких-либо вхождений P в T и необходимости выполнения возврата в тексте. Существуют два подхода, различающихся в зависимости от того, должен ли [math]\displaystyle{ p_{next[i]} }[/math] совпадать с [math]\displaystyle{ p_i }[/math].

Теорема 3 (Кнут, Моррис и Пратт, 1977 [11])). Текстовый поиск может быть выполнен за время O(n) с использованием памяти в размере O(m). Предварительная обработка шаблона может быть выполнена за время O(m).

Поиск можно осуществить с использованием реализованного алгоритма поиска потомка по умолчанию из детерминированного конечного автомата [math]\displaystyle{ \mathcal{D}(P) }[/math], распознающего язык [math]\displaystyle{ \Sigma * P }[/math]. Размер реализации алгоритма составляет O(m) и не зависит от размера алфавита в силу того, что автомат [math]\displaystyle{ \mathcal{D}(P) }[/math] имеет m + 1 состояний, m прямых дуг и не более m обратных дуг. Использование конечного автомата для поиска в тексте позволяет получить алгоритм с эффективной задержкой (представляющей собой максимальное время обработки символа текста).

Теорема 4 (Ханкарт, 1993 [10]). Поиск шаблона P может быть произведен с задержкой в [math]\displaystyle{ O(min \{ \sigma, log_2 \; m ) \} ) }[/math] сравнений букв.

Заметим, что в большинстве алгоритмов предварительная обработка шаблона не обязательно производится перед разбором текста, поскольку ее можно выполнить «на лету» в процессе разбора.

Практически эффективные алгоритмы

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