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

• Автор: Айткулов, Павел Григорьевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Ижевск
• Количество страниц: 97 с.

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