Алгоритмы обработки текста, 125 задач с решениями, Крошемор М., Лекрок Т., Риттер В., 2021

Алгоритмы обработки текста, 125 задач с решениями, Крошемор М., Лекрок Т., Риттер В., 2021.

   Сопоставление строк - одна из самых старых тем в теории алгоритмов, но по-прежнему занимает важное место в информатике. За прошедшие 20 лет мы видели технологические прорывы в таких разных приложениях, как информационный поиск и сжатие информации. Эта книга, представляющая собой богатое собрание задач и упражнений по важнейшим вопросам алгоритмов обработки текстов и комбинаторных свойств слов, предлагает студентам и исследователям приятный и прямой путь к изучению и практическому освоению концепций повышенного уровня.
Задачи взяты из многочисленных научных публикаций - как уже ставших классическими, так и сравнительно новых. Начав с основ, авторы рассматривают все более сложные задачи по комбинаторным свойствам слов (включая слова Фибоначчи и Туэ-Морса), поиску строк в тексте (включая алгоритмы Кнута-Морриса-Пратта и Бойера-Мура), эффективным структурам данных для представления текстов (включая суффиксные деревья и суффиксные массивы) и сжатия текста (включая методы Хаффмана, Лемпеля-Зива и Барроуза-Уилера).
Издание будет полезно в качестве пособия для подготовки к олимпиадам по информатике.




Суффиксные структуры.
Суффиксные структуры данных, в которых хранятся суффиксы слова, важны для построения эффективных индексов. В этом качестве можно использовать префиксные деревья, но их размер может расти квадратично. Одно из решений этой проблемы - уплотнить префиксное дерево, получив суффиксное дерево слова. Для этого удаляются нелистовые узлы, из которых исходит только одно ребро, а дуги помечаются соответственными факторами слова. Удаленные узлы иногда называют неявными узлами суффиксного дерева, а оставшиеся узлы - явными.

Ниже показано префиксное дерево T(Suff(aabab)) суффиксов aabab (слева) и его суффиксное дерево STfaabab) (справа). Чтобы получить полную структуру линейного размера, каждый фактор слова, помечающий дугу, нужно представить парой целых чисел (позиция, длина).

ОГЛАВЛЕНИЕ.
От издательства.
Предисловие.
Глава 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. Суперслова укороченных перестановок.
Литература.
Предметный указатель.

Купить .





Теги: учебник по программированию :: программирование :: Крошемор :: Лекрок :: Риттер