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

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

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

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

Пусть даны строка образца [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).