Алгоритм основанный на суффикс функции

Поиск подстроки. Алгоритм Кнута–Морриса-Пратта

В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:

Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае. Прежде чем перейти к описанию алгоритма, необходимо рассмотреть понятие префикс-функции.

Префикс-функция строки π(S,i) – это длина наибольшего префикса строки S[1..i], который не совпадает с этой строкой и одновременно является ее суффиксом. Проще говоря, это длина наиболее длинного начала строки, являющегося также и ее концом. Для строки S удобно представлять префикс функцию в виде вектора длиной |S|-1. Можно рассматривать префикс-функцию длины |S|, положив π(S,1)=0. Пример префикс функции для строки «abcdabcabcdabcdab»:

Предположим, что π(S,i)=k. Отметим следующие свойства префикс-функции.

1. Если S[i+1]=S[k+1], то π(S,i+1)=k+1.
2. S[1..π(S,k)] является суффиксом строки S[1..i]. Действительно, если строка S[1..i] оканчивается строкой S[1… π(S,i)]=S[1..k], а строка S[1..k] оканчивается строкой S[1..π(S,k)], то и строка S[1..i] оканчивается строкой S[1..π(S,k)].
3. ∀ j∈(k,i), S[1..j] не является суффиксом строки S[1..i]. В противном случае было бы неверным предположение π(S,i)=k, так как j>k.

Рассмотренные свойства позволяют получить алгоритм вычисления префикс-функции.
Пусть π(S,i)=k. Необходимо вычислить π(S,i+1).

1. Если S[i+1]=S[k+1], то π(S,i+1)=k+1.
2. Иначе, если k=0, то π(S,i+1)=0.
3. Иначе положить k:=π(S,k) и перейти к шагу 1.

Ключевым моментом для понимания сути алгоритма является тот факт, что если найденный на предыдущем шаге суффикс не может быть расширен на следующую позицию, то мы пытаемся рассматривать меньшие суффиксы до тех пор, пока это возможно.

Алгоритм вычисления префикс-функции на языке Python:

Покажем, что время работы алгоритма составляет О(n), где n=|S|. Заметим, что асимптотику алгоритма определяет итоговое количество итераций цикла while. Это так, поскольку без учета цикла while каждая итерация цикла for выполняется за время, не превышающее константу. На каждой итерации цикла for k увеличивается не более чем на единицу, значит максимально возможное значение k=n–1. Поскольку внутри цикла while значение k лишь уменьшается, получается, что k не может суммарно уменьшиться больше, чем n–1 раз. Значит цикл while в итоге выполнится не более n раз, что дает итоговую оценку времени алгоритма O(n).

Рассмотрим алгоритм Кнута-Морриса-Пратта, основанный на использовании префикс-функции. Как и в примитивном алгоритме поиска подстроки, образец «перемещается» по строке слева направо с целью обнаружения совпадения. Однако ключевым отличием является то, что при помощи префикс-функции мы можем избежать заведомо бесполезных сдвигов.

Пусть S[0..m–1] – образец, T[0..n–1] – строка, в которой ведется поиск. Рассмотрим сравнение строк на позиции i, то есть образец S[0..m–1] сопоставляется с частью строки T[i..i+m–1]. Предположим, первое несовпадение произошло между символами S[j] и T[i+j], где i 0, присвоим k = F[k–1] и перейдем в начало шага 3.
Пока i

Алгоритмы поиска в тексте

Цель лекции: изучить основные алгоритмы поиска в тексте и научиться решать задачи поиска в тексте на основе алгоритмов прямого поиска; Кнута, Морриса и Пратта; Боуера и Мура.

Работа в текстовом редакторе, поисковые запросы в базе данных, задачи в биоинформатике, лексический анализ программ требуют эффективных алгоритмов работы с текстом. Задачи поиска слова в тексте используются в криптографии , различных разделах физики, сжатии данных, распознавании речи и других сферах человеческой деятельности.

Введем ряд определений, которые будут использоваться далее в изложении материала.

Алфавит – конечное множество символов.

Строка (слово) – это последовательность символов из некоторого алфавита. Длина строки – количество символов в строке.

Строку будем обозначать символами алфавита , например X=x[1]x[2]. x[n] – строка длиной n , где x[i] – i -ый символ строки Х , принадлежащий алфавиту. Строка, не содержащая ни одного символа, называется пустой.

