Вычислительная сложность некоторых задач обработки строк
|
1 Введение 5
1.1 Структура диссертации и организация текста 6
1.2 Предварительные сведения 9
1.2.1 Понятия из стрингологии 9
1.2.2 Модель вычисления ШоЫ-ИЛМ 10
1.2.3 Типы алгоритмических задач 11
1.2.4 Структуры данных 12
1.2.5 Исходные коды программ 13
1.2.6 Используемые структуры данных 13
1.3 Обзор результатов диссертации 15
1.3.1 Цели, задачи и основные результаты 16
1.3.2 Научная новизна, значимость и корректность результатов 17
1.3.3 Основные методы исследования 17
1.3.4 Апробация и публикации 17
1.4 Благодарности 19
2 Палиндромы 20
2.1 Введение 20
2.1.1 Определения и обозначения 21
2.2 Овердрево 21
2.2.1 Побуждающая задача: поиск подпалиндромов онлайн 21
2.2.2 Интерфейс структуры данных 26
2.2.3 Внутреннее устройство структуры данных 26
2.2.4 Простой онлайн-алгоритм 27
2.2.5 Некоторые свойства овердрева 29
2.2.6 Задачи, иллюстрирующие возможности овердрева 31
2.3 Вариации овердрева и некоторые их приложения 36
2.3.1 Совместное овердрево для нескольких строк 36
2.3.2 Поиск с откатами 38
2.3.3 Подсчёт палиндромно-насыщенных строк 42
2.3.4 Поиск подпалиндромов на дереве 45
2.4 Задачи о разбиении на подпалиндромы 47
2.4.1 Простое решение за O(kn + n log n) 48
2.4.2 Разбиение на k палиндромов и поиск палиндромной длины 49
2.4.3 Решение задачи о палиндромной длине 50
2.4.4 Гипотеза о линейном решении 55
3 Повреждённые строки 60
3.1 Введение 60
3.2 Предварительные сведения 61
3.2.1 Основные определения 61
3.2.2 Исторический обзор 61
3.3 Задача максимизации числа вхождений 63
3.3.1 Решение для неповреждённого текста 63
3.3.2 Решение для неповреждённого шаблона 64
3.3.3 Доказательство NP-трудности в общем случае 65
3.4 Задача минимизации расстояния Хэмминга 68
3.4.1 Случай неповреждённого текста 68
3.4.2 Случай неповреждённого шаблона 69
3.4.3 Случай частичных строк с циклическим текстом 69
3.4.4 Случай бинарного алфавита 70
3.4.5 Случай частичных строк и задача о мультиразрезе 71
3.4.6 Доказательство NP-трудности в общем случае 72
Заключение 75
Список литературы 77
Список иллюстраций
Список таблиц
1.1 Структура диссертации и организация текста 6
1.2 Предварительные сведения 9
1.2.1 Понятия из стрингологии 9
1.2.2 Модель вычисления ШоЫ-ИЛМ 10
1.2.3 Типы алгоритмических задач 11
1.2.4 Структуры данных 12
1.2.5 Исходные коды программ 13
1.2.6 Используемые структуры данных 13
1.3 Обзор результатов диссертации 15
1.3.1 Цели, задачи и основные результаты 16
1.3.2 Научная новизна, значимость и корректность результатов 17
1.3.3 Основные методы исследования 17
1.3.4 Апробация и публикации 17
1.4 Благодарности 19
2 Палиндромы 20
2.1 Введение 20
2.1.1 Определения и обозначения 21
2.2 Овердрево 21
2.2.1 Побуждающая задача: поиск подпалиндромов онлайн 21
2.2.2 Интерфейс структуры данных 26
2.2.3 Внутреннее устройство структуры данных 26
2.2.4 Простой онлайн-алгоритм 27
2.2.5 Некоторые свойства овердрева 29
2.2.6 Задачи, иллюстрирующие возможности овердрева 31
2.3 Вариации овердрева и некоторые их приложения 36
2.3.1 Совместное овердрево для нескольких строк 36
2.3.2 Поиск с откатами 38
2.3.3 Подсчёт палиндромно-насыщенных строк 42
2.3.4 Поиск подпалиндромов на дереве 45
2.4 Задачи о разбиении на подпалиндромы 47
2.4.1 Простое решение за O(kn + n log n) 48
2.4.2 Разбиение на k палиндромов и поиск палиндромной длины 49
2.4.3 Решение задачи о палиндромной длине 50
2.4.4 Гипотеза о линейном решении 55
3 Повреждённые строки 60
3.1 Введение 60
3.2 Предварительные сведения 61
3.2.1 Основные определения 61
3.2.2 Исторический обзор 61
3.3 Задача максимизации числа вхождений 63
3.3.1 Решение для неповреждённого текста 63
3.3.2 Решение для неповреждённого шаблона 64
3.3.3 Доказательство NP-трудности в общем случае 65
3.4 Задача минимизации расстояния Хэмминга 68
3.4.1 Случай неповреждённого текста 68
3.4.2 Случай неповреждённого шаблона 69
3.4.3 Случай частичных строк с циклическим текстом 69
3.4.4 Случай бинарного алфавита 70
3.4.5 Случай частичных строк и задача о мультиразрезе 71
3.4.6 Доказательство NP-трудности в общем случае 72
Заключение 75
Список литературы 77
Список иллюстраций
Список таблиц
Строка (последовательность символов) — один из центральных объектов компьютерных наук.
Любые данные, имеющие линейную структуру (например, текст на естественном или искусственном языке, лог сервера или колебания курса валюты) можно представить в виде строки
и изучать особенности в этой строке. Начало активного изучения алгоритмов, связанных со
строками, приходится на 1970е годы. Раздел компьютерных наук, посвящённый изучению алгоритмов обработки строк, называется стрингологией (stringology). Впервые это название было
предложено в 1985 в работе [21], когда область уже имела какой-то набор результатов, но сложно было назвать её отдельной наукой. Однако уже в 90х годах наблюдается стремительный рост
числа публикаций по данной тематике. Одной из самых сильных предпосылок развития является появление биоинформатики, науки, изучающей «биологические строки» (ДНК, РНК, белки
и др.). Именно биоинформатика породила множество задач, изучаемых стрингологами. Не менее важным источником задач являются современные информационные технологии, требующие
эффективных алгоритмов анализа и обработки данных. Среди задач этой группы выделяются
задача поиска в массиве данных и задача сжатия данных. Кроме того, стрингология, относимая к фундаментальной информатике, решает большое число чисто математических задач, не
нашедших еще практического применения. Сюда относится, в частности, классификация задач
о строках по их вычислительной сложности. Многие теоретические задачи приходят в стрингологию из комбинаторики слов.
Развитость стрингологии как самостоятельной науки может показать, к примеру, наличие
ряда монографий [2, 12, 13, 48] и специализированных международных конференций и семинаров: String Processing and Information Retrieval (SPIRE), Combinatorial Pattern Matching (CPM),
5Prague Stringology Conference (PSC), StringMasters.
Данная работа сконцентрирована на двух классах задач из стрингологии. Первая — алгоритмы, связанные с поиском и анализом палиндромов1 в строках.
Любые данные, имеющие линейную структуру (например, текст на естественном или искусственном языке, лог сервера или колебания курса валюты) можно представить в виде строки
и изучать особенности в этой строке. Начало активного изучения алгоритмов, связанных со
строками, приходится на 1970е годы. Раздел компьютерных наук, посвящённый изучению алгоритмов обработки строк, называется стрингологией (stringology). Впервые это название было
предложено в 1985 в работе [21], когда область уже имела какой-то набор результатов, но сложно было назвать её отдельной наукой. Однако уже в 90х годах наблюдается стремительный рост
числа публикаций по данной тематике. Одной из самых сильных предпосылок развития является появление биоинформатики, науки, изучающей «биологические строки» (ДНК, РНК, белки
и др.). Именно биоинформатика породила множество задач, изучаемых стрингологами. Не менее важным источником задач являются современные информационные технологии, требующие
эффективных алгоритмов анализа и обработки данных. Среди задач этой группы выделяются
задача поиска в массиве данных и задача сжатия данных. Кроме того, стрингология, относимая к фундаментальной информатике, решает большое число чисто математических задач, не
нашедших еще практического применения. Сюда относится, в частности, классификация задач
о строках по их вычислительной сложности. Многие теоретические задачи приходят в стрингологию из комбинаторики слов.
Развитость стрингологии как самостоятельной науки может показать, к примеру, наличие
ряда монографий [2, 12, 13, 48] и специализированных международных конференций и семинаров: String Processing and Information Retrieval (SPIRE), Combinatorial Pattern Matching (CPM),
5Prague Stringology Conference (PSC), StringMasters.
Данная работа сконцентрирована на двух классах задач из стрингологии. Первая — алгоритмы, связанные с поиском и анализом палиндромов1 в строках.
В заключении, представив краткое резюме по каждой из двух основных глав, обсудим пути
дальнейшей возможной работы в соответствующих направлениях и сформулируем связанные
оставшиеся открытыми проблемы.
Палиндромы
В данной главе мы описали новую компактную и быструю структуру данных — овердрево. Рассмотрели его различные модификации, которые более эффективны в использовании времени,
либо памяти. Одна из модификаций позволяет сделать овердрево с откатами, другая делает его
персистентным. Разобрали множество возможных применений, получив теоретически быстрые
и практически легко реализуемые алгоритмы для ряда комбинаторных задач. Самыми существенными из представленных применений являются простая реализация разбиения строки на
палиндромы, перечисление палиндромно-насыщенных строк, а также поиск всех различных
подпалиндромов строки.
Дальнейшие исследования в этом направлении связаны с поиском новых приложений овердрева, а также с гипотезой о возможности линейного поиска палиндромной длины и с открытой
проблемой об оптимальной реализации овердрева.
Повреждённые строки
В данной работе рассмотрены две задачи о восстановлении повреждений в тексте и шаблоне.
Для обеих задач общий случай оказался NP-трудным, а случаи неповреждённого текста и
неповреждённого шаблона — эффективно разрешимыми. При этом во второй задаче, где критерием восстановления является минимизация суммарного расстояния Хэмминга, полиномиально
разрешимых частных случаев оказалось больше.
Отдельно отметим, что для решения различных частных случаев использованы совершенно
75разные полиномиальные алгоритмы, основанные на жадных стратегиях, преобразовании Фурье,
динамическом программировании и потоках в сетях.
Дальнейшее исследование предполагает продолжение изучения задачи о минимизации непохожести шаблона и текста для частичных строк (частный случай, оставшийся открытым), а
также выделение дополнительных частных случаев обеих задач с целью выявления более простых подходов к решению.
дальнейшей возможной работы в соответствующих направлениях и сформулируем связанные
оставшиеся открытыми проблемы.
Палиндромы
В данной главе мы описали новую компактную и быструю структуру данных — овердрево. Рассмотрели его различные модификации, которые более эффективны в использовании времени,
либо памяти. Одна из модификаций позволяет сделать овердрево с откатами, другая делает его
персистентным. Разобрали множество возможных применений, получив теоретически быстрые
и практически легко реализуемые алгоритмы для ряда комбинаторных задач. Самыми существенными из представленных применений являются простая реализация разбиения строки на
палиндромы, перечисление палиндромно-насыщенных строк, а также поиск всех различных
подпалиндромов строки.
Дальнейшие исследования в этом направлении связаны с поиском новых приложений овердрева, а также с гипотезой о возможности линейного поиска палиндромной длины и с открытой
проблемой об оптимальной реализации овердрева.
Повреждённые строки
В данной работе рассмотрены две задачи о восстановлении повреждений в тексте и шаблоне.
Для обеих задач общий случай оказался NP-трудным, а случаи неповреждённого текста и
неповреждённого шаблона — эффективно разрешимыми. При этом во второй задаче, где критерием восстановления является минимизация суммарного расстояния Хэмминга, полиномиально
разрешимых частных случаев оказалось больше.
Отдельно отметим, что для решения различных частных случаев использованы совершенно
75разные полиномиальные алгоритмы, основанные на жадных стратегиях, преобразовании Фурье,
динамическом программировании и потоках в сетях.
Дальнейшее исследование предполагает продолжение изучения задачи о минимизации непохожести шаблона и текста для частичных строк (частный случай, оставшийся открытым), а
также выделение дополнительных частных случаев обеих задач с целью выявления более простых подходов к решению.
Подобные работы
- Вычислительная сложность
некоторых задач обработки строк
Авторефераты (РГБ), математика. Язык работы: Русский. Цена: 2000 р. Год сдачи: 2016 - Непараметрическая идентификация дискретно-непрерывных процессов по выборке наблюдений с пропусками
Магистерская диссертация, информационные системы. Язык работы: Русский. Цена: 4900 р. Год сдачи: 2018 - Разработка модифицированной нейронной сети адаптивной резонансной теории для решения задач распознавания изображений
Бакалаврская работа, физика. Язык работы: Русский. Цена: 4270 р. Год сдачи: 2016 - Методы обучения искусственных нейронных сетей в задачах распознавания образов
Магистерская диссертация, нейронные сети . Язык работы: Русский. Цена: 5600 р. Год сдачи: 2018 - Разработка модифицированной нейронной сети адаптивной резонансной теории для решения задач распознавания изображений
Бакалаврская работа, нейронные сети . Язык работы: Русский. Цена: 4700 р. Год сдачи: 2016 - Разработка семантического языка запросов для анализа больших данных
Бакалаврская работа, база данных. Язык работы: Русский. Цена: 4650 р. Год сдачи: 2020 - Планирование сбытовой деятельности компании на основе SWOT-модели с помощью FAHP
Дипломные работы, ВКР, информатика. Язык работы: Русский. Цена: 4325 р. Год сдачи: 2022 - Планирование сбытовой деятельности компании на основе SWOT-модели с помощью FAHP
Дипломные работы, ВКР, информатика. Язык работы: Русский. Цена: 4210 р. Год сдачи: 2022 - ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ОКАЗАНИЯ СОЦИАЛЬНЫХ УСЛУГ НАСЕЛЕНИЮ НА МУНИЦИПАЛЬНОМ УРОВНЕ
Магистерская диссертация, социальная работа. Язык работы: Русский. Цена: 4800 р. Год сдачи: 2017