Последовательное точное сравнение строк: различия между версиями

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

Прямолинейный алгоритм решения задачи ESM выполняет проверку вхождения P на каждой позиции j строки T, где <math>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).'''

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

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

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

[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0| Алгоритм Бойера-Мура] считается одним из самых эффективных алгоритмов решения задачи ESM. Его упрощенная версия либо весь алгоритм полностью нередко применяются в программах редактирования текстов для выполнения операций поиска и замены.

Алгоритм сканирует символы в окне справа налево, начиная с самого правого символа. В случае несовпадения (либо полного совпадения с шаблоном) он использует две предварительно вычисляемые функции для сдвига шаблона вправо. Эти две функции сдвига носят название ''сдвига плохого символа'' и ''сдвига хорошего суффикса''. Они основаны на следующих наблюдениях. Предположим, что несовпадение обнаруживается между символом <math>p_i = a</math> шаблона и символом <math>t_{i + j} = b</math> текста после попытки в позиции j. Тогда <math>p_{i + 1} ... p_m = t_{i + j + 1} ... t_{j + m} = u</math> и <math>p_i \ne t_{i + j}</math>. Сдвиг хорошего суффикса заключается в выравнивании сегмента <math>t_{i + j + 1} ... t_{j + m}</math> с его самым правым вхождением в P, предшествующим символу, отличному от <math>p_i</math>. Еще один вариант, называемый ''сдвигом лучшего суффикса'', заключается в выравнивании сегмента <math>t_{i + j} ... t_{j + m}</math> с его самым правым вхождением в P. Вычисление обоих вариантов требует O(m) времени и памяти, независимо от размера алфавита. Если такого сегмента не существует, сдвиг заключается в выравнивании самого длинного суффикса v строки <math>t_{i + j + 1} ... t_{j + m}</math> с совпадающим префиксом x. Сдвиг плохого символа заключается в выравнивании символа текста <math>t_{i + j}</math> с его самым правым вхождением в <math>p_1 ... p_{m - 1}</math>. Если <math>t_{i + j}</math> не встречается в шаблоне и никакое вхождение P в T не перекрывает символ <math>t_{i + j}</math>, тогда левый конец шаблона выравнивается с символом в позиции 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 [4]). Поиск может быть выполнен за оптимальное ожидаемое время O((log m/m) x n) с использованием суффиксного конечного автомата или суффиксного дерева обращенного шаблона.'''

Вместо индексной структуры может использоваться [http://ru.knowledgr.com/11652108/%D0%9E%D1%80%D0%B0%D0%BA%D1%83%D0%BB%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B0| оракул фактора], поскольку единственной строкой длины m, принимаемой оракулом строки w длины m, является сама строка w. Это выполняется при помощи алгоритма сопоставления с обращенным оракулом (Backward Oracle Matching, BOM) Аллозена, Крочмора и Раффино [1]. На практике его поведение схоже с поведением алгоритма BDM.

Алгоритмы этого типа выполняются за линейное время (это относится и к предварительной обработке, и к поиску) и требуют константного объема памяти в дополнение к объему входных данных.

'''Теорема 7 (Галил, Сейферас, 1983 [8]). Поиск может быть выполнен оптимальным образом за время O(n) с использованием константного объема памяти.'''

После первого решения Галила и Сейфераса другие варианты были предложены Крочмором и Перреном [6] и Риттером [13]. Алгоритмы разбивают шаблон на две части; вначале они выполняют поиск правой части шаблона слева направо, а затем, если не обнаружено несовпадений, ищут левую часть. Разбиение может представлять собой идеальную факторизацию [8] или критическую факторизацию [6] либо основываться на лексикографически максимальном суффиксе шаблона [13]. Еще одно решение Крочмора [2] представляет собой вариант KMP [11]: оно на лету вычисляет нижние границы периодов префиксов шаблона и не требует предварительной обработки.