Строка X называется подстрокой строки Y , если найдутся такие строки Z₁ и Z₂ , что Y=Z₁XZ₂ . При этом Z₁ называют левым, а Z₂ – правым крылом подстроки. Подстрокой может быть и сама строка. Иногда при этом строку X называют вхождением в строку Y . Например, строки hrf и fhr является подстроками строки abhrfhr .

Подстрока X называется префиксом строки Y , если есть такая подстрока Z , что Y=XZ . Причем сама строка является префиксом для себя самой (так как найдется нулевая строка L , что X=XL ). Например, подстрока ab является префиксом строки abcfa .

Подстрока X называется суффиксом строки Y , если есть такая подстрока Z , что Y=ZX . Аналогично, строка является суффиксом себя самой. Например, подстрока bfg является суффиксом строки vsenfbfg .

Поставим задачу поиска подстроки в строке. Пусть задана строка, состоящая из некоторого количества символов. Проверим, входит ли заданная подстрока в данную строку. Если входит, то найдем номер, начиная с какого символа строки, то есть, определим первое вхождение заданной подстроки в исходной строке.

Рассмотрим несколько известных алгоритмов поиска подстроки в строке более подробно.

Прямой поиск

Данный алгоритм еще называется алгоритмом последовательного поиска , он является самым простым и очевидным.

Основная идея алгоритма прямым поиском заключается в посимвольном сравнении строки с подстрокой. В начальный момент происходит сравнение первого символа строки с первым символом подстроки, второго символа строки со вторым символом подстроки и т. д. Если произошло совпадение всех символов, то фиксируется факт нахождения подстроки. В противном случае производится сдвиг подстроки на одну позицию вправо и повторяется посимвольное сравнение, то есть сравнивается второй символ строки с первым символом подстроки, третий символ строки со вторым символом подстроки и т. д. ( рис. 39.1) Символы, которые сравниваются, на рисунке выделены жирным. Рассматриваемые сдвиги подстроки повторяются до тех пор, пока конец подстроки не достиг конца строки или не произошло полное совпадение символов подстроки со строкой, то есть найдется подстрока .

Данный алгоритм является малозатратным и не нуждается в предварительной обработке и в дополнительном пространстве. Большинство сравнений алгоритма прямого поиска являются лишними. Поэтому в худшем случае алгоритм будет малоэффективен, так как его сложность будет пропорциональна O((n-m+1)xm) , где n и m – длины строки и подстроки соответственно.

Алгоритм Кнута, Морриса и Пратта

Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они совместно опубликовали в 1977 году. Алгоритм Кнута, Морриса и Пратта (КМП- алгоритм ) является алгоритмом, который фактически требует только O(n) сравнений даже в самом худшем случае. Рассматриваемый алгоритм основывается на том, что после частичного совпадения начальной части подстроки с соответствующими символами строки фактически известна пройденная часть строки и можно, вычислить некоторые сведения, с помощью которых затем быстро продвинуться по строке.

Основным отличием алгоритма Кнута, Морриса и Пратта от алгоритма прямого поиска заключается в том, что сдвиг подстроки выполняется не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Следовательно, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим ( рис. 39.2). На рисунке символы, подвергшиеся сравнению, выделены жирным шрифтом.

Если для произвольной подстроки определить все ее начала, одновременно являющиеся ее концами, и выбрать из них самую длинную (не считая, конечно, саму строку), то такую процедуру принято называть префикс -функцией. В реализации алгоритма Кнута, Морриса и Пратта используется предобработка искомой подстроки, которая заключается в создании префикс -функции на ее основе. При этом используется следующая идея: если префикс (он же суффикс ) строки длиной i длиннее одного символа, то он одновременно и префикс подстроки длиной i-1 . Таким образом, проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс .

Точный анализ рассматриваемого алгоритма весьма сложен. Д. Кнут, Д. Моррис и В. Пратт доказывают, что для данного алгоритма требуется порядка O(m+n) сравнений символов (где n и m – длины строки и подстроки соответственно), что значительно лучше, чем при прямом поиске.

Сканирование слева направо, сравнение справа налево.

Алгоритм Бойера — Мура

