Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных

Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных

Автор: Айткулов, Павел Григорьевич

Шифр специальности: 05.13.11

Научная степень: Кандидатская

Год защиты: 2010

Место защиты: Ижевск

Количество страниц: 97 с.

Артикул: 4871947

Автор: Айткулов, Павел Григорьевич

Стоимость: 250 руб.

Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных  Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных 

Оглавление
ВВЕДЕНИЕ
1 Обзор
1.1 Алгоритмы работы со строками
1.2 Обзор алгоритмов точного поиска преобразования образца .
1.3 Обзор суффиксных структур данных
1.4 Обзор алгоритмов построения суффиксных массивов
1.5 Аналогии с отсортированной коллекцией.
1.6 Замечание по используемым структурам данным.
1.7 Основные понятия
1.8 Обзор алгоритмов по изменению суффиксных структур данных
1.9 О 1ср и поиске минимума на отрезке
2 Разработка алгоритмов обработки символьных массивов
2.1 Алгоритм последовательного построения суффиксиого массива
2.1.1 Оценка алгоритмической сложности и затрат памяти
2.1.2 Преимущества алгоритма и недостатки алгоритма . .
2.2 Алгоритм блочного построения суффиксного массива
2.2.1 Оценка алгоритмической сложности и затрат памяти
2.2.2 Выбор блока
2.2.3 Преимущества и недостатки алгоритма.
2.3 Удаление подстроки
2.3.1 Оценка алгоритма.
3 Приложения построенных алгоритмов в базах данных
3.1 Приложение для баз данных и файловых систем
3.2 Поиск наибольшей общей подстроки.
3.3 Поиск наибольшей общей подстроки для двух строк
3.4 Поиск наибольшей общей подстроки для к строк.
3.5 Лексикографически наименьший суффикс
3.6 Линеаризация циклического слова
3.7 Потоковое приложение еуффиксных массивов к алгоритму
ЛемиеляЗива.
3.8 Техника скользящего окна.
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЕ
ВВЕДЕНИЕ
Актуальность


Для обработки таких больших данных требуются эффективные алгоритмы вычислений на строках. Существует два основных подхода в алгоритмах точного поиска образца : преобразование образца и суффиксные структуры данных2. В первом подходе образец является статичным, а исходный текст динамичен. Для каждого поискового запроса требуется прочитать исходный текст заново. Если исходный текст является статичным, то стоит воспользоваться суф-фиксными структурами данных. В квантовых вычислениях имеется алгоритм Гровера (| для быст]>ого поиска в неупорядоченной базе данных за 0{/п). В классических вычислениях эффективность алгоритмов на строках означает время работы близкое к линейному. В области неточного поиска используются другие меюды, например, на основе п-грамм |}. К недостаткам существующих алгоритмов построения суффиксных структур данных относится то, что для построения структуры требуется вся строка целиком. Это ограничивает использование суффиксных структур данных с потоковыми данными. Малое изменение строки приведет к полной перестройке суффиксной структуры. При использовании суффиксных структур данных для индексации текстовых записей в базах данных малое изменение (добавление, удаление или изменение одной записи) приводит к полной перестройке индекса. Целью работы является построение эффективных алгоритмов изменения суффиксных структур данных (суффиксных массивов), построение приложений для индексации текстовых записей в базах данных. Эффективность подразумевает линейные (близкие к линейным) затраты от длины изменившейся части строки. Методы исследования. В работе применяются методы теории алгоритмов и сложности, амортизационного анализа, алгебры, динамического программирования. Используются алгоритмы и структуры данных из таких областей, как теория автоматов, теория графов, строковые алгоритмы. Научная новизна. В работе построены алгоритмы модификации такой суффиксной структуры данных, как суффиксный массив. Построены алгоритмы потокового построения суффикспого массива и удаления подстроки из суффиксного массива. Построен алгоритм препроцессинга (создание всех дополнительных структур данных на основе текущего суффиксного массива и строки). Индексация строковых полей в базе данных и имен файлов в файловой системе применена на практике. Построенные алгоритмы позволяют решать задачу о наибольшей общей подстроке для динамического случая для одной, двух и к строк. Были известны решения только для статического случая. Построен алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига. Для поиска лексикографически наименьшего суффикса были известны потоковые решения, а для задачи лексикографически наименьшего циклического сдвига только решения для статического случая. Построено приложение к архивации. Предлагается использовать потоковое построение суффиксных массивов для ? Построено приложение к технике «скользящего окна» (поддержка суффиксного массива только для последних символов потока). Достоверность результатов обеспечивается строгостью доказательств и подтверждается практическими результатами реализованных алгоритмов. Практическая и теоретическая ценность. Решен класс динамических задач (динамическая задача о наибольшей общей подстроке, лексикографически наименьший суффикс, циклический сдвиг). Построено приложение к архивации: предлагается использовать суффиксные массивы в качестве внутренней структуры данных для алгоритма потокового сжатия Лемпеля-Зива. Реализация и внедрение результатов работы. Результаты исследования (потоковое построение суффиксных массивов) внедрены в практическую деятельность и используются в программных продуктах ОАО «НК Роснефть», что подтверждается актом о внедрении результатов диссертационной работы. Алгоритм последовательного построения суффиксного массива. Алгоритм блочного построения суффиксного массива. Алгоритм удаления подстроки из суффиксного массива. Приложение для индексации текстовых записей в базах данных. Алгоритм динамического поиска наибольшей общей подстроки для к строк.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.212, запросов: 244