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

Точное сравнение с образцом

Пусть даны ''строка образца'' <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>. Предполагается, что образец задан первым, после чего производится поиск его вхождения в нескольких текстах.

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

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

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

Первый линейный алгоритм решения задачи 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).'''

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

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