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

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

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




Примечательные слова.
Помимо слов Линдона, есть еще три класса слов, которые обладают примечательными свойствами и часто используются в примерах. Это слова Туэ–Морса, слова Фибоначчи и слова де Брёйна. Первые два – префиксы (односторонне) бесконечных слов. Формально бесконечным словом над алфавитом A называется отображение множества натуральных чисел в A. Множество бесконечных слов обозначается A.

Содержание.
От издательства.
Предисловие.
Глава 1.Первые понятия стрингологии.
Глава 2.Комбинаторные задачи.
Глава 3.Сопоставление с образцом.
Глава 4.Эффективные структуры данных.
Глава 5.Регулярные структуры в словах.
Глава 6.Сжатие текста.
Глава 7.Разное.
Литература.
Предметный указатель.

Купить .





Теги: Крошемор :: Лекрок :: Риттер :: книги по информатике :: информатика :: обработка текста