Данный алгоритм был разработан двумя учеными — Робертом Бойером (англ. Robert Stephen Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Он считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

Вопрос: что значит алгоритмы «общего назначения»?

Ответ: это значит, что эти алгоритмы универсальны, т.е. предназначены для решения широкого класса задач.

Алфавит — конечное множество символов.

Подстрока — это последовательность подряд идущих символов в строке.

Строка — последовательность символов текста.

Суффикс — это подстрока, заканчивающаяся на последний символ строки.

В определении строки речь не обязательно должна идти именно о тексте.

В общем случае строка — это любая последовательность байтов.

Поиск подстроки в строке осуществляется по заданному образцу, т. е. некоторой последовательности байтов, длина которой не превышает длину строки.

Наша задача заключается в том, чтобы определить, содержит ли строка заданный образец.

Алгоритма Бойера — Мура можно представить в виде двух простых шагов.

Для искомого образца строим две таблицы — таблицу стоп-символов и таблицу суффиксов.

Процесс построения таблиц будет описан ниже.

Совмещаем начало строки и образца и начинаем проверку с последнего символа образца.

Если символы совпадают, производится сравнение предпоследнего символа образца и т. д. Если все символы образца совпали с наложенными символами строки, значит, подстрока найдена и поиск окончен.

Если же какой-то символ образца не совпадает с соответствующим символом строки, образец сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.

Назовем эти «несколько символов», упомянутые в предыдущем абзаце, величиной сдвига.

В качестве величины сдвигаберется большее из двух значений:

1) Значение, полученное с помощью таблицы стоп-символов по простому правилу:

Если несовпадение произошло на позиции , а стоп-символ « », то значение величины сдвига будет равно .

— позиция символа в образце (нумерация с 1);

— значение, записанное в таблице стоп-символов, для символа «c».

2) Значение, полученное из таблицы суффиксов.

Подробное описание работы алгоритма

Псевдокод: алгоритм Бойера — Мура

Boyer-Moore-Matcher( )

1.

2. m

3. Compute-Last-Occurrence-Function( )

4. Compute-Good-Suffix-Function( )

5.

6. while

7. do

8. while and

9. do

10. if

11. then print «Образец входит со сдвигом» s

12.

13. else

Алгоритм основан на трёх идеях.

Сканирование слева направо, сравнение справа налево.

Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона.

Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д.

Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.

Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам.

Вопрос: что такое эвристика?

Ответ: эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.

2. Эвристика стоп-символа(англ. bad-character heuristic).

Стоп-символ — это первый справа символ в строке, отличный от соответствующего символа в образце.

Эвристика стоп-символа предлагает попробовать новое значение сдвига, исходя из того, где в образце встречается стоп-символ (если вообще встречается).

В наиболее удачном случае стоп-символ выявляется при первом же сравнении и не встречается нигде в образце.

В этом случае сдвиг можно сразу увеличить на : любой меньший сдвиг заведомо не подойдет, так как стоп- символ в тексте окажется напротив какого-то символа из образца.

Если этот наиболее удачный случай повторяется постоянно, то при поиске подстроки мы просмотрим всего лишь часть текста (вот как полезно сравнивать справа налево!).

В общем случае эвристика стоп-символа работает так. Предположим, что при сравнении права налево мы наткнулись на первое несовпадение: , где . Пусть — номер самого правого вхождения символа в образец (если этот символ вообще не появляется в образце, считаем равным ). Мы утверждаем, что можно увеличить на , не упустив ни одного допустимого сдвига.

В самом деле, если , то стоп-символ вообще не встречается в образце , так что можно сразу сдвинуть образец на позиций вправо.

Если , то образец можно сдвинуть на позиций вправо, т.к. при меньших сдвигах стоп-символ в тексте не совпадет с соответствующим символом образца.

Наконец, если , то эвристика предлагает сдвигать образец не вправо, а влево; алгоритм Бойера — Мура эту рекомендацию игнорирует, поскольку эвристика безопасного суффикса всегда предлагает ненулевой сдвиг вправо.

Чтобы применять эвристику стоп-символа полезно для каждого возможного стоп-символа вычислить значение . Это делается простой процедурой Compute-Last-Occurrence-Function («найти последнее вхождение»), которая для каждого вычисляет — номер крайнего правого вхождения в , или нуль, если в не входит. В этих обозначениях приращение сдвига, диктуемое эвристикой стоп-символа, есть , как и написано в строке 13 алгоритма Boyer-Moore-Matcher.

