Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Алгоритмы обработки строк

Покупка
Артикул: 613590.03.99
На материале задачи поиска подстроки в строке, решению которой посвящены работы многих профессионалов за последние 20-30 лет, показано, как построить занятия по информатике, чтобы побудить школьника к творчеству, развить у него вкус к решению исследовательских проблем. Для школьников, преподавателей информатики, а также для студентов, выбравших информатику в качестве основной специальности. Книга может быть использована как в обычных школах при проведении факультативных занятий, так и в образовательных учреждениях с углубленным изучением информатики и математики.
Окулов, С. М. Алгоритмы обработки строк : учебное пособие / С. М. Окулов. — 4-е изд. — Москва : Лаборатория знаний, 2020. — 258 с. — (Развитие интеллекта школьников). - ISBN 978-5-00101-658-8. - Текст : электронный. - URL: https://znanium.com/catalog/product/1094351 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
С. М. Окулов

АЛГОРИТМЫ
ОБРАБОТКИ
СТРОК

Москва
Лаборатория знаний
2020

4-е издание,  электронное

УДК 519.85(023)
ББК 22.18

О-52

С е р и я о с н о в а н а в 2008 г.
Окулов С. М.

О-52
Алгоритмы
обработки
строк
/
С. М. Окулов. —
4-е изд., электрон. — М. : Лаборатория знаний, 2020. —
258 с. — (Развитие интеллекта школьников). — Систем.
требования:
Adobe
Reader
XI
;
экран
10".— Загл.
с титул. экрана. — Текст : электронный.
ISBN 978-5-00101-658-8
На
материале
задачи
поиска
подстроки
в
строке,
решению которой посвящены работы многих профессионалов
за последние 20–30 лет, показано, как построить занятия
по информатике, чтобы побудить школьника к творчеству,
развить у него вкус к решению исследовательских проблем.
Для школьников, преподавателей информатики, а также
для студентов, выбравших информатику в качестве основной
специальности. Книга может быть использована как в обычных школах при проведении факультативных занятий, так
и в образовательных учреждениях с углубленным изучением
информатики и математики.
УДК 519.85(023)
ББК 22.18

Деривативное издание на основе печатного аналога: Алгоритмы
обработки
строк
/
С. М. Окулов. — 2-е
изд. —
М. : БИНОМ. Лаборатория знаний, 2015. — 255 с. : ил. —
(Развитие интеллекта школьников).
ISBN 978-5-9963-1931-2.

В
соответствии
со
ст. 1299
и
1301
ГК
РФ
при
устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации

ISBN 978-5-00101-658-8
c○ Лаборатория знаний, 2015

2

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Глава 1. Строки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2. Методы предварительного анализа строк . . . . . . . . . 13

Глава 2. Классические алгоритмы решения задач
обработки строк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.1. Алгоритм Д. Кнута – Дж. Морриса – В. Пратта . . . . 28
2.2. Алгоритм Р. Бойера – Дж. Мура . . . . . . . . . . . . . . . . . 36
2.3. Алгоритм Р. Карпа – М. Рабина. . . . . . . . . . . . . . . . . . 52
2.4. Алгоритм Shift-And. . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.5. Использование элементов теории автоматов
в решении задач обработки строк . . . . . . . . . . . . . . . . 73

2.6. Алгоритм М. Крочемора . . . . . . . . . . . . . . . . . . . . . . . . 81
2.7. Алгоритм М. Мейна – Р. Лоренца . . . . . . . . . . . . . . . . 88

Глава 3. Деревья суффиксов. . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

3.1. Основные понятия. Простые алгоритмы
построения дерева суффиксов . . . . . . . . . . . . . . . . . . 103

3.2. Алгоритм Э. Укконена . . . . . . . . . . . . . . . . . . . . . . . . 118
3.3. Алгоритм Е. Мак-Крейга . . . . . . . . . . . . . . . . . . . . . . 127
3.4. Суффиксные массивы . . . . . . . . . . . . . . . . . . . . . . . . . 136
3.5. Алгоритм А. Ахо – М. Корасик . . . . . . . . . . . . . . . . . 147

