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

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

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

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

Пусть даны строка образца P = p1p2 :pm и текстовая строка T = t1t 2.. tn, представляющие собой последовательности над алфавитом S размера a. Задача точного сравнения строк (exact string matching, ESM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, начиная с которых P входит в T; иначе говоря, в вычислении множества fj j 1 < j < n — m + 1 и P = tjtj+1 tj+m-i}. Предполагается, что образец задан первым, после чего производится поиск его вхождения в нескольких текстах.

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

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

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

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

Алгоритм решения задачи ESM полным перебором выполняет проверку вхождения P на каждой позиции j строки T, где 1 < j < n — m + 1. Ему не требуется этап предварительной обработки. Этот алгоритм требует O(mn) времени и константной дополнительной памяти и в среднем производит O(n) сравнений символов. Его можно сравнить со следующими границами.

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

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

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