Псевдокод: найти последнее вхождение стоп-символа в подстроку

Compute-Last-Occurrence-Function( )

1. for each character

2. do

3. for to

4. do

5. return

Время работы процедуры Compute-Last-Occurrence-Function есть

Пример использования эвристики стоп-символа:

Предположим, что мы производим поиск слова «колокол».

Первая же буква не совпала — «к» (назовём эту букву стоп-символом).

Тогда можно сдвинуть шаблон вправо до последней буквы «к».

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.

Строка: * * * * * а л * * * * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

В данном случае стоп-символ — «а», и шаблон сдвигается так, чтобы он оказался прямо за этой буквой. В алгоритме Бойера — Мура эвристика стоп-символа вообще не смотрит на совпавший суффикс (см. ниже), так что первая буква шаблона («к») окажется под «л», и будет проведена одна заведомо холостая проверка.

Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.

Строка: * * * * к к о л * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л .

В таких ситуациях выручает третья идея алгоритма — эвристика совпавшего суффикса.

3. Эвристика безопасного (совпавшего) суффикса(англ. good-suffix heuristic).

Если и — строки, будем говорить, что они сравнимы (обозначение: ), если одна из них является суффиксом другой. Если выровнять две сравнимые строки по правому краю, то символы, расположенные один под другим, будут совпадать. Отношение симметрично: если , то и .

Эвристика безопасного суффикса состоит в следующем: если , где (и число — наибольшее с таким свойством), то мы можем безбоязненно увеличить сдвиг на

Иными словами, — наименьшее расстояние, на которое мы можем сдвинуть образец без того, чтобы какой- то из символов, входящих в «безопасный суффикс» оказался напротив несовпадающего с ним символа из образца. Поскольку строка заведомо сравнима с пустой строкой , число корректно определено для всех . Стоит также заметить, что для всех , так что на каждом шаге алгоритма Бойера — Мура образец будет сдвигаться вправо хотя бы на одну позицию. Мы будем называть функцией безопасного суффикса (англ. good-suffix function), ассоциированной со строкой .

Псевдокод: вычисление функции безопасных суффиксов

Compute-Good-Suffix-Function( )

2. pi[] = префикс-функция(P)

3. pi1[] = префикс-функция(обращение(P))

5. suffshift[j] = m — pi[m]

8. suffshift[j] = min(suffshift[j], i — pi1[i])

Время работы процедуры Compute-Good-Suffix-Function есть .

Пример использования эвристики безопасного (совпавшего) суффикса:

Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.

Строка: * * т о к о л * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.

Обе эвристики требуют предварительных вычислений — в зависимости от шаблона поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту (например, если алфавит состоит из 256 символов, то её длина 256); таблица суффиксов — искомому шаблону. Именно из-за этого алгоритм Бойера — Мура не учитывает совпавший суффикс и несовпавший символ одновременно — это потребовало бы слишком много предварительных вычислений.

Опишем подробнее обе таблицы.

Таблица стоп-символов

Считается, что символы строк нумеруются с 1 (как в Паскале).