Глава 4. Вычисление расстояния между строками . . . . . . 155

4.1. Основной алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.2. Алгоритм Э. Укконена – Ю. Майерса . . . . . . . . . . . . 165
4.3. Задача о наибольшей общей
подпоследовательности двух строк . . . . . . . . . . . . . 174

Оглавление

Глава 5. Алгоритмы приближенного поиска подстрок . . 198

5.1. Простой алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.2. Алгоритм С. Ву – Ю. Менбера . . . . . . . . . . . . . . . . . . 201
5.3. Задача о k-несовпадениях . . . . . . . . . . . . . . . . . . . . . . 205
5.4. Алгоритм Ю. Майерса . . . . . . . . . . . . . . . . . . . . . . . . . 215

Вместо заключения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

Приложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

4
Оглавление

Что может быть эффективнее для развития творческих
возможностей школьника и его интеллекта, чем решение задач, казалось бы, очень простых, но «тянущих» за собой проблемы, исследованием которых занимались ведущие специалисты по информатике в последние 20–30 лет? Одной из таких задач является задача поиска подстроки в строке,
которая так или иначе затрагивается в любом учебнике по
информатике. Длительность ее решения с помощью самого
простого алгоритма пропорциональна произведению длин
строки и подстроки, и, несмотря на возросшую производительность компьютера, она оказывается слишком большой
для многих приложений. Можно ли найти такие алгоритмы
решения этой задачи, чтобы произведение заменялось хотя
бы суммой? Оказывается, да, и эта замена является сутью работ лучших умов в информатике, многие из которых продолжают свою деятельность и в настоящее время.
Данная книга конструктивно построена в виде занятий,
ее материал апробирован в ходе проведения реальных уроков1). Особенность изложения этого материала заключается
в том, что он не приводится в виде конечных результатов
(лемм, теорем, фактов и т. д.). Напротив, автором сделана попытка показать сам процесс получения нового результата,
а он не появляется сразу доказательно оформленным. Конеч
Михаилу, сыну моему, посвящаю.

Предисловие

Все должно быть изложено так
просто, как только возможно, —
но не проще.
Альберт Эйнштейн

1) Первая попытка изложения части предлагаемого здесь материала была сделана в 1997 г. (Бабушкина И. А., Бушмелева Н. А., Окулов С. М., Черных С. Ю. Конспекты занятий по информатике (практикум по Турбо Паскалю). — Киров: Изд-во ВГПУ, 1997).

ное оформление по принятым «правилам игры» при написании книг такого типа обычно скрывает способ его «рождения» — в каких «муках» и как он получен. «Ни один ученый
не
мыслит
формулами»,
—
любил
говорить
Альберт
Эйнштейн. В основе любого алгоритма лежит какая-то образная картинка или ясная идея. Воссоздать эту картинку,
взять на себя смелость утверждения о «рождении» результата именно так, как описывается в книге (через примеры, через эксперименты — а они обязательны — и ошибки с «набросками» кода) — страшно. Но если читатель подвергнет
все сомнению, то автор будет считать, что он уже достиг
цели, ибо специалист по информатике обязан все подвергать
сомнению и ничего не принимать на веру! Такое сомнение в
правильности результатов и самостоятельная работа приведут вас к моментам «Эврика!», к рождению нового, и, может
быть, ваша фамилия так же войдет в историю информатики,
как и фамилии авторов рассматриваемых здесь алгоритмов...
В предмете «информатика», а именно в олимпиадных
соревнованиях по информатике, сложилась уникальная ситуация, которой нет ни в одном школьном предмете. Например, тематика заданий олимпиад по математике опирается
на школьный курс, что вполне естественно. В олимпиадной
же информатике (назовем ее так) существует как минимум
три направления: первое, поддерживаемое и развиваемое
международным сообществом, связано с алгоритмами и
программированием; второе — это олимпиады по базовому
курсу информатики; третье — различного рода соревнования по использованию информационных технологий. Связь
первого направления со школьным курсом информатики
ограничена несколькими разделами, второе направление
полностью адекватно курсу, а третье — лишь частично. Для
достижения результатов в рамках первого направления
знать и уметь требуется много, очень много, и любой школьный учебник не входит в этот необходимый минимум. Если
выразиться точнее, то победитель соревнований первого
типа не всегда сможет выразить свои мысли тем языком, который задается учебниками, хотя, конечно, он знает их материал, но только на совершенно другом уровне понимания
и осознания.
Рассматриваемые в книге алгоритмы (основные) входят
в примерную программу по олимпиадной информатике всего
одной строкой — «алгоритмы поиска подстроки в строке

