Сопоставление строк – одна из самых старых тем в теории алгоритмов, но по-прежнему занимает важное место в информатике. За прошедшие 20 лет мы видели технологические прорывы в таких разных приложениях, как информационный поиск и сжатие информации. Эта книга, представляющая собой богатое собрание задач и упражнений по важнейшим вопросам алгоритмов обработки текстов и комбинаторных свойств слов, предлагает студентам и исследователям приятный и прямой путь к изучению и практическому освоению концепций повышенного уровня.
Задачи взяты из многочисленных научных публикаций – как уже ставших классическими, так и сравнительно новых. Начав с основ, авторы рассматривают все более сложные задачи по комбинаторным свойствам слов (включая слова Фибоначчи и Туэ–Морса), поиску строк в тексте (включая алгоритмы Кнута–Морриса–Пратта и Бойера–Мура), эффективным структурам данных для представления текстов (включая суффиксные деревья и суффиксные массивы) и сжатия текста (включая методы Хаффмана, Лемпеля–Зива и Барроуза–Уилера).
Издание будет полезно в качестве пособия для подготовки к олимпиадам по информатике.
Author(s): Максим Крошемор, Тьерри Лекрок, Войцех Риттер
Edition: 1
Publisher: ДМК Пресс
Year: 2021
Language: Russian
Commentary: Vector PDF
Pages: 312
City: М.
Tags: Algorithms; Pattern Recognition; Data Structures; Text Analysis; Combinatorics; Compression Algorithms; Puzzles; Competitive Programming; String Algorithms
От издательства
Предисловие
Глава 1. Первые понятия стрингологии
Слова
Периодичность
Регулярные структуры
Упорядочение
Примечательные слова
Автоматы
Префиксные деревья
Суффиксные структуры
Суффиксный массив
Сжатие
Соглашения о псевдокоде алгоритмов
Примечания
Глава 2. Комбинаторные задачи
1. Стрингологическое доказательство малой теоремы Ферма
2. Простой случай проверки однозначности декодирования
3. Магические квадраты и слово Туэ–Морса
4. Последовательность Ольденбургера–Колакоски
5. Бесквадратная игра
6. Слова Фибоначчи и фибоначчиева система счисления
7. Игра Витхоффа и слово Фибоначчи
8. Различные периодические слова
9. Вариации на тему слова Туэ–Морса
10. Слова Туэ–Морса и суммы степеней
11. Сопряженные слова и ротации слов
12. Сопряженные палиндромы
13. Много слов с большим числом палиндромов
14. Короткое суперслово перестановок
15. Короткая суперпоследовательность перестановок
16. Слова Сколема
17. Слова Лэнгфорда
18. От слов Линдона к словам де Брёйна
Глава 3. Сопоставление с образцом
19. Таблица границ
20. Кратчайшие покрытия
21. Короткие границы
22. Таблица префиксов
23. От таблицы границ к максимальному суффиксу
24. Тест периодичности
25. Строгие границы
26. Задержка последовательного сопоставления строк
27. Разреженный автомат сопоставления
28. Сопоставление со строкой, эффективное с точки зрения числа сравнений
29. Таблица строгих границ слова Фибоначчи
30. Слова с подстановочными переменными
31. Образцы, сохраняющие порядок
32. Параметрическое сопоставление
33. Таблица хороших суффиксов
34. Худший случай в алгоритме Бойера–Мура
35. Алгоритм Turbo-BM
36. Сопоставление с образцом при наличии универсального символа
37. Циклическая эквивалентность
38. Простое вычисление максимального суффикса
39. Самомаксимальные слова
40. Максимальный суффикс и его период
41. Критическая позиция в слове
42. Периоды префиксов слов Линдона
43. Поиск слов Зимина
44. Поиск нерегулярных двумерных образцов
Глава 4. Эффективные структуры данных
45. Списковый алгоритм для кратчайшего покрытия
46. Вычисление наибольших общих префиксов
47. От суффиксного массива к суффиксному дереву
48. Линейное суффиксное trie-дерево
49. Троичное префиксное дерево поиска
50. Наибольший общий фактор двух слов
51. Автомат подпоследовательностей
52. Проверка однозначности декодирования
53. Таблица LPF
54. Сортировка суффиксов слов Туэ–Морса
55. Простое построение суффиксного дерева
56. Сравнение суффиксов слова Фибоначчи
57. Устранимость двоичных слов
58. Устранимость множества слов
59. Минимальные уникальные факторы
60. Минимальные отсутствующие слова
61. Жадная суперстрока
62. Кратчайшая общая суперстрока коротких слов
63. Подсчет факторов по длине
64. Подсчет факторов, покрывающих позицию
65. Наибольшие факторы с одинаковой четностью
66. Установление свободы слова от квадратов с помощью словаря базовых факторов
67. Общие решения факторных уравнений
68. Поиск в бесконечном слове
69. Совершенные слова
70. Плотные двоичные слова
71. Факторный оракул
Глава 5. Регулярные структуры в словах
72. Три квадрата префиксов
73. Точные границы количества вхождений степеней
74. Вычисление серий для алфавитов общего вида
75. Проверка перекрытий в двоичном слове
76. Игра, свободная от перекрытий
77. Заякоренные квадраты
78. Слова, почти свободные от квадратов
79. Двоичные слова с небольшим числом квадратов
80. Построение длинных свободных от квадратов слов
81. Проверка свободы морфизма от квадратов
82. Число квадратных факторов в помеченных деревьях
83. Подсчет квадратов в гребнях за линейное время
84. Кубические серии
85. Короткий квадрат и локальный период
86. Число серий
87. Вычислений серий над отсортированным алфавитом
88. Периодичность и факторная сложность
89. Периодичность морфических слов
90. Простые антистепени
91. Палиндромическая конкатенация палиндромов
92. Деревья палиндромов
93. Неустранимые образцы
Глава 6. Сжатие текста
94. Преобразование Барроуза–Уилера слов Туэ–Морса
95. Преобразование Барроуза–Уилера сбалансированных слов
96. Преобразование Барроуза–Уилера на месте
97. Факторизация Лемпеля–Зива
98. Декодирование Лемпеля–Зива–Уэлча
99. Стоимость кода Хаффмана
100. Кодирование Хаффмана с ограничением на длину
101. Динамическое кодирование Хаффмана
102. Кодирование длинами серий
103. Компактный факторный автомат
104. Сжатое сопоставление в слове Фибоначчи
105. Предсказание по частичному совпадению
106. Сжатие суффиксных массивов
107. Коэффициент сжатия жадных суперстрок
Глава 7. Разное
108. Двоичные слова Паскаля
109. Самовоспроизводящиеся слова
110. Веса факторов
111. Разности вхождений букв
112. Факторизация с префиксами, свободными от границ
113. Тест примитивности для унарных расширений
114. Частично коммутативные алфавиты
115. Наибольшее ожерелье фиксированной плотности
116. Двоичные слова, эквивалентные по периодам
117. Динамическое генерирование слов де Брёйна
118. Рекурсивное генерирование слов де Брёйна
119. Уравнения в словах с заданными длинами переменных
120. Разнородные факторы над трехбуквенным алфавитом
121. Наибольшая возрастающая подпоследовательность
122. Неустранимые множества и слова Линдона
123. Синхронизация слов
124. Сейфооткрывающие слова
125. Суперслова укороченных перестановок
Литература
Предметный указатель
