Последовательное точное сравнение строк
Ключевые слова и синонимы
Точное сравнение с шаблоном
Постановка задачи
Пусть даны строка шаблона [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. Его упрощенная версия либо весь алгоритм полностью нередко применяется в программах редактирования текстов для выполнения операций поиска и замены.
Алгоритм сканирует символы в окне справа налево, начиная с самого правого символа. В случае несовпадения (либо полного совпадения с шаблоном) он использует две предварительно вычисляемые функции для сдвига шаблона вправо. Эти две функции сдвига носят название сдвига плохого символа и сдвига хорошего суффикса. Они основаны на следующих наблюдениях. Предположим, что несовпадение обнаруживается между символом pi = a шаблона и символом ti+j = b текста после попытки в позиции j. Тогда pi+1 … pm = ti+j+1 … tj+m = u и pi ф ti+j. Сдвиг хорошего суффикса заключается в выравнивании сегмента ti+j+1 … tj+m с его самым правым вхождением в P, предшествующим символу, отличному от pi. Еще один вариант сдвига хорошего суффикса заключается в выравнивании сегмента ti+j … tj+m с его самым правым вхождением в P. Вычисление обоих вариантов требует O(m) времени и памяти, независимо от размера алфавита. Если такого сегмента не существует, сдвиг заключается в выравнивании самого длинного суффикса v строки ti+j+1 … tj+m с совпадающим префиксом x. Сдвиг плохого символа заключается в выравнивании символа текста ti+j с его самым правым вхождением в p1 … pm-\-. Если ti+j не встречается в шаблоне и никакое вхождение P в T не перекрывает символ ti+j, тогда левый конец шаблона выравнивается с символом в позиции i + j + 1. В этом случае поиск может быть выполнен за время O(n/m) в наилучшем случае.
Теорема 5 (Коул, 1994 [5, 14]). В ходе поиска непериодического шаблона P длины m (такой, что длина самой длинной границы P меньше m/2) в тексте T длины n алгоритм Бойера-Мура производит не более 3n сравнений между буквами P и T.
Граница Яо может быть достигнута благодаря использованию индексной структуры для реверсивного шаблона. Это выполняется при помощи алгоритма обращения сегмента (Reverse Factor), также известного как BDM (Backward Dawg Matching, сопоставление с обращенным ОАГС).
Теорема 6 (Крочмор и др., 1994 [ ]). Поиск может быть выполнен за оптимальное ожидаемое время O((log m/m) x n) с использованием суффиксного конечного автомата или суффиксного дерева реверсивного шаблона.
Вместо индексной структуры может использоваться фактор-оракул, поскольку единственной строкой длины m, принимаемая оракулом строки w длины m, является сама строка w. Это выполняется при помощи алгоритма сопоставления с обращенным оракулом (Backward Oracle Matching, BOM) Аллозена, Крочмора и Раффино [ ]. На практике его поведение схоже с поведением алгоритма BDM.
Алгоритмы, оптимальные по времени и памяти
Алгоритмы этого типа выполняются за линейное время (это относится к предварительной обработке и поиску) и требуют константного объема памяти в дополнение к объему входных данных.
Теорема 7 (Галил, Сейферас, 1983 [ ])). Поиск может быть выполнен оптимальным образом за время O(n) с использованием константного объема памяти.
После первого решения Галила и Сейфераса другие варианты были предложены Крочмором и Перреном [ ] и Риттером [ ]. Алгоритмы разбивают шаблон на две части; вначале они выполняют поиск правой части шаблона слева направо, а затем, если не обнаружено несовпадений, ищут левую часть. Разбиение может представлять собой идеальную факторизацию [8] или критическую факторизацию [ ] лабо основываться на лексикографически максимальном суффиксе шаблона [ ]. Еще одно решение Крочмора [ ] представляет собой вариант KMP [ ]: оно на лету вычисляет нижние границы периодов префиксов шаблона и не требует предварительной обработки.
Бит-параллельное решение
Для решения задачи ESM можно применить технику битового параллелизма.