6
Предисловие

за O(n+m)»1). Эти алгоритмы относятся к дидактическим
единицам, «изучение которых формирует у школьников
ключевые умения в области олимпиадной подготовки, открывает перед участником олимпиадного состязания возможность проявить свой творческий потенциал на достойном уровне ... — победителей и призеров заключительных
этапов Всероссийской олимпиады школьников»2).

Структура книги
Первая глава, с одной стороны, является вводной, а с
другой — дает основы предварительного анализа строк, без
которых понимание многих изложенных далее алгоритмов
невозможно. Но, вероятно, главным в ней следует считать
«очерчивание» одного из основных способов построения эффективных алгоритмов, который заключается в тщательном анализе исходных данных с целью выявления в них закономерностей, а затем — в использовании этих закономерностей при решении основной задачи.
Во второй главе рассматриваются ставшие уже классикой алгоритмы Д. Кнута – Дж. Морриса – В. Пратта; Р. Бойера – Дж. Мура; Р. Карпа – М. Рабина; Shift–And (Б. Дёмёлки – Р. Беза-Йетс – Г. Гоннет); М. Крочемора и М. Мейна –
Р. Лоренца. Если первые четыре алгоритма посвящены проблеме поиска подстроки в строке, то последние два являются
основополагающими в задаче анализа свойств строки (текста). Во второй главе кратко показано, как использовать аппарат теории автоматов при описании алгоритмов на строках.
Третья глава целиком посвящена деревьям суффиксов — структуре данных, в которой фиксируются особенности строки (текста), позволяющие эффективно решать
многочисленные задачи обработки строк. Рассмотрены два
алгоритма — Э. Укконена и Е. Мак-Крейга, однако их рассмотрению предшествует анализ простых методов построения дерева суффиксов, что позволяет сделать изложение
доступным и ясным (с точки зрения автора). На остальные
известные алгоритмы решения этой задачи в данной книге
приводятся только ссылки.
В четвертой главе рассматриваются задачи вычисления
расстояния между строками и нахождения наибольшей общей подпоследовательности двух строк. Анализ первой за
Предисловие
7

1) Кирюхин В. М. Информатика: всероссийские олимпиады. — М.: Просвещение, 2008. С. 71.
2) Там же. С. 67.

дачи ограничивается основным алгоритмом и результатом
Э. Укконена – Ю. Майерса. Вторая проблема анализируется
через достижения С. Нудельмана – К. Вунша, Д. Ханта –
Т. Зиманского и Л. Эллисона – Т. Дикса.
Пятая глава посвящена достаточно значимой задаче
данной проблематики — приближенному поиску подстрок в
тексте. Даны простые алгоритмы, а также алгоритм С. Ву –
Ю. Менбера, алгоритм решения задачи о k-несовпадениях и
идейные основы алгоритма Ю. Майерса.
Вместо заключения читателям предлагается небольшое
эссе о предмете «информатика», из которого становятся яснее роль и место как материала данной книги, так и результата, получаемого в итоге деятельности по освоению рассматриваемых алгоритмов.
В
приложениях
раскрываются
некоторые
моменты
организации углубленного экспериментального исследования алгоритмов и приводится ряд проблем (задач) для индивидуальной творческой работы1). Рассмотренные в данной
книге алгоритмы — это, если можно так выразиться, только первый «пласт» указанного раздела информатики. Проблемы, приведенные в приложении, лишь частично восполняют этот пробел, полностью устраняемый, вероятно, лишь
последующими работами.