В таблице стоп-символов указывается последняя позиция в образце (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в образец , пишем 0 (для нумерации с 0 — соответственно, −1).

Например, если , таблица стоп-символов будет выглядеть так.

Символ a b c d [все остальные]

Последняя позиция 5 2 7 6 0

Обратите внимание, для стоп-символа «d» последняя позиция будет 6, а не 8 — последняя буква не учитывается. Это известная ошибка, приводящая к неоптимальности. Для АБМ она не фатальна («вытягивает» эвристика суффикса), но фатальна для упрощённой версии АБМ — алгоритма Хорспула.

Если несовпадение произошло на позиции , а стоп-символ , то сдвиг будет .

Таблица суффиксов

Для каждого возможного суффикса шаблона указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с . Если такой сдвиг невозможен, ставится (в обеих системах нумерации). Например, для того же будет:

Суффикс [пустой] d cd dcd . abcdadcd

Сдвиг 1 2 4 8 . 8

было ? ?d ?cd ?dcd . abcdadcd

стало abcdadcd abcdadcd abcdadcd abcdadcd . abcdadcd

Если шаблон начинается и заканчивается одной и той же комбинацией букв, вообще не появится в таблице.

Например, для для всех суффиксов (кроме, естественно, пустого) сдвиг будет равен 4.

Суффикс [пустой] л ол . олокол колокол

Сдвиг 1 4 4 . 4 4

было ? ?л ?ол . ?олокол колокол

стало колокол колокол колокол . колокол колокол

Пусть у нас есть набор символов (алфавит) из пяти символов: и мы хотим найти вхождение образца “ ” в строке “ ”. Следующие схемы иллюстрируют все этапы выполнения алгоритма:

Если несовпадение произошло на позиции , а стоп-символ , то сдвиг будет .

Таблица суффиксов для образца “ ”.

Суффикс [пустой] d ad bad bbad abbad

Сдвиг 1 5 5 5 5 5

было ? ?d ?ad ?bad ?bbad abbad

стало abbad abbad abbad abbad abbad abbad

a b e c c a a b a d b a b b a d

Накладываем образец на строку. Совпадения суффикса нет — таблица суффиксов даёт сдвиг на одну позицию. Для несовпавшего символа исходной строки «с» (5-я позиция) в таблице стоп-символов записан 0. Сдвигаем образец вправо на 5-0=5 позиций:

a b e c c a a b a d b a b b a d

Символы 3—5 совпали, а второй — нет. Эвристика стоп-символа для «а» не работает (2-4=-2). Но поскольку часть символов совпала, в дело включается эвристика совпавшего суффикса, сдвигающая образец сразу на пять позиций!

a b e c c a a b a d b a b b a d

И снова совпадения суффикса нет. В соответствии с таблицей стоп-символов сдвигаем образец на 1 позицию и получаем искомое вхождение образца:

a b e c c a a b a d b a b b a d

Вычислительная сложность

Общая оценка вычислительной сложности алгоритма — на непериодических шаблонах и на периодических, где n — строка, в которой выполняется поиск, m — шаблон поиска, Σ — алфавит, на котором проводится сравнение. В 1991 году Коул показал, что на непериодических шаблонах за полный проход по строке алгоритм совершит не более сравнений.

Время исполнения алгоритма Бойера — Мура в наихудшем случае есть , поскольку на исполнение Compute-Last-Occurrence-Function уходит время , на Compute-Good-Suffix-Function уходит , и в худшем случае алгоритм Бойера — Мура (как и алгоритм Рабина — Карпа) потратит время на проверку каждого априори возможного сдвига. На практике, однако, именно алгоритм Бойера — Мура часто оказывается наиболее эффективным.

Выводы

Достоинства

Алгоритм Бойера-Мура на «хороших» данных очень быстр, а вероятность появления «плохих» данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск (haystack). Разве что на коротких текстах выигрыш не оправдает предварительных вычислений.

haystack — строка, в которой выполняется поиск.

В переводе на русский haystack дословно означает «стог сена».

Недостатки

Алгоритмы семейства Бойера — Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.

Сравнение не является «чёрным ящиком», поэтому при реализации наиболее быстрого поиска приходится либо рассчитывать на удачную работу оптимизатора, либо вручную оптимизировать поиск на ассемблерном уровне.

Если текст изменяется редко, а операций поиска проводится много (например, поисковая машина), в тексте стоило бы провести индексацию, после чего поиск можно будет выполнять в разы быстрее, чем даже алгоритмом Бойера — Мура.

На больших алфавитах (например, Юникод) таблица стоп-символов может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.

На искусственно подобранных «неудачных» текстах (например, ) скорость алгоритма Бойера — Мура серьёзно снижается. Существуют попытки совместить присущую алгоритму Кнута — Морриса — Пратта эффективность в «плохих» случаях и скорость Бойера — Мура в «хороших» — например, турбо-алгоритм, обратный алгоритм Колусси и другие.

Итог

Алгоритм Бойера и Мура оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.

Особенность алгоритма Бойера и Мура заключается в предварительных вычислениях над подстрокой с целью сравнения подстроки с исходной строкой, осуществляемой не во всех позициях.

Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы: построение и анализ».-М.:МЦНМО,1999, с.801 – 806