Эффективные алгоритмы для некоторых задач обработки слов

• Автор: Стариковская, Татьяна Андреевна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 94 с. : ил.

Оглавление
Введение
1 Основные понятия и структуры данных
1.1 Понятия алфавита и слова
1.2 Суффиксное дерево
1.2.1 Приложение: задача о поиске образца
1.2.2 Построение суффиксного дерева
1.3 Суффиксный массив
1.4 Обобщенные суффиксные деревья и массивы
2 Поиск вхождений образца
2.1 Поиск вхождений образца с помощью разреженного суффиксного дерева
2.1.1 Разреженное суффиксное дерево
2.1.2 Алгоритм
2.1.3 Построение разреженного суффиксного дерева
2.2 Перекрёстный поиск образца
2.2.1 Задача о взвешенных предках
2.2.2 Задача о перекрёстном поиске образца
2.2.3 Динамические структуры данных
3 Разложение Лемпеля — Зива
3.1 Алгоритм
3.1.1 Структуры данных
3.1.2 Процедура Р<г

3.1.3 Процедура Р>,
3.2 Детали реализации
3.2.1 Бор
3.2.2 Суффиксное дерево
3.3 Оценки времени работы и объема памяти
4 Общие подслова
4.1 1-неточное наибольшее общее подслово
4.1.1 Общее описание алгоритма
4.1.2 Вычисление наибольших общих префиксов
4.1.3 Вычисление наибольших общих суффиксов
4.2 Максимальные и минимальные общие подслова
4.2.1 Максимальные общие подслова для заданного с?
4.2.2 Минимальные общие подслова для заданного с£
Литература

Введение
В работе рассматриваются различные задачи обработки слов и предлагаются эффективные алгоритмы для их решения.
Рассматриваемая область интересна как с теоретической точки зрения, так и с практической: во-первых, она имеет многочисленные связи с комбинаторикой слов, теорией конечных автоматов, вычислительной геометрией, во-вторых, она имеет приложения в биоинформатике, обработке текстов, распознавании речи, компьютерном зрении.
Под словом мы понимаем конечную упорядоченную последовательность элементов конечного непустого множества, называемого алфавитом. Элементы этого множества называются буквами.
Поскольку задачи на словах имеют важные практические приложения, то нас будут интересовать модели вычислений, которые, в некотором приближении, описывают процессы, происходящие в реальном компьютере. В настоящей работе используются две модели вычислений.
Первая модель вычислений, которая будет использоваться по умолчанию, — это равнодоступная адресная машина, сокращенно РАМ (см. [2]). РАМ состоит из входной ленты, с которой она может только считывать данные, выходной ленты, на которую она может только записывать данные, и памяти. Память машины состоит из последовательности ячеек, в каждой из которых можно хранить произвольное целое число в двоичной записи. Число ячеек, которое можно использовать, не ограничено сверху. Такая идеализация допустима в случаях, когда 1) размер задачи достаточно мал, чтобы она поместилась в оперативную память вычислительной машины;

процедурой, в самом деле являются начальными позициями вхождений суффиксов Р[к + 1..],0 Покажем, что процедура не пропускает ни одной такой границы. Это следует из определения суффиксных ссылок: а именно, при переходе по суффиксной ссылке (строки 20-22), алгоритм переходит от поиска конца пути, помеченного суффиксом Р[к + 1..], к поиску конца пути, помеченного суффиксом Р[к + г + 1..], где і - - тип суффиксной ссылки. Предположим, суффикс Р[к + г' + 1-.], і' < г, представлен в дереве. Но тогда бы, но определению, тип суффиксной ссылки был бы равен і' — противоречие. □
Теперь докажем оценку на время работы процедуры ШснтБеацсн. Ребра 5ТГ, с которыми работает процедура, можно разделить на два класса: просмотренные полностью и просмотренные частично (тупиковые), что могло случиться при несовпадении букв или достижении конца образца.
Количество тупиковых ребер не превышает г, так как просмотр любого из них завершает поиск Р[к + 1..] в 5ТГ. При работе с любым из тупиковых ребер алгоритм сравнивает не более Pft блоков букв. Тем самым, время, которое процедура потратит на работу с тупиковыми ребрами, равно 0-~).
Количество сравнений блоков, которые процедура сделает при работе с полностью просмотренными ребрами, ограничено сверху числом |Р|, так как эти сравнения относятся к разным участкам образца. Другими словами, последовательность этих сравнений может быть проиллюстрирована движением указателя в образце слева направо блоками по і букв. Тем самым, время, которое будет потрачено на сравнения блоков букв, равно 0(|Р|).
Теорема 2. ([66], Г.А. Кучеров, Р.М. Колпаков) ШСНТЭЕАНСН вычисляет ранговые интервалы суффиксов Р[к+1..], 0 < к < г— 1, у которых есть вхождения в слово Т, начинающиеся на границах блоков, за время