Благодарности
Я благодарю коллег: Евгения Вячеславовича Котельникова, Андрея Васильевича Лялина и многих других за интеллектуальную помощь, без которой вряд ли состоялся бы
этот труд. Особая признательность — Дмитрию Юрьевичу
Усенкову, сотруднику издательства «БИНОМ. Лаборатория
знаний», оперативность и доброжелательность работы которого вызывают восхищение. Глубочайшая благодарность —
директору издательства Михаилу Николаевичу Бородину,
который не только поверил в «пришедшего с улицы» автора
(в 2001 г.), но и все эти годы профессионально поддерживает
его деятельность.

8
Предисловие

1) На русском языке имеются только две фундаментальные переводные книги
по данной проблематике: Смит Б. Методы и алгоритмы вычисления на строках: пер. с англ. — М.: ООО «И. Д. Вильямс», 2006 и Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная
биология: пер. с англ. И. В. Романовского. — СПб.: Невский Диалект;
БХВ-Петербург, 2003. Автор, конечно же, использовал их (как и англоязычные статьи) при написании данной книги, которая, выражаясь педагогическим языком, является пропедевтикой к изучению названных книг, предоставляющих обширный материал по проблемам для индивидуальной творческой работы как школьника, так и студента.

1.1.
Основные понятия

Стену можно пробить только головой.
Все остальное — только орудия.
Лешек Кумор

Обычно говорят, что строка (S) — это последовательность символов, взятых из заранее определенного алфавита. При этом сразу возникают как минимум два вопроса, заключенные в понятиях «последовательность» и «алфавит».
Последовательность — это значит строка как одномерная структура, в которой каждый элемент (символ) имеет
уникальную метку в виде номера, а рассматриваются только
конечные элементы строки (первый и последний). Далее,
каждый элемент строки, кроме первого (самого левого), имеет единственный предшествующий элемент, а каждый элемент, кроме последнего (самого правого), имеет единственный следующий элемент. Проводя аналогию с языком программирования Паскаль, можно сказать, что для строки
работают операции pred(i) и succ(i), где i — номер символа
в строке, и справедливы равенства:
i = succ(pred(i))
(за исключением самого левого символа) и i = pred(succ(i))
(за исключением самого правого символа).
Алфавит — это интуитивно достаточно ясное понятие;
определим его как конечное множество A различимых элементов, на котором определено отношение порядка. Традиционные примеры алфавитов: латинский; русский; все символы в соответствии с их кодировкой ASCII. Алфавит из двух
символов (а компьютер работает с данными, представленны
Глава 1

Строки

И приходят мне в голову сказки
Мудрецами отмеченных дней,
И блуждаю я в них по указке
Удивительной птицы моей.
Николай Заболоцкий

ми в таком алфавите!) называют бинарным (двоичным).
Отношение порядка для символов из алфавита говорит о том,
что для любых x A и y A можно сделать вывод, какой
элемент больше другого, т. е. что x < y или y < x при x  y.
Понятие «подстрока» строки S определяется как S[i..j]
для любой пары таких чисел i и j, что 1 i j n, где n —
количество символов в S (длина строки, обозначим ее как
|S|). Если же i > j, то мы считаем подстроку S[i..j] пустой.
Другими словами, подстрока — это часть строки, состоящая
из некоторого количества смежных символов исходной
строки, и в данном случае «некоторое количество» определяется как j – i + 1. Можно выделить точно n – k + 1 подстрок длины k из строки S длины n: это подстроки S[1..k],
S[2..k + 1], ..., S[n – k + 1..n]. Общее количество подстрок с длинами от 1 до n определяется суммой —

(
)
n
k
n
n

k

n
1
2
1

2
, т. е. имеет порядок O(n2).

Строки (естественно, на одном алфавите) S1 и S2 равны,
если:
1) совпадают их длины (n);
2) S1[i] = S2[i] для всех i = 1, ..., n.

На множестве строк на упорядоченном алфавите A отношение порядка (лексикографического) вводится естественным образом. Пусть имеется две строки S1[1..n] и
S2[1..m], тогда мы говорим, что S1 < S2 (S1 лексикографически меньше S2), если выполняется одно из следующих
условий (взаимоисключающих):
а) n < m и S1[1..n] = S2[1..n];
б) существует такое целое число i (i 1..min{n, m}), что
S1[1..i – 1] = S2[1..i – 1] и S1[i] < S2[i] (или, другими
словами, i — первая позиция слева, в которой элементы S1 и S2 различны).

Примеры

abc < abcd (n = 3, m = 4); abdef < ada (i = 2, b < d).

Префикс строки S, заканчивающийся в позиции i, —
это подстрока S[1..i].
Суффикс строки S, начинающийся в позиции i, — это
подстрока S[i..n].

10
Глава 1. Строки

Префиксы и суффиксы называют собственными, если
они не являются пустыми и не совпадают с S.

Основная задача. Дана строка P (ее чаще всего называют образцом) и строка T (текст). Требуется найти все
вхождения образца P в текст T. Длины строк обозначим как
m = |P| и n = |T|.

Пример
P = aab, T = aacbaabaatabaabaaw. P входит в T, начиная с позиций 5 и 13.

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

Как нетрудно видеть, для решения поставленной задачи
образец P «прикладывается» левым концом к тексту T, начиная с его первой позиции, а затем осуществляется посимвольное сравнение образца и соответствующих символов текста. При этом возможны два исхода: произойдет несовпадение символов в какой-то позиции либо будет найдено
вхождение P в T (все символы P сравнены). Во втором случае
фиксируется факт совпадения, но в обоих случаях затем P
сдвигается на одну позицию вправо и процесс проверки совпадения повторяется. В данном алгоритме не учитываются
как результаты предыдущих сравнений, так и структура образца или текста.
Формализованная запись рассмотренного алгоритма
имеет следующий вид.

1.1. Основные понятия
11

Рис. 1.1. Пример простого поиска образца в тексте

Procedure Solve;
{P, T – глобальные величины типа String}
Var i,j:Integer;
Begin
For i:=1 To n-m+1 Do Begin
j:=1;
While (j<=m) And (P[j]=T[i+j-1]) Do j:=j+1;
If j=m+1 Then WriteLn('найдено вхождение P в T,
начиная с позиции ', i);
End;
End;

Оценим время работы этого алгоритма в количестве операций сравнения. Оно очевидно и имеет значение O(n·m).
Такая оценка достигается при n – m + 1 совпадениях, т. е.
когда и P, и T состоят из одного символа. При значениях
m > 103, n > 109 время работы такого алгориитма становится неприемлемым для многих приложений.

Целью специалистов по информатике за последние 30 лет
является разработка алгоритмов поиска вхождения образца в
текст (иногда — удивительных и неожиданных, как сказка ),
а также решение целого ряда родственных задач, с временной
оценкой порядка O(n + m). Большинство результатов при
этом основано на предварительном анализе образца или текста (в зависимости от задачи), направленном на выявление,
если можно так выразиться, его структуры, с последующим
использованием этой информации для решения задачи. Разумеется, смысл имеют только алгоритмы с временной оценкой
O(n) или O(m). Скажем, такой анализ P позволил бы решить
задачу из приведенного на рис. 1.1 примера не за 16 сдвигов,
а за гораздо меньшее их число (например, 9).
Упражнения

1.
Сформулируйте отличие следующей реализации простого алгоритма поиска вхождения P в T от ранее приведенной.

Procedure Solve;
{P, T – глобальные величины типа String}
Var i,j:Integer;
Begin
For i:=1 To n-m+1 Do Begin

12
Глава 